何時使用深度優先搜索

Question

所以我想排序一系列數字，以便每個連續數字的總和爲平方數（4,9,16,25，...）我被告知應該使用深度首次搜索，但無法正確實現，特別是回溯部分。這是做到這一點的正確方法，我沒有看到什麼，做錯了什麼？ DFS甚至是正確的方法嗎？

class Node:       #Define node Object 
    def __init__(self, value): 
     self.value = value   #Node "Name" 
     self.adjacentNodes=list() #Node Neighbours 

#Set limit 
limit=16 
squares=list() #list for squared numbers in rang smaller than 2Xlimit 
tree=list() #Tree containing nodes 
path=list() #current path taken 

def calculate(limit): #Population control legal squares 
    for i in range(1,(limit+1)): 
     i=i*i 
     if i<(limit+limit): 
      squares.append(i) 

calculate(limit) #Populate squares list 

for a in range(1,(limit+1)): #creating the nodes 
    newnode=Node(a) 
    for s in squares: 
     legalsum=s-a 
     if legalsum>0 and legalsum<limit and legalsum!=a: #zero and lower can't play,keeping non-exiting nodes out of node.adjacentNodes, don't connect to selve. 
      newnode.adjacentNodes.append(legalsum) #Add adjacentnode 
    tree.append(newnode) #add newborn to tree 

for b in range(0,limit): 
    print tree[b].value,tree[b].adjacentNodes #Quick checkup 
#Now the tree is build and can be used to search for paths. 
''' 
Take a node and check adjnodes 
is it already visited? check path 
yes-> are all nodes visited (loop over tree(currentnode).adjnodes) Maybe use len() 
     yes->pop last node from path and take other node -> fear for infinte loops, do I need a current node discard pile? 
     no -> visit next available adje node next in line from loop got from len(tree.adjn) 
no-> take this as node and check adj nodes. 

''' 
def dfs (node): 
    path.append(node) 
    #load/check adjacent nodes 
    tree[node].adjacentNodes 
    for adjnode in tree[node-1].adjacentNodes: 
     if adjnode in path: 
      #skip to next adj node 
      continue 


     else: 
      print path #Quick checkup 
      dfs(adjnode) 
dfs(8) # start with 8 since 1-16 should be {8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,16} 

Answer 1

我不知道你說的是帶有方塊什麼，但這裏有一些問題

def dfs (node): 
    #always assume the path starts with this node 
    path=[node] 
    if node == GoalState: return path #we win!! 
    #load/check adjacent nodes 
    #this line did nothing `tree[node].adjacentNodes` 
    for adjnode in tree[node-1].adjacentNodes: 
    # if adjnode in path: ****this will never be true, lets eliminate it 
    #   #skip to next adj node 
    #  continue 

    # else: 
      subpath = dfs(adjnode) 
      if subpath and subpath.endswith(GoalState): 
       return path + subpath #return solution 

    #if we get here there is no solution from this node to the goal state