Hoppa till huvudinnehåll

Min DFS-implementering

Nedan visar jag min lösning för Depth-First Search (DFS) i Berkeley Pacman-projektet.
Det är viktigt att poängtera att din lösning absolut inte behöver se exakt likadan ut som min för att fungera korrekt. DFS kan också implementeras rekursivt, vilket är ett annat vanligt och elegant sätt att lösa problemet på.

Huvudsaken är att du förstår principerna bakom DFS och kan använda en lämplig datastruktur (som stack eller rekursion) för att utforska sökträdet.

Jag önskar dig stort lycka till med din implementation och hoppas att Pac-Man hittar vägen till målet utan problem! 🚀

def depth_first_search(problem):

    stack = util.Stack()
    visited = set()
    start_state = problem.get_start_state()
    stack.push((start_state, []))
    while not stack.is_empty():
        state, actions = stack.pop()
        
        if state not in visited:
            visited.add(state)
            if problem.is_goal_state(state):
                return actions
            for successor, action, _ in problem.get_successors(state):
                if successor not in visited:
                    stack.push((successor, actions + [action]))


Förklaring till DFS-koden​

  • Skapar en stack för att hålla tillstånd som ska utforskas, tillsammans med sökvägen dit.
  • Håller koll på besökta tillstånd med en mängd för att undvika cykler och onödig repetition.
  • Loopar tills stacken är tom eller målet hittas.
  • När ett nytt tillstånd tas ut från stacken kontrolleras om det är målet.
  • Om inte, läggs dess efterföljare i stacken om de inte redan besökts.
  • Returnerar sökvägen till målet när den hittas, annars en tom lista.

Avslutning

Jag hoppas att du har lärt dig något värdefullt om Depth-First Search och hur du kan implementera det i Pacman-projektet.

Vill du fördjupa dig mer i sökalgoritmer och andra AI-koncept kan du ta en titt på genomgångarna och materialet på Berkeley AI-projektets sida.