Python: 使用包含经纬度的数据框进行A*路径规划

Question

我有一个包含3万条记录的数据框，格式如下：

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

我希望选择一条记录作为起点，另一条记录作为终点，并返回最短路径的路径（列表）。

我正在使用Geopy查找点之间的距离（以千米为单位）。

import geopy.distance

coords_1 = (52.2296756, 21.0122287)
coords_2 = (52.406374, 16.9251681)

print (geopy.distance.vincenty(coords_1, coords_2).km)

我已经阅读了以下教程，学习了如何在Python中使用A*算法： 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])

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

编辑： 我已经尝试将考虑的邻居数量从4增加到10，我得到了一条路径，但不是最优路径。

我们正在尝试从Hessle到Leeds的路上。 ^ 可用节点

原始数据： 链接

- brian4342

---

不确定这是否是问题所在，但如果您只将最近的其他4个点视为邻居，则很可能从起点到终点没有路径。 - tobias_k

算法将选择Ipswich节点作为起点，然后搜索其他30,000个节点以识别4个最近的节点，并将它们设置为邻居并放入开放列表中。然后对于开放列表中的每个节点，它将搜索30,000个节点以找到4个最近的节点。并且它“应该”重复此过程直到找到终点。我可以尝试将其更改为10个最近的邻居，看看是否有任何影响。挑战在于反复搜索30,000个节点所需的时间。 - brian4342

你能否将所有可用的点添加到显示路径的图片中？这可能有助于理解为什么A*算法选择了一些奇怪的绕路，并且如何修复它。 - tobias_k

我无法在这里画出方向线。但它是从Hessle到Leeds的。第一步应该是从Hessle到Ferriby。 - brian4342

哦， values 的结果是一个二维的 numpy 矩阵，检查 <int> in ...values 将返回 true，即使 int 不是索引，而是矩阵中的任何其他 int（在这种情况下，它是父节点的索引）。你能试着将这些检查更改为 adjacentLocations['ID'][index] in openlist['ID'].values 吗？ - tobias_k

Answer 1

虽然评论中已经提到了一些问题，但我仍然不确定你的方法有何问题。

• 仅考虑最近的四个（或任何固定数量的）邻居可能会导致死路或图的某些部分完全被切断，例如孤立的城市不在任何邻居的“最近X”内
• 你的检查形式为x in dataframe.values将检查x是否是由values返回的numpy数组中的任何值，而不一定是ID字段
• 使用数据框而不是适当的堆作为开放列表和哈希集作为关闭列表使搜索变得不必要地缓慢，因为您必须一直搜索和排序整个列表（不确定Pandas是否可以通过索引加快查找，但排序肯定需要时间）

无论如何，我发现这是一个有趣的问题，并尝试解决它。结果，使用数据框作为某种伪堆确实非常缓慢，而且我发现数据框索引非常令人困惑（可能容易出错？），因此我将代码更改为使用namedtuple作为数据和适当的heapq堆作为openlist，以及将节点映射到其父节点的dict用于closedlist。此外，与您的代码相比，检查较少（例如，一个节点是否已在openlist中），而这些并不重要。

import csv, geopy.distance, collections, heapq

Location = collections.namedtuple("Location", "ID name latitude longitude country".split())
data = {}
with open("stations.csv") as f:
    r = csv.DictReader(f)
    for d in r:
        i, n, x, y, c = int(d["id"]), d["name"], d["latitude"], d["longitude"], d["country"]
        if c == "GB":
            data[i] = Location(i,n,x,y,c)

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

def getneighbors(startlocation, n=10):
    return sorted(data.values(), key=lambda x: calcH(startlocation, x.ID))[1:n+1]

def getParent(closedlist, index):
    path = []
    while index is not None:
        path.append(index)
        index = closedlist.get(index, None)
    return [data[i] for i in path[::-1]]


startIndex = 25479 # Hessle
endIndex = 8262 # Leeds

Node = collections.namedtuple("Node", "ID F G H parentID".split())

h = calcH(startIndex, endIndex)
openlist = [(h, Node(startIndex, h, 0, h, None))] # heap
closedlist = {} # map visited nodes to parent

while len(openlist) >= 1:
    _, currentLocation = heapq.heappop(openlist)
    print(currentLocation)

    if currentLocation.ID in closedlist:
        continue
    closedlist[currentLocation.ID] = currentLocation.parentID

    if currentLocation.ID == endIndex:
        print("Complete")
        for p in getParent(closedlist, currentLocation.ID):
            print(p)
        break

    for other in getneighbors(currentLocation.ID):
        g = currentLocation.G + calcH(currentLocation.ID, other.ID)
        h = calcH(other.ID, endIndex)
        f = g + h
        heapq.heappush(openlist, (f, Node(other.ID, f, g, h, currentLocation.ID)))

这给我从Hessle到Leeds的路径，似乎更合理：

Location(ID=25479, name='Hessle', latitude='53.717567', longitude='-0.442169', country='GB')
Location(ID=8166, name='Brough', latitude='53.726452', longitude='-0.578255', country='GB')
Location(ID=25208, name='Eastrington', latitude='53.75481', longitude='-0.786612', country='GB')
Location(ID=25525, name='Howden', latitude='53.764526', longitude='-0.86068', country='GB')
Location(ID=7780, name='Selby', latitude='53.78336', longitude='-1.06355', country='GB')
Location(ID=26157, name='Sherburn-In-Elmet', latitude='53.797142', longitude='-1.23176', country='GB')
Location(ID=25308, name='Garforth Station', latitude='53.796211', longitude='-1.382083', country='GB')
Location(ID=8262, name='Leeds', latitude='53.795158', longitude='-1.549089', country='GB')

即使您不能使用这个，因为您必须使用Pandas(?), 但是也许这可以帮助您最终找到实际错误。

- tobias_k

---

这个问题已经解决了，谢谢。在开始之前我不知道heapq以及如何将其与字典映射。但是这个方法有效，并且即使在整个数据集（不仅仅是英国）上也不会太慢。 我必须等待16小时才能给你赏金，但再次感谢 :) - brian4342