심도 우선 검색 열기/닫기 목록

Question

나는 지금 정말로 당황스럽고 미쳐 가고있다.

가장 간단한 용어로 깊이 우선 검색을 사용하여 열기 및 닫기 목록에서 언제 중지합니까?

노드가 없어 질 때까지 모든 노드를 열고 닫으시겠습니까?

내가 doolally 여기

려고하고 있기 때문에 도와주세요

Answer 1

열기 목록 처음 두 깊이에 도움이와 제대로 트리를 탐색 먼저 검색을 폭 주셔서 감사합니다. 알고리즘을 단계별로 생각해보십시오. 당신은 많은 아이들이있는 노드에 있으며 그 중 하나를 확장하려고합니다. 확장 후에는 돌아와서 탐색을 계속할 수있는 메커니즘이 있어야합니다. 공개 목록은 당신을 위해 그것을 수행하고 실제로 확장 할 다음 노드가 무엇인지 말해줍니다. 그리고 알고리즘은 목록에 자식 삽입 순서 만 명확히합니다.

그리고 닫힌 목록은 일반적으로 알고리즘의 속도를 향상시킵니다. 알고리즘이 사전 방문 노드를 확장하는 것을 방지합니다. 어쩌면 다른 지점을 통해 이전에 확장 된 노드 A에 도달했을 수 있습니다. 그러면이 지점을 잘라 다른 경로를 시도 할 수 있습니다.

휴리스틱 스는 막 다른 방향에서 벗어나는 데 유용합니다. 인공 지능 알고리즘에서는 일반적으로 많은 쓰레기가있는 문제에 직면하고 있습니다. 각 단계를 거치면 경로 비용을 변수에 추가 할 수 있으며 열린 목록에 확장 된 노드를 추가하려는 경우이를 고려하지 않아도됩니다. 그렇지 않으면 트랩에 들어가 알고리즘이 중단됩니다.

예를 들어 더 자세히 설명하겠습니다. 게임을 생각해보십시오. 15-puzzles. 당신은 알고리즘을 통해 그것을 해결할 것이며 가능한 모든 방법을 확인해야합니다. (실제로 당신은 나무를 만들 것입니다). 나무에서 가능한 방향으로 타일을 이동하면 그 방향을 다음 단계의 반대 방향으로 움직일 수 있습니다. 맞습니까? 따라서 막 다른 골목에서 빠져 나올 수 없으며 알고리즘이 중단됩니다.

이것은 열린 목록과 닫힌 목록에 대한 설명입니다. 알고리즘 완료 시점에 대해 물었습니다. 실제로 확장을 반복하고 목표를 찾거나 목록이 비어있을 때까지 공개 목록에 추가합니다.