python - 找到两点之间的最短路径

Question

我想编写一个代码，可以找到起点和终点之间的最短路径。我写了一个代码，它没有错误，但它没有做我想要的。

它显示“运动”，但它没有在终点完成。

我该如何解决这个问题，如何包含“路径”需要从头到尾的条件？

你有下面的“地图”和代码的例子。

非常感谢。

地图：

代码：

import random

def shortestWay(n):

    minx = 1 
    miny = 1

    maxx = 5
    maxy = 5

    x_start = 1
    y_start = 1

    X_end = 3
    Y_end = 5

    for i in range (n):

        way = random.choice(["up", "down", "left", "right"])


        if way == "up" and y_start<maxy:
                y_start +=1

        elif way == "down" and y_start>miny:
                y_start -=1

        elif way == "left" and x_start>minx:
                x_start -=1

        elif way == "right" and x_start<maxx:
                x_start += 1


    if x_start == X_end and y_start == Y_end:

        return(x_start,y_start)

    x1 = x_start
    y1 = y_start


    return (x1, y1)

list1 = []
for i in range(25):

    way = shortestWay(10)

    theShortestWay = abs(way[0]) + abs(way[1])

    list1.append(theShortestWay)

    x = min (list1)

    print(way, "distance from start: ", theShortestWay, "cells")

print ("Minimal distance: ", x)

标签： python

Answer 1

第一个函数“shortestWay(n)”在随机方向上进行 n 次迭代，很明显它可以降落在目的地 X,Y 之外的其他地方。例如，您应该根据当前与目标 X、Y 的距离制定算法。在每一步尝试使 abs(X_start - X_end) 和 abs(Y_start - Y_end) 尽可能小。