최적의 여행 플래너를 디자인하는 방법

Question

여행용 비행기 프로그램을 개발 중입니다. 각 도시에는 rateOfInterest라는 속성이 있습니다. 두 도시 간의 각 도로에는 시간 비용이 있습니다. 문제는 출발 도시와 지출하려는 특정 시간, 가장 흥미로운 경로 (즉, 도시의 rateOfInterest의 합)를 출력하는 방법을 고려하면 문제입니다. 일부 욕심 많은 알고리즘을 사용하여 생각하고 있지만 최적의 경로를 보장 할 수있는 알고리즘이 있습니까?

EDIT @robotking과 마찬가지로, 우리는 여러 번 방문 장소를 허용하고 첫 방문 만 흥미 롭습니다. 우리는 50 개의 도시를 가지고 있으며, 각 도시에는 약 5 개의 인접한 도시가 있습니다. 각 모서리의 비용 함수는 시간 또는 거리 중 하나입니다. 우리는 모든 도시를 방문 할 필요가 없습니다. 주어진 비용 함수 만 있으면 ROI가 가장 높은 최적의 부분 여행을 반환해야합니다. 문제가 더 명확 해지기를 바랍니다.

Answer 1

지금 당신은 모든 가능한 순열을 시도하는 최적의 경로를 찾을 수 ... 다른 것보다 더 바람직하다 일부 정점이 (사용 되돌아 우리가 이야기하고있는 도시의 수에 따라 더 빨리 처리 할 수있는 가지 치기가 있습니다). TSP 문제는 n! 문제는 n> 10 이후에 잊어 버릴 수 있습니다.

도시 수가 적지 않은 경우 최적의 경로를 찾을 수 없으므로 아이디어를 삭제하십시오.하지만 가장 좋은 방법이 있습니다. 충분한 휴리스틱 알고리즘으로 충분한 솔루션을 근사화하십시오.

스티븐 스키 나 (Steven Skiena)는 이러한 어려운 문제를 근사하기위한 휴리스틱을 "시뮬레이션 어닐링 (Simulated Annealing)"이라고 권장합니다. 그것은 매우 "힐 클라이밍"방식과 비슷하지만보다 유연하거나 용인적인 방식입니다. 내 말은 "암벽 등반"에서 솔루션을 개선하는 변경 사항 만 수락하는 반면 "Simulated Annealing"에서는 해결 방법을 로컬에서 악화 시키더라도 변경 사항을 실제로 수락하는 경우가 있습니다. 돈을 돌려 받으십시오 ...

어느 쪽이든, TSP와 유사한 문제를 근사하는 데 사용되는 것은 무엇이든 여기에 해당됩니다.

Answer 2

http://en.wikipedia.org/wiki/Travelling_salesman_problem에서 결정 문제 버전은 "(길이 L 인 경우 작업이 L보다 짧은 지의 여부를 결정하는 것입니다)"라는 점에 유의하십시오. 누군가가 나에게 여행 세일즈맨 문제를 해결하면 모든 도시가 동일한 이자율을 갖도록 설정할 수 있습니다. 그런 다음 결정 문제는 시간 L에 대한 가장 흥미로운 경로가 실제로 모든 도시와 수익을 방문하는지 여부입니다.

문제에 대한 효율적인 해결책이 있다면 여행 세일즈맨 문제에 대한 효율적인 해결책이 될 것 같지 않습니다.

욕심이 많은 검색보다 더 자세히 살펴 보려면 여행 판매원 문제의 일부 접근 방법을 적용 할 수 있습니다. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.5150은 TSP와 관련하여 흥미로운 "반복 로컬 검색"을 설명합니다.

이 의미 가중 방식으로 TSP의 인스턴스처럼 매우 소리

Answer 3

최적의 결과를 얻으려면 잎이 시간이없는 곳에있는 무차별 한 철저한 검색을 사용하십시오. 검색 트리의 예상 깊이가 10보다 작고 최악의 경우가 15보다 작 으면 실용적인 알고리즘을 생성 할 수 있습니다.

미래에 대해 생각하고 도시 네트워크가 성장할 것으로 예상되면 최적 성을 보장 할 수 없습니다. 이 경우 로컬 검색 문제를 처리하고 있습니다.