Breitensuche Art Fehler

Question

In meiner Python-Skript für Breitensuche ich die folgende Fehlermeldung erhalten:

TypeError: 'list' object is not callable

ist der Code:

initialState = sys.argv[2] 
initialState = [i for i in initialState.split(',')] 
goalTest = ['0','1','2','3','4','5','6','7','8'] 

def bfs(initialState, goalTest): 
    q = deque([]) 
    for item in initialState: 
     q.appendleft(item) 
     print q 

    frontier = q 
    explored = set() 

    while not frontier <= len(frontier): 
     state = frontier.pop() 
     print state 
     explored.add(state) 

     if goalTest(state): 
      return state 

     for neighbor in state.neighbors(): 
      if neighbor not in frontier or explored: 
       frontier.append(neighbor) 

    return "FAILURE" 

So ist die Linie wirft if goalTest(state) die TypeError, Warum?

Answer 1

Es gibt durchaus ein paar Probleme mit Ihrem Code:

• , wenn Sie die Staaten zu einem set der besuchten Staaten hinzufügen möchten, haben sie tuple sein, wie list nicht
• don ist hashable‘ t fügen Sie die einzelnen Elemente aus dem Zustand der deque, nur der Staat als Ganzes
• Wenn dies ein BFS sein soll, müssen Sie deque.popleft verwenden, so dass es wie eine FIFO-Warteschlange verhält; unter Verwendung pop haben Sie eine LIFO-Warteschlange oder Stapel, d. h. ein DFS (Tiefe erste Suche)
• while not frontier <= len(frontier) macht keinen Sinn; wahrscheinlich Sie while len(frontier) > 0 oder nur while frontier
• goalTest ist nur ein Referenzzustand, so sollten Sie nur vergleichen: if state == goalTest
• neighbors keine Methode state ist (die nur eine Liste oder Tupel ist), sondern sollte eine Funktion sein, so rufen Sie es wie neighbors(state) anstelle von state.neighbors()
• neighbor not in frontier or explored nicht überprüft, ob neighbor in keiner dieser Listen ist, aber (neighbor not in frontier) or explored; auch, keine Notwendigkeit zu prüfen, ob es in frontier ist, wenn Sie es explored hinzufügen sofort
• statt return "FAILURE", sollten Sie nur return False oder return None

Hier ist eine feste (aber nicht gründlich getestet) Version:

initialState = tuple(initialState.split(',')) 
goalTest = ('0','1','2','3','4','5','6','7','8') 

def bfs(initialState, goalTest): 
    frontier = collections.deque([initialState]) 
    explored = set() 

    while frontier: 
     state = frontier.popleft() 
     print(repr(state), len(frontier), len(explored)) 

     if state == goalTest: 
      return state 

     for neighbor in neighbors(state): 
      if neighbor not in explored: 
       frontier.append(neighbor) 
       explored.add(neighbor) 
    return False 

def neighbors(state): 
    ... 

Implementierung neighbors ist als Übung für den Leser übrig. Wenn dies ist, as you say, ein , dann soll 0 der "leere" Platz im Puzzle sein. Überprüfe einfach, welche der anderen Teile daneben sind (Tipp: Division und Modulo sind deine Freunde) und tausche diese Teile aus und gib dann eine Liste dieser getauschten Zustände zurück.

Beachten Sie auch, dass BFS möglicherweise nicht der beste Algorithmus für dieses Problem ist, da es viel von Staaten gibt, und uninformierte Suche, wie BFS, kann sehr, sehr lange dauern. Bessere informierte Suche, wie z. B. A*, verwenden z. die Anzahl der falsch platzierten Kacheln als Heuristik.