좋은 작품 A *를 작성했습니다. 두 노드 사이의 최단 경로를 제공합니다. 그러나 두 가지 또는 세 가지 경로가 필요합니다. 최상의 두 번째 및 세 번째 경로 (사용할 수있는 경로가 두 개 이상있는 경우). Google지도에서 두 도시간에 여러 옵션을 볼 수있는 길 찾기와 같습니다.A *에서 하나 이상의 경로?
A *로 가능합니까? 아니면 최상의 결과 만 얻었습니까? 가능하면 올바른 방향으로 나를 가리 키십시오. A *에서 가능하지 않다면 어떤 알고리즘을 사용해야합니까?
내 구현은 위키 피 디아 (http://en.wikipedia.org/wiki/A * _search_algorithm # Pseudocode)의 의사 코드에서 가져온 것으로 VB .NET으로 작성되었습니다. 그게 중요하다면.
감사합니다.
정확한 두 번째 최단 경로를 얻으려면 this과 같은 것이 필요합니다.
당신은 정밀 그런 종류의 걱정하지 않는 경우에, 당신은 최단 경로로 난수의 비트 소개 할 수
A * 검색을 수행 할 때 우선 순위 큐 상태가 변경됩니다. 작업을 마칠 때 가장 가까운 꼭지점을 가장 가까운 곳에 놓습니다. 이미 다른 꼭지점이 이미 마무리되어 있습니다. 대기열에서 이들을 들여다보고 "다른 최상의 경로"를 얻을 수도 있습니다.
그러나 다른 결과를 얻을 수 있습니다. 경로가 마지막 가장자리에서만 서로 다를 수 있습니다. 이렇게 : ------- < => 완료. 비슷한 길이의 또 다른 경로가 있다면 그 경로를 찾을 수 있습니다.
다른 측정 항목을 동시에 사용하기 때문에 Google에서 여러 경로를 제공한다고 생각합니다. 메트릭은 다른 결과를 제공하고 다른 매개 변수를 사용하여 경로 최적화 문제를 해결합니다.
감사합니다.이 답변도 도움이되었습니다. – Ragowit
동일한 그래프를 사용하지만 다른 가중치를 사용하여 A * 알고리즘을 다시 계산합니다. 가장 빠른 여행을위한 각 호의 가중치는 아크의 길이를 따라 이동하는 예상 속도로 나눈 호를 통과하는 데 걸리는 시간이어야합니다.
예상되는 속도가 아닌 거리 만 사용하여 새 가중치 집합을 만들 수 있습니다 (모든 호에 동일한 속도를 지정하는 것이 더 편리합니다). 그것은 가장 빠른 길이 아니라 가장 짧은 길을 줄 것입니다.
그런 다음 가장 짧은 항목과 가장 빠른 항목 간의 절충안을 만들 수 있습니다. 이제 세 가지 경로가 가능합니다.
다른 옵션 :
(I) 시작과 끝의 접합을 설명하기 위해 모든 아크에 무게를 추가; 턴을 최소화하는 경로를 만들 수 있도록이 무게로 땜장이. 매우 날카로운 전환을 위해 추가 가중치를 추가하거나 교통 흐름 (영국, 호주, 인도 등에서 우회전, 미국, 프랑스 등에서 좌회전)에 대한 추가 가중치를 추가 할 수 있습니다.
(ii) 고속도로/고속도로가 매우 높은 가격으로 설정되어 고속도로/고속도로를 피할 수있는 경로를 만듭니다.
(iii) 하루 중 시간대 또는 실제 온라인 정보를 사용하여 트래픽 흐름을 추정하고이를 기반으로 가중치를 수정하십시오.
고맙습니다. 이것은 좋은 방향으로 나를 지적했습니다.이 최단 경로를 사용하여이 경로의 각 노드/도시에 대해 다시 한 번 현재 노드/도시를 다시 계산합니다. 나는 새로운 길로 끝났다. – Ragowit