如何撤消回溯？我在用遞歸追蹤方法

Question

好問題，我有這個圖：

我必須讓總部設在分支限界，並使用回溯代碼，是要顯示的最佳途徑，以配合圖的節點。所以在這個例子中，最佳解決方案必須是>> [(1,4),(2,3)]。但是我的算法顯示了這種可能的解決方案，這不是最佳的>> [(1,2),(3,4)]。我認爲這個問題可能是在'撤銷'路線上，但我不確定......如果有人能幫我解決這個問題，我會非常感激！

這裏是我的代碼：

import networkx as nx 
import sys 
import matplotlib.pyplot as plt 
import copy 
import operator 
from itertools import izip 

def grouped(iterable, n): 
    "s -> (s0,s1,s2,...sn-1), (sn,sn+1,sn+2,...s2n-1), (s2n,s2n+1,s2n+2,...s3n-1), ..." 
    return izip(*[iter(iterable)]*n) 

''' Method to create a Graf from a file ''' 
def leerGrafo():                             
    #name = raw_input("Enter the name of the Graph please: ") 
    name = "grafo2.dat"                   
    G = nx.read_edgelist(name,nodetype=int,data=(('weight',float),)) 
    return G  

''' Method to create the adjacency matrix ''' 
def matrixAdj(G): 
    ''' Tener en cuenta: diagonal = 0, y no conex. = Inf ''' 
    nodes = G.number_of_nodes() 
    edges = G.edges() 

    listaAdj = [[float("Inf") for j in range(nodes)] for i in range(nodes)] 

    for i in range(len(edges)): 
     valor1,valor2 = edges[i][0],edges[i][1] 
     listaAdj[valor1-1][valor2-1] = G.edge[valor1][valor2]['weight'] 
     listaAdj[valor2-1][valor1-1] = G.edge[valor1][valor2]['weight'] 

    return listaAdj 

''' returns the weight from the adjacency matrix ''' 
def weight_of(s,G,son): 
    return matrix[s-1][int(son)-1] 

''' Backtracking Method ''' 
def backtracking(s,G,l,cMax,cMin,finalSol): 
    # We insert the current valid node, from our current way 
    l.append(s) 
    # We iterate over the sons of our current node 
    for son in G.neighbors(s): 
     # If the current son is not one of the predecessors of the current node 's'... 
     if not son in l: 
      # We calculate the bound of the current son, adding the weight of his father (s) + the weight of the current son 
      # Note: At the start (the first node), we add the lower bound + the weight of that node. 
      c = weight_of(son,G,s) + cMin 
      # If this bound is lesser or iqual than the upper bound... 
      if c <= cMax: 
       # If this current node is a leaf, means that we've found a possible way... 
       if len(l)+1 == G.number_of_nodes(): 
        # We insert this current node (son) 
        l.append(son) 
        # We update the upper bound with the bound of this current node 
        cMax = c 
        # We store a copy of our possible way 
        finalSol = copy.copy(l) 
        # We reset our list that conteins our possible way 
        l = [] 
        return finalSol 
       # Si no...seguimos recorriendo las ramas hasta encontrar un camino entero 
       else: 
        backtracking(son,G,l,cMax,c,finalSol) 
    # Undo 
    del l[-1] 

    return 

''' Main Function ''' 
def main(): 
    # We make the graf 
    G1 = leerGrafo() 
    global matrix 
    # We create the adjacency matrix 
    matrix = matrixAdj(G1) 
    # We make a ordered list that contains just the weight of all nodes 
    pesos = [a[2]['weight'] for a in sorted(G1.edges(data=True), key=lambda aux: aux[2])] 
    # We calculate the default upper bound 
    cotaMax = sum(pesos) 
    # We calculate the lower bound 
    cotaMin = pesos[0] 
    l = [] 
    global finalSol 
    finalSol = 0 
    # We call the backtracking method 
    bestSol = backtracking(G1.nodes()[0],G1,l,cotaMax,cotaMin,finalSol) 
    # We print the solution 
    print "Best Solution: " 
    for x, y in grouped(bestSol, 2): 
     print "(%d,%d)" % (x, y) 

Answer 1

我想我開始看到這裏的問題，你的算法只能選擇一個路徑，即相遇，它需要檢查所有的路徑，並選擇最小的第一路徑一個和你的榜樣所選擇的所有非走路徑的下一個節點分鐘...

這裏我的解決方案

def minimun_path(s,G,camino,cMax,cMin): 
    if len(camino) == G.number_of_nodes(): 
     # I found the complete path 
     return camino 
    temp = [] 
    for son in G.neighbors(s): 
     # I record all path to a node not visited yet 
     if son not in camino: 
      peso = weight_of(son,G,s)+cMin 
      temp.append((son,peso)) 
    if temp: 
     # I choose a minimun of those 
     sig,w = min(temp, key=lambda x:x[1]) 
    else: 
     # I don't have where to go, so I stay put 
     sig = s 
    return minimun_path(sig,G,camino+(s,),cMax,cMin) 

對於camino I U SE元組而不是列表，作爲inmutable對象，我不會發現怪異的邊框效果，以防萬一......

稱其爲

bestSol = minimun_path(G1.nodes()[0],G1,tuple(),cotaMax,cotaMin) 

輸出

Best Solution: 
(1,4) 
(3,2)