Python: A*路由从数据框中的经度和纬度

Question

我有一个包含30000条记录的数据帧，格式如下：

ID | Name | Latitude | Longitude | Country |
1  | Hull | 53.744   | -0.3456   | GB      |

我想选择一条记录作为起始位置，一条记录作为目的地，并返回最短路径的路径（列表）。在

我用Geopy来计算点之间的距离

^{pr2}$

我必须阅读以下python教程： https://www.redblobgames.com/pathfinding/a-star/implementation.html

然而，它们创建了一个网格系统来导航。在

这是数据帧中记录的可视化表示：

这是我到目前为止找到的代码，但是它找不到路径：

def calcH(start, end):
    coords_1 = (df['latitude'][start], df['longitude'][start])
    coords_2 = (df['latitude'][end], df['longitude'][end])
    distance = (geopy.distance.vincenty(coords_1, coords_2)).km
    return distance

^计算点之间的距离

def getneighbors(startlocation):
    neighborDF = pd.DataFrame(columns=['ID', 'Distance'])
    coords_1 = (df['latitude'][startlocation], df['longitude'][startlocation])
    for index, row in df.iterrows():
        coords_2 = (df['latitude'][index], df['longitude'][index])
        distance = round((geopy.distance.vincenty(coords_1, coords_2)).km,2)
        neighborDF.loc[len(neighborDF)] = [index, distance]
    neighborDF = neighborDF.sort_values(by=['Distance'])
    neighborDF = neighborDF.reset_index(drop=True)

    return neighborDF[1:5]

^返回最近的4个位置（忽略自身）

openlist = pd.DataFrame(columns=['ID', 'F', 'G', 'H', 'parentID'])
closedlist = pd.DataFrame(columns=['ID', 'F', 'G', 'H', 'parentID'])

startIndex = 25479 # Hessle
endIndex = 8262 # Leeds

h = calcH(startIndex, endIndex)
openlist.loc[len(openlist)] = [startIndex,h, 0, h, startIndex]

while True:

#sort the open list by F score
openlist = openlist.sort_values(by=['F'])
openlist = openlist.reset_index(drop=True)

currentLocation = openlist.loc[0]
closedlist.loc[len(closedlist)] = currentLocation
openlist = openlist[openlist.ID != currentLocation.ID]

if currentLocation.ID == endIndex:
    print("Complete")
    break

adjacentLocations = getneighbors(currentLocation.ID)

if(len(adjacentLocations) < 1):
    print("No Neighbors: " + str(currentLocation.ID))
else:
    print(str(len(adjacentLocations)))

for index, row in adjacentLocations.iterrows():
    if adjacentLocations['ID'][index] in closedlist.values:
        continue

    if (adjacentLocations['ID'][index] in openlist.values) == False:

        g = currentLocation.G + calcH(currentLocation.ID, adjacentLocations['ID'][index])
        h = calcH(adjacentLocations['ID'][index], endIndex)
        f = g + h
        openlist.loc[len(openlist)] = [adjacentLocations['ID'][index], f, g, h, currentLocation.ID]
    else:
        adjacentLocationInDF = openlist.loc[openlist['ID'] == adjacentLocations['ID'][index]] #Get location from openlist
        g = currentLocation.G + calcH(currentLocation.ID, adjacentLocations['ID'][index])
        f = g + adjacentLocationInDF.H
        if float(f) < float(adjacentLocationInDF.F):
            openlist = openlist[openlist.ID != currentLocation.ID]
            openlist.loc[len(openlist)] = [adjacentLocations['ID'][index], f, g, adjacentLocationInDF.H, currentLocation.ID]

if (len(openlist)< 1):
    print("No Path")
    break

从已关闭列表中查找路径：

# return the path
pathdf = pd.DataFrame(columns=['name', 'latitude', 'longitude', 'country'])
def getParent(index):

    parentDF = closedlist.loc[closedlist['ID'] == index]
    pathdf.loc[len(pathdf)] = [df['name'][parentDF.ID.values[0]],df['latitude'][parentDF.ID.values[0]],df['longitude'][parentDF.ID.values[0]],df['country'][parentDF.ID.values[0]]]
    if index != startIndex:
        getParent(parentDF.parentID.values[0])

getParent(closedlist['ID'][len(closedlist)-1])

目前，*的这个实现没有找到完整的路径。有什么建议吗？在

编辑： 我尝试过将考虑的邻居数量从4个增加到10个，我得到了一个路径，但不是一个最佳路径：

我们正试图从赫斯勒到利兹。在

^可用节点

原始数据： Link