如何在回溯中撤消?我在使用递归回溯方法时遇到问题
how to make undo in backtracking? I'm having problems with the recursively backtracking method
嗯,我有这张图:
我必须编写一个基于分支定界并使用回溯的代码,它必须显示匹配图形节点的最佳方式。所以在这个例子中,最优解一定是>> [(1,4),(2,3)]
。但是我的算法显示了这个可能的解决方案,它不是最优的>> [(1,2),(3,4)]
。我认为问题可能出在 'Undo' 行,但我不确定...如果有人能帮我解决这个问题,我将不胜感激!
这是我的代码:
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)
我想我开始看到这里的问题了,你的算法只选择一条路径,遇到的第一条路径,它需要检查所有路径并选择最小的,并且通过你的例子选择最小的到下一个节点的所有非步行路径...
这是我的解决方案
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
我使用元组而不是列表,作为一个不可变对象我不会发现奇怪的边框效果,以防万一...
称其为
bestSol = minimun_path(G1.nodes()[0],G1,tuple(),cotaMax,cotaMin)
输出
Best Solution:
(1,4)
(3,2)
嗯,我有这张图:
我必须编写一个基于分支定界并使用回溯的代码,它必须显示匹配图形节点的最佳方式。所以在这个例子中,最优解一定是>> [(1,4),(2,3)]
。但是我的算法显示了这个可能的解决方案,它不是最优的>> [(1,2),(3,4)]
。我认为问题可能出在 'Undo' 行,但我不确定...如果有人能帮我解决这个问题,我将不胜感激!
这是我的代码:
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)
我想我开始看到这里的问题了,你的算法只选择一条路径,遇到的第一条路径,它需要检查所有路径并选择最小的,并且通过你的例子选择最小的到下一个节点的所有非步行路径...
这是我的解决方案
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
我使用元组而不是列表,作为一个不可变对象我不会发现奇怪的边框效果,以防万一...
称其为
bestSol = minimun_path(G1.nodes()[0],G1,tuple(),cotaMax,cotaMin)
输出
Best Solution:
(1,4)
(3,2)