时间戳

首页 > 解决方案 > 寻找最有效路径的算法

python - 寻找最有效路径的算法

问题描述

给定一只昆虫在从原点 (0,0) 开始的平面上移动。只能向东北、东南、西北和西南方向移动的昆虫。现在问题是昆虫一次只能向一个方向移动超过特定数量的步数。例如，NE只能移动3步，SE只能移动4步，NW只能移动5步，SW只能移动2步。

如果昆虫一次向 NE 方向移动 3 步——它必须向 NW、SE 或 SW 移动——然后再向 NE 方向移动。

在这种情况下，如何获得到达给定点的最有效路径？我是编程新手，遇到了这个问题。谁能告诉我解决这类问题的好方法？谢谢你。

我的想法：

首先，在 NE 和 SE 中走一步，在 E 中走 2 步。对于 N、S 和 W，同样如此。现在，找到最短路径。基本上，把这个问题变成一个更简单的问题，而不是走对角线。（不是一个好方法。但可以找到路径。）

第二个是受用于寻找 3-d 曲线最小值的迭代方法的启发。如果我取消一次只向一个方向行驶的限制，我们可以通过沿带我们更快到达目的地的方向（四个方向之一）移动来做到这一点。这类似于梯度下降法，但只有四个方向可以移动。

Python代码将不胜感激。

标签： pythonalgorithmdijkstra

解决方案

TL;DR：最短路径 => 考虑 Dijkstra 算法。

在这里，您可以想到一个带有节点的图(Last Move, Position)。计算四个可能的最短路径Last Move并取最短的一个。

注意：如果你只关心移动的数量，而不是移动的距离，那么广度优先搜索会更有效。

以下是 BFS 案例的一些代码：

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

如果目标真的很远，你可以使用通常的改进：双向搜索、带有一些启发式的 A* 算法等。

推荐阅读