<p>在无法了解您是如何实现<code>neighbour</code>和<code>distance</code>函数的情况下,我仍然可以很好地猜测出什么问题:</p>
<p><strong>如果允许对角线遍历,则不应使用曼哈顿距离。</strong></p>
<p>目标函数中的曼哈顿距离应该是距离目标最短距离的度量。(事实并非如此,如果你能沿对角线穿过积木。)</p>
<p>解决这个问题最简单的方法是将曼哈顿距离保持为目标函数,并将邻居的定义更改为只包括四个左右上下相邻的单元。在</p>
<p><strong>编辑</strong></p>
<p>您的代码仍有问题。以下伪代码取自<a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="nofollow">wikipedia</a>。我已经在重要的地方做了记号,你得检查一下。您必须确保i)如果您找到更好的解决方案,您正在更新开放集中的节点;ii)始终考虑到以前的行驶距离。在</p>
<pre><code>function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node
came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Cost from start along best known path.
// Estimated total cost from start to goal through y.
f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
while openset is not empty
current := the node in openset having the lowest f_score[] value
if current = goal
return reconstruct_path(came_from, goal)
remove current from openset
add current to closedset
for each neighbor in neighbor_nodes(current)
// -
// This is the way the tentative_g_score should be calculated.
// Do you include the current g_score in your calculation parent.distance(self) ?
tentative_g_score := g_score[current] + dist_between(current,neighbor)
// -
if neighbor in closedset
if tentative_g_score >= g_score[neighbor]
continue
// -
// You never make this comparrison
if neighbor not in openset or tentative_g_score < g_score[neighbor]
// -
came_from[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openset
add neighbor to openset
return failure
function reconstruct_path(came_from, current_node)
if current_node in came_from
p := reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node
</code></pre>