修改后的背包问题陷入死循环

Question

我一直在尝试实现关于生物信息学的修改后的背包问题算法。

到目前为止，在我看来，我的解决方案非常接近，但程序卡在了某个点。

我有一个节点列表，其中包含（某种氨基酸的）质量、索引和它们可以到达的节点列表。

节点:

class Node():
def __init__(self, mass, index):
    self.mass = mass
    self.prev = []
    self.next = []
    self.index = index


def chainTo(self, next):
    self.next.append(next)
    next.prev.append(self)

目标是找到给定节点的最长链，这样我就可以从它们的质量中找到它们代表的肽。

为此，我编写了一个函数，它遍历所有节点的列表并将它们相互链接起来，如果 nodes[i].mass - nodes[j].mass 等于 .txt 文件中预定义的一些氨基酸质量。

def createTree(massTable, massDev, aminoTable, extras):
    nodes = createNodes()

    for i in range(0, len(nodes)):
        for j in range(i+1, len(nodes)):
            findAmino(nodes[i], nodes[j], massTable, massDev, aminoTable, extras)

    return nodes

def findAmino(first, second, massTable, massDev, aminoTable, extras):
found = False
for amino, mass in massTable.items():
    for extra, extraMass in extras.items():
        #print(first.mass - second.mass)
        if ((mass + extraMass - massDev) <= abs(first.mass - second.mass) <= (mass + extraMass + massDev)):
            first.chainTo(second) #pravimo vezu
            #print(amino)
            aminoTable.update({(first, second) : amino})
            found = True
            break

return False if not found else True #ako ne nađe niti jednu mogućnost, vraća False

所以代码的最后和主要部分是遵循特定规则的树遍历算法：

从列表中取出第一个节点（如果下一个列表中没有节点，则取第二个，依此类推）
调用树遍历算法找到所有可能的路径（例如，如果节点[0]的下一个列表中有节点[1]和节点[2]，则树遍历算法必须找到路径节点[0]->节点[1]和节点[0]->节点[2]
在所有生成的路径中，程序占用最长的一个
程序重复第 1 步，但它不从列表中获取第一个节点，而是取最长找到路径中最后一个节点之后的节点
当到达最后一个节点时，它结束并且 returns 最长可能链的列表。

def traverseRoot(root, chains):
    traverse(root, [], chains)

#node - čvor na kojem se nalazimo
#ako nema susjede, u chains dodajemo taj put
#ako ima, pokrecemo isti algoritam
def traverse(node, path, chains):
    path.append(node)
    if(len(node.next) == 0):
        chains.append(path)
    else:
        for i in node.next:
            print(str(i.mass) + " " + str(i.index))
            traverse(i, path.copy(), chains)


def start(nodes, massTable, massDev, extras):
        #IDEJA:
        #1. funkcija uzima prvi čvor (ukoliko nema prijelaze, uzima idući, pa idući, itd.)
        #2. nad tim čvorom provodi neku vrstu tree-traversing algoritma kako bi prošao sve puteve
        #3. uzima kao konačni put onaj koji je došao najdalje u listi / pokrio najviše čvorova
        #4. ponavlja sve počevši od prvog koraka samo što ne uzima prvi čvor nego onaj koji dolazi nakon zadnjeg u prethodno pronađenom putu
        #5. kad dođe do zadnjeg čvora, prestaje sa radom i vraća listu stvorenih lanaca po čijim čemo vezama gledati koje aminokiseline predstavljaju
        start = 0
        finalChains = []
        while(True):
            currentNodeChains = []
            found = False
            for i in range(start, len(nodes)):
                if(not nodes[i].next): #1.
                    continue
                else:
                    found = True
                    print(start)
                    traverseRoot(nodes[i], currentNodeChains) #2.
                    break
            
            if (not found):
                return finalChains
                
            #3.
            maxLen = 0
            maxChain = None
            for chain in currentNodeChains:
                if (len(chain) > maxLen):
                    maxLen = len(chain)
                    maxChain = chain
            if (maxChain != None):
                finalChains.append(maxChain)
                print([i for i in maxChain])
                print("-----------")
                start = maxChain[-1].index + 1 #4.
        return finalChains

我的整个问题是程序卡在某个点。

例如，我有 300 个节点，它在接近尾声的某个地方陷入无限循环，在我运行它所在的示例中大约第 280 个节点。

我怀疑它是否与我运行这个特定示例有关，但更可能的是递归函数调用中某处存在逻辑错误。

如果有人知道问题出在哪里，我将不胜感激！

Answer 1

在尝试调试代码时，问题似乎出在 Node next next 属性的整个概念中 class.

当我打印出所有节点的下一个列表时，我发现同一个节点多次出现，例如 [2,2,2,3,8,...] 所以当我转换 list to set不再卡了

希望这对以后的人有所帮助。

修改后的背包问题陷入死循环

Modified knapsack problem gets stuck in infinite loop

tree

traversal

bioinformatics

knapsack-problem