我已经为此工作了几天，但没有成功。基本上，我有一堆节点排列在一个二维矩阵中。每个节点都有四个邻居，除了矩阵边和角上的节点，它们分别有 3 个和 2 个邻居。想象一堆方形卡片并排放置在一个矩形区域中——该项目实际上是在模拟一种纸牌/棋盘游戏。
每个节点可能连接也可能不连接到它周围的节点。每个节点都有一个函数 (get_connections())，它返回它所连接的紧邻它的节点（因此返回 0 到 4 个节点之间的任何地方）。每个节点还有一个“索引”属性，包含它在棋盘矩阵上的位置（例如，'1, 4' -> 第 1 行，第 4 列）。我想做的是在给定特定“开始”节点的情况下找到连接节点的最长非重复路径。
我已经上传了几张图片，应该可以很好地了解我正在尝试做的事情：
（来源：必要游戏.com）
（来源：必要游戏.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
这里的问题与 processes_countries 列表有关：如果您查看我的第一个屏幕截图，您会看到发生的情况是，当乌克兰出现时，它查看了最长路径的两种可能选择（马尔多瓦-罗马尼亚，或土耳其，保加利亚），看到他们都是平等的，并不加选择地选择了一个。现在，当匈牙利出现时，它无法尝试通过罗马尼亚（实际上最长的路径），因为罗马尼亚已被乌克兰添加到 processes_countries 列表中。
非常感谢您对此的任何帮助。如果你能找到我的解决方案，递归与否，我很乐意向你捐赠一些 $$。
我已将完整的源代码（需要 Python 2.6、Pygame 1.9）上传到：
http://www.necessarygames.com/junk/planes_trains.zip
相关代码在 src/main.py 中，全部设置为运行。