我已经为此工作了几天，但没有成功。基本上，我有一堆排列在二维矩阵中的节点。每个节点都有四个邻居，除了矩阵边和角上的节点分别有 3 个和 2 个邻居。想象一下在一个矩形区域内并排放置一堆方形卡片——该项目实际上是在模拟一种纸牌/棋盘游戏。
每个节点可能会或可能不会连接到它周围的节点。每个节点都有一个函数 (get_connections())，该函数返回它连接到的紧邻节点(因此返回 0 到 4 个节点之间的任何位置)。每个节点还有一个“索引”属性，其中包含它在棋盘矩阵上的位置(例如“1、4”-> 第 1 行，第 4 列)。我想做的是找到给定特定“开始”节点的连接节点的最长非重复路径。
我已经上传了几张图片，应该可以很好地了解我正在尝试做什么:
(来源:necessarygames.com)
(来源:necessarygames.com)
在这两个图像中，突出显示的红色卡片应该是包含最左上角卡片的连接卡片的最长路径。但是，您可以在两张图片中看到路径中应该有几张卡片被遗漏了(第一张图片中的罗马尼亚和马尔多瓦，第二张图片中的希腊和土耳其)
给定起始节点/卡片，这是我目前用于查找最长路径的递归函数:
def get_longest_trip(self, board, processed_connections = list(),
processed_countries = list()):
#Append this country to the processed countries list,
#so we don't re-double over it
processed_countries.append(self)
possible_trips = dict()
if self.get_connections(board):
for i, card in enumerate(self.get_connections(board)):
if card not in processed_countries:
processed_connections.append((self, card))
possible_trips[i] = card.get_longest_trip(board,
processed_connections,
processed_countries)
if possible_trips:
longest_trip = []
for i, trip in possible_trips.iteritems():
trip_length = len(trip)
if trip_length > len(longest_trip):
longest_trip = trip
longest_trip.append(self)
return longest_trip
else:
print
card_list = []
card_list.append(self)
return card_list
else:
#If no connections from start_card, just return the start card
#as the longest trip
card_list = []
card_list.append(board.start_card)
return card_list
这里的问题与 processed_countries 列表有关:如果你看我的第一个截图，你可以看到发生的事情是当乌克兰出现时，它查看了最长路径的两个可能选择(马尔多瓦 - 罗马尼亚, 或土耳其, 保加利亚), 看到他们都是平等的, 并且不加区别地选择了一个。现在，当匈牙利出现时，它无法尝试穿过罗马尼亚(最长的路径实际上是那里)，因为罗马尼亚已被乌克兰添加到 processed_countries 列表中。
非常感谢您对此提供的任何帮助。如果你能找到我的解决方案，递归与否，我很乐意向你捐赠一些 $$。
我已将我的完整源代码(需要 Python 2.6、Pygame 1.9)上传到:
http://www.necessarygames.com/junk/planes_trains.zip
相关代码在src/main.py中，设置好即可运行。
请您参考如下方法:
你确实知道 longest path problem在有循环的图中是 NP-hard？
