A * 알고리즘은 부 가중치에서 작동합니까?

A *가 최적 일 때 A * 트리 검색에 사용 된 경험적 추론이 왜 받아 들여질 필요가 있는지 알아 내려고했습니다. 트리 검색이란 알고리즘에 의해 관리되는 탐색 세트가 없음을 의미합니다.A * 알고리즘은 부 가중치에서 작동합니까?

이렇게하는 동안, 나는 부정적인 가장자리 가중치에 대해 A *가 작동합니까?

는 A * 알고리즘은 기본적으로 휴리스틱과 Dijkstra’s algorithm입니다. 그리고 Dijkstra의 알고리즘은 음의 에지 가중치에서는 작동하지 않습니다. 따라서 A *는 부 가중치로 작동하지 않습니다.

네거티브 에지 가중치로 작동하는 알고리즘을 찾으려면 the Bellman-Ford algorithm을 살펴보십시오 (그러나 휴리스틱을 사용하지는 않습니다).

2011-02-24 18:43:06 Gumbo

doea 음수 사이클이 없으면 음의 모서리를 사용합니까? – TimeToCodeTheRoad

@TimeToCodeTheRoad : 아니요. – Gumbo

다 익스트라가 도움이 될 음의 가장자리에 대해 좋은 예를 제공 할 수 있습니다에 대한이 우수한 기사 ...

2011-02-24 18:21:48 Orbit

Dijkstra의 알고리즘은 음의 에지 가중치에서는 작동하지 않습니다. – Gumbo

Gumbo 요약 정보 주셔서 감사합니다. – Orbit

답변