帮助通过连接节点找到最长的非重复路径 - Python

Question

我已经在这几天工作但现在没有成功.基本上,我有一堆以2D矩阵排列的节点.每个节点有四个邻居,除了矩阵的边和角上的节点,它们分别有3个和2个邻居.想象一下,在一个矩形区域中并排放置了一堆方形卡片 - 该项目实际上模拟了一种卡片/棋盘游戏.

每个节点可以连接或不连接到它周围的节点.每个节点都有一个函数(get_connections()),它返回它所连接的节点周围的节点(因此返回0到4个节点的任何地方).每个节点还有一个"索引"属性,它包含它在板矩阵上的位置(例如'1,4' - >第1行,第4列).我想要做的是在给定特定"开始"节点的情况下找到连接节点的最长非重复路径.

我上传了几张图片,可以很好地了解我要做的事情:

www.necessarygames.com/junk/10-days-problem-01.jpg http://www.necessarygames.com/junk/10-days-problem-01.jpg

www.necessarygames.com/junk/10-days-problem-02.jpg http://www.necessarygames.com/junk/10-days-problem-02.jpg

在两张图像中,突出显示的红色卡片被认为是包含最左上方卡片的连接卡片的最长路径.但是,您可以在两张图片中看到应该在路径中留下的几张卡片(第一张图片中是罗马尼亚和马尔代夫,第二张图片中是希腊和土耳其)

这是我目前用于查找最长路径的递归函数,给定起始节点/卡:

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列表有关:如果你查看我的第一个截图,你可以看到发生的事情是,当乌克兰出现时,它看了两个可能的最长路径选择(马尔多瓦 - 罗马尼亚,或土耳其) ,保加利亚),看到他们都是平等的,并且不分青红皂白地选择了一个.现在,当匈牙利出现时,它不能试图通过罗马尼亚(最长的路径实际上是这条路径),因为罗马尼亚已经被加入了乌克兰的加工国家名单.

对此有任何帮助非常感谢.如果你能找到我的解决方案,无论是递归与否,我都乐意为你捐赠一些$$.

我已将我的完整源代码(Python 2.6,需要Pygame 1.9)上传到:

http://www.necessarygames.com/junk/planes_trains.zip

相关代码位于src/main.py中,该代码全部设置为运行.

Answer 1

你知道循环图中最长的路径问题是NP难吗？