查找连接节点中的最长不重复路径

Question

我这几天一直在研究这个问题，但还没找到解决办法。简单来说，我有一堆节点排成一个二维矩阵。每个节点周围有四个邻居，除了边缘和角落的节点，它们分别只有三个和两个邻居。可以想象成一堆方形卡片并排放在一个矩形区域里——这个项目实际上是在模拟一种卡片/棋盘游戏。

每个节点可能与周围的节点连接，也可能不连接。每个节点都有一个函数（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 中，已经设置好可以运行。

Answer 1

暴力破解方法：

1. 首先，创建一个深度优先的连接列表。把这个列表叫做L，并记录它的长度T。

2. 对于这个列表中的每一个连接：

   • 把整个图形推入栈中。
   • 删除这个连接。
   • 再创建一个深度优先的连接列表。
   • 如果这个新列表的长度比T长，就把T更新为这个新列表的长度，并把这个新列表赋值给L，然后回到第2步。
   • 把整个图形从栈中弹出。
   • 返回。

这样做应该能找到所有可能的连接方式，类似于填充的效果。

Answer 2

你知道吗？在有循环的图中，寻找最长路径的问题是非常困难的，属于NP难题。

Answer 3

……乌克兰已经把罗马尼亚加入到处理过的国家列表中。

每个图表路径都应该使用单独的处理过的国家列表。他们说一个代码示例胜过千言万语，所以我稍微修改了一下你的代码（未经测试）：

def get_longest_trip(self, board, processed_countries = list()):
    # see https://stackoverflow.com/questions/576988/python-specific-antipatterns-and-bad-practices/577198#577198
    processed_countries = list(processed_countries)
    processed_countries.append(self)

    longest_trip = list()
    if self.get_connections(board):
        possible_trips = list()
        for card in self.get_connections(board):
            if card not in processed_countries:
                possible_trips.append(card.get_longest_trip(board, 
                                                            processed_countries))
        if possible_trips:
            longest_trip = max(possible_trips, key=len)
            longest_trip.append(self)

    if not longest_trip:
        longest_trip.append(self)
    return longest_trip

无关的事情：

Traceback (most recent call last):
  File "main.py", line 1171, in <module>
    main()
  File "main.py", line 1162, in main
    interface = Interface(continent, screen, ev_manager)    
  File "main.py", line 72, in __init__
    self.deck = Deck(ev_manager, continent)
  File "main.py", line 125, in __init__
    self.rebuild(continent)  
  File "main.py", line 148, in rebuild
    self.stack.append(CountryCard(country, self.ev_manager))
  File "main.py", line 1093, in __init__
    Card.__init__(self, COUNTRY, country.name, country.image, country.color, ev_manager)  
  File "main.py", line 693, in __init__
    self.set_text(text)
  File "main.py", line 721, in set_text
    self.rendered_text = self.render_text_rec(text)  
  File "main.py", line 817, in render_text_rec
    return render_textrect(text, self.font, text_rect, self.text_color, self.text_bgcolor, 1)       
  File "/home/vasi/Desktop/Planes and Trains/src/textrect.py", line 47, in render_textrect
    raise TextRectException, "The word " + word + " is too long to fit in the rect passed."
textrect.TextRectException: The word Montenegro is too long to fit in the rect passed.

你的源代码包里有16个不同的 bak 文件。十六。十六个。想想这个问题，开始使用 版本控制吧。