明星算法:距离启发法 [英] A star algorithm: Distance heuristics

问题描述

我正在使用A星算法，如此处所示(摘自解决方案

为什么试探法的更改会导致其更准确，并且运行时间更长?

第一个启发式距离平方会高估实际距离(在很多情况下，视情况而定)，即使实际距离是以相同方式计算的，因为实际距离是作为单个步长的总和计算的(总和的平方小于总和的平方).A *倾向于通过不进行足够的探索来确保找到最佳路线来对此做出响应，它更倾向于仅遵循所尝试的路线，因为向目标靠近一步会减少与目标的期望距离 lot (远远超出了步骤本身，因为启发式方法高估了太多).它通常不会备份(即从队列中取出某个先前打开的节点，而不是最近的节点)，然后尝试其他操作，因为返回意味着H值上升大于G值下降.

这具有您看到的两个效果:

1. 通常速度要快得多(在某些迷宫中，您可以欺骗"算法，使它以错误的方式停留更长的时间)
2. 不一定找到最佳路线

您的连通性是8个邻域，对于这个邻域而言，比欧几里得距离具有更好的启发性.请注意，路径不能具有任意角度，它必须笔直或成45度角，因此即使没有障碍物，欧几里德距离也会低估该距离.正确无误，但是您可以使用对角距离"启发式:(取自此处，并且易于适应Python-该站点还讨论了高估启发式算法的影响)

  function heuristic(node)=dx = abs(node.x-Goal.x)dy = abs(node.y-Goal.y)返回D *(dx + dy)+(D2-2 * D)* min(dx，dy) 

您将具有 D = 1，D2 = sqrt(2)来匹配您的欧几里得距离度量标准.

---

如果多个路径共享一个源或目标，则可以使用某些技术来重用某些工作(这无关紧要，因为它始终是对称的).例如，当您从A搜寻到B时，G分数可以存储在网格中(甚至可以将它们保留在节点之外).然后在搜索到到的路径时，那些保存的G得分代表了到A的真实距离.显然，可以使用这些得分来获得完美的启发式方法，但是使用起来甚至更快:从队列中提取出使用这种完美启发式算法来计算其F的节点，则最短路径是通过该节点的确定(因为其F是 actual 的长度)路径，并且显然是从优先级队列中走出的最短路径)，此外，您知道该路径无需进一步搜索(将保存的G分数回溯到A).

这导致的是，每次搜索路径都会积累可用于其他方向的其他搜索的信息.然后，在另一个方向上进行搜索会再次建立信息，以便在另一个方向上进行搜索，依此类推.应该注意一些-让内存使用爆炸很容易.可能并非所有信息都可以保留.

这可能也可以与跳转点搜索"结合使用，尽管要保存的G较少，所以它可能不是很有效，主要是浪费了很多空间.

I am using the A star algorithm as seen here (taken from http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/), but I have a problem I don't understand.

The heuristics given here is the square of the distance between two points. I found that if I take the square root of it instead, my results are more accurate, but the running time of the function increases dramatically (i.e. it goes over many, many more loops than before).

Why does the change in heuristics cause it to be more accurate, and take longer to run?

# Author: Christian Careaga ([e-mail])
# A* Pathfinding in Python (2.7)
# Please give credit if used

import numpy
from heapq import *


def heuristic(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def astar(array, start, goal):

    neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]

    close_set = set()
    came_from = {}
    gscore = {start:0}
    fscore = {start:heuristic(start, goal)}
    oheap = []

    heappush(oheap, (fscore[start], start))

    while oheap:

        current = heappop(oheap)[1]

        if current == goal:
            data = []
            while current in came_from:
                data.append(current)
                current = came_from[current]
            return data

        close_set.add(current)
        for i, j in neighbors:
            neighbor = current[0] + i, current[1] + j            
            tentative_g_score = gscore[current] + heuristic(current, neighbor)
            if 0 <= neighbor[0] < array.shape[0]:
                if 0 <= neighbor[1] < array.shape[1]:                
                    if array[neighbor[0]][neighbor[1]] == 1:
                        continue
                else:
                    # array bound y walls
                    continue
            else:
                # array bound x walls
                continue

            if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):
                continue

            if  tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in oheap]:
                came_from[neighbor] = current
                gscore[neighbor] = tentative_g_score
                fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                heappush(oheap, (fscore[neighbor], neighbor))

    return False

'''Here is an example of using my algo with a numpy array,
   astar(array, start, destination)
   astar function returns a list of points (shortest path)'''

nmap = numpy.array([
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,0,1,1,1,1,1,1,1,1,1,1,1,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,0,1,1,1,1,1,1,1,1,1,1,1,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0]])

print astar(nmap, (0,0), (10,13))

解决方案

Why does the change in heuristics cause it to be more accurate, and take longer to run?

The first heuristic, distance squared, overestimates the real distance (by a lot, depending on the situation) even though the actual distance is computed the same way, because the actual distance is computed as the sum of single steps (the sum of squares is less than the square of the sum). A* tends to respond to that by not exploring enough to guarantee finding the optimal route, it prefers to just keep following whatever route it is trying because taking a step closer to the goal reduces the expected distance to it by a lot (by much more than the step itself takes, because the heuristic overestimates so much). It will often not back up (ie take some previously-opened node from the queue instead of the most-recent node) and try something else, because going back means the H value goes up more than the G value goes down.

So this has the two effects you saw:

1. It's usually a lot faster (except in certain mazes where you can "trick" the algorithm into going the wrong way for longer than it otherwise would have)
2. It does not necessarily find the best route

Your connectivity is the 8-neighbourhood, for which there is a better heuristic than Euclidean distance. Note that a path cannot have an arbitrary angle, it has to go straight or at a 45 degree angle, so Euclidean distance underestimates the distance even in the absence of obstacles. That is OK for correctness, but you can use the "diagonal distance" heuristic: (taken from here and easy to adapt to Python - that site also discusses the impact of having an overestimating heuristic)

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

You would have D = 1, D2 = sqrt(2) to match your Euclidean distance metric.

---

There are some techniques that can be used to re-use some work if multiple paths share a source or destination (it doesn't matter which since it's symmetric anyway). For example, as you search from A to B, the G scores can be stored in a grid (they can even be left out of the nodes). Then on a search for a path towards A, those saved G scores represent the real distances to A. Obviously these could be used in order to have a perfect heuristic, but there is an even faster use: if a node that used such a perfect heuristic to calculate its F is drawn from the queue, then the shortest path is definitely through that node (since its F is the actual length of the path, and it is apparently the shortest since it came off of the priority queue), and moreover, you know the path with no further search (greedily follow the saved G scores back to A).

What this leads to is that every search for a path builds up information that can be used for an other search in the other direction. That search in the other direction then builds up information again for searches in that other direction and so forth. Some care should be taken - it is very easy to let the memory use explode. Likely not all information can be kept around.

This can probably be combined with Jump Point Search as well though there would be fewer G's to save so it's probably not very effective, mostly wasting a bunch of space.

这篇关于明星算法:距离启发法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！