A *를 사용하여 가장 높은 게인을 가진 경로를 찾는 방법

Question

A *의 로직을 변경하여 최단 경로를 찾는 대신 가장 유용한 경로 (즉, 가장 높은 게인을 가진 경로)를 찾으려고한다고 가정합니다 경로 (즉, 비용이 가장 낮은 경로).

필자의 경우 목표는 고유 한 끝 노드로 고정되지 않습니다. 노드는 시작점으로부터 거리가 B 인 노드로 정의됩니다.

바닐라 버전 ("최단 경로 찾기")에서 비용을 과대 평가하지 말아야합니다 (즉, 실제 비용보다 작거나 같은 경험적 발견 방법을 찾아야합니다). 대신 내 수정 된 버전에서

("가장 유용한 경로를 찾는"), 가장자리가 의 최대 겪고의 제약 주어진 유틸리티가 아닌 비용으로 태그, 그리고 최종 이득을 극대화하려는 B 가장자리. A * 작업을하기 위해 유틸리티를 과대 평가해야합니까 (즉, 실제 유틸리티보다 크거나 같은 경험적 발견 방법)?

편집 :

• g(n) : 더 공식화,

  f(n) = g(n) + h(n) 
  

  에 의해 구성된 노드의 유틸리티하자 n

에 시작 노드에서 갈 때 내가 얻을 무엇을
• h(n) : 경험적으로, n에서 목표로 갈 때 얻을 수있는 것의 예상치 그 거리의 시작 지점으로부터 노드는이야 B) h(n) 과대 평가되어야하며 f(n)가 가장 좋은 경로를 식별하기 위해 극대화 할

?

B은 예산이므로 완전히 완료 할 수 있습니다. 즉, B 단계보다 짧은 경로를 찾을 필요는 없습니다.

Answer 1

귀하의 문제는 강하게 NP-하드인 longest path problem입니다. 이뿐만 아니라이 있다는 것을 의미 (거의 확실) 더 빠른 정확한 알고리즘뿐만 아니라 (거의 확실) 없다 더 좋은 대략 알고리즘입니다.

당신은 불행하게도 @Charles 알 수 있듯이 등 에지 가중치의 부호를 부정하기

---

, 유전 프로그래밍, 그것 - 무력, 또는 어닐링과 같은 다양한 global optimization 기술에 의존해야 할 것 중 하나, A *는 부 가중치를 처리 할 수 ​​없으므로 작동하지 않습니다. 그리고 other algorithms 어느 수 네거티브 에지 가중치를 처리 여전히 부정적인 사이클을 처리 할 수 ​​없습니다.