BFS 그래프 검색에서 너무 많은 노드가 확장되었습니다.

Question

AI 과정의 문제를 해결하고 Python에서 BFS 알고리즘을 사용하여 그래프 검색을 구현해야합니다. 내 구현 실제로 솔루션을 찾으십시오,하지만 너무 많은 노드를 확장합니다. 대답은 269 개의 ​​노드가 확장되어야한다고 말합니다. 그러나 275를 얻었습니다.

나는 사전을 사용하여 방문한 노드를 추적합니다. 키는 확장 상태이고 값은 1입니다. 노드의 후계 노드를 얻으면 사전에 해당 노드가 있는지 확인합니다. 그렇다면이 후임을 무시합니다. 그렇지 않다면 나는 그것을 프린지 (큐)에 밀어 넣는다. 이 프로세스는 이미 방문한 노드를 확장하는 것을 방지 할 것이라고 생각했지만 실제로는 그렇지 않습니다.

누구든지 내게이 힌트를 줄 수 있습니까? 아무 것도 잘못 될지도 모른다는 아이디어가 필요하기 때문에 코드가 필요하지 않습니다.

미리 감사드립니다.

Answer 1

계속 진행할 정보는 많지 않지만 다음 사항이 문제가 아닌 것으로 판단됩니다. 프린지 큐에 노드가 추가되면 바로 방문한 사전에 노드를 추가해야합니다. 방문 할 때까지 기다리면 (예 : 프린지 큐에 도달했을 때) 프린지 큐에 같은 노드가 두 번있을 수 있습니다.

또한 방문한 사전에 시작 노드를 추가하는 것을 잊지 마십시오.