[🐣질문] A스타 알고리즘에서 막다른 길에 도달했을 때

[익명(60.120)]

이미 지나온 열린 노드를 따라서 다시 에이스타로 돌아간 다음, 이미 한 번 지나온 열린 노드는 닫힌 노드에 넣어버리면 되는 거임?

막다른 길 도달했을 때의 예제나 설명이 없어서 잘 모르겠는데 혹시 알려줄 인붕이 없니ㅠㅠ

- dc official App

[익명(222.117)]

그냥 노드에 isVisible 해놓고 방문했으면 체크하셈.

[익명(118.47)]

나는 딱히 막다른 길은 처리하지 않았고 노드를 탐색할때 좀더 가까울것 같은 노드를 우선순위를 주고 일단 경로가 찾아지면 해당 경로의 길이보다 길어지는 노드는 탐색을 생략하는 방식으로 했었음. 그리고 최단 거리 보다는 적당한 길이의 경로가 탐색되면 중단.(휴리스틱)

[익명(222.117)]

첨부터 Astar 만들지말고 너비우선탐색부터 해봐. 너비우선탐색으로 길찾기 해보고, 거기서 약간만 수정하면됨. 너비우선탐색은 Queue를 쓰고 Astar는 우선순위큐를 쓰면됨. 우선순위 기준은? 예상비용 (휴리스틱)임

[익명(222.117)]

Node StartNode; Node EndNode; NodeQueue.push(StartNode); while( !NodeQueue.empty() ) { Node nowNode = NodeQueue.pop(); if( nowNode.isVisible == true ) continue; for( int i = 0; i < nowNode.nextNode.Lenght; i++ ) { if(nowNode.nextNode[i] == null ) continue; NodeQueue.push(nowNode.nextNode[i]); nowNode.nextNode[i].isVisible = true; } }

[익명(222.117)]

대충 너비우선탐색 수도코드..

[ㅇㅇㅇ(183.182)]

https://www.youtube.com/watch?v=pKnV6ViDpAI
열린 노드니 닫힌 노드니 처음으로 돌아가고 그런거 할 필요없이 자연스럽게 최우선의 열린 노드에서 재탐색을 함

[익명(60.120)]

답변 감사함미다 - dc App