<p>TL;DR:最短路径=>;考虑Dijkstra算法。你知道吗</p>
<p>在这里您可以想到一个节点为<code>(Last Move, Position)</code>的图。
计算四个可能的<code>Last Move</code>的最短路径并取最短路径。你知道吗</p>
<p>注意:如果你只关心移动的次数,而不关心移动的距离,那么广度优先搜索更有效。你知道吗</p>
<p>以下是BFS案例的一些代码:</p>
<pre><code>def neighbor(node):
last, (x,y) = node
r = []
for d in ['NE', 'NW', 'SE', 'SW']:
if d == last:
continue
if d == 'NE':
p = (x+3, y+3)
if d == 'NW':
p = (x-5, y+5)
if d == 'SE':
p = (x+4, y-4)
if d == 'SW':
p = (x-2, y-2)
r.append((d, p))
return r
def find_shortest_path(x,y):
"""
BFS to find the shortest path between (0,0) and (x,y)
NB: we consider all moves have the same cost
"""
predecessor = {(None, (0,0)): None}
queue = [(None, (0,0))]
while True:
if not queue:
return None
next_queue = []
for node in queue:
for n in neighbor(node):
if n not in predecessor:
predecessor[n] = node
last, (u,v) = n
if (u,v) == (x,y):
backtrack = []
while n in predecessor:
backtrack.append(n)
n = predecessor[n]
return list(reversed(backtrack))
next_queue.append(n)
queue = next_queue
</code></pre>
<p>如果目标真的很远,你可以使用通常的改进方法:双向搜索,A*算法和一些启发式算法,等等</p>