버스 경로 만들기

Question

버스 경로를 만드는 데 사용할 수있는 좋은 알고리즘 또는 알고리즘 클래스 란 무엇입니까?

나는 Traveling Salesman 또는 해밀턴 경로 문제를 해결하는 데 사용되는 알고리즘의 라인을 따라 생각하고 있었지만 실제로는 두 정류장 사이를 이동하는 방법에 대한 문제를 해결하지 못했습니다.

나는 다음과 같은 특징이 적어도 가지고 알고리즘을 싶습니다

:

• 는 상대적으로 최적화 된 경로 생성
• 는 수 (나는 문제가 아마 NP 완전하다는 것을 이해하고, 그래서 좋은 발견 괜찮습니다) 다른 가중치를 가진 경로의 부분을 처리하십시오 (예 : 경로의 해당 부분을 통과하는 시간)
• 주어진 시작점과 끝점을 강제로 사용할 수 있습니다 (이 문제가 발생할 것으로 생각하지 않습니다)

이렇게 할 수있는 코드 또는 이와 비슷한 코드는 (특히 C#에서는) 높이 평가할 수 있지만, 그 자체로 좋은 알고리즘만으로도 좋습니다.

참고 : 두 점 사이의 최단 경로를 찾을 수있는 많은 알고리즘이 있지만 멈추려는 순서를 알지 못합니다. 따라서 두 알고리즘 (내가 의심 스럽다)의 조합을 사용하지 않으면 이러한 알고리즘은 내가 원하는 것을하지 못한다.

편집 : 내가해야 할 모든 정류장을 알고 있다고 가정합니다. http://en.wikipedia.org/wiki/Dijkstras_algorithm이

가장자리를 따라 여행 비용은 단지 거리 아니라, "다음"버스가 지정된 노드에서 출발 할 때까지 또한 시간과 관련된 :

Answer 1

이 작업을 수행하는 방법은 Floyd-Warshall 알고리즘을 사용하고 여행 판매원 문제를 해결하는 데 사용되는 알고리즘을 사용하는 것 같습니다.

이것은 "선택적인"모든 정점 (교차점)의 문제를 해결하고 여행 판매원 알고리즘을 사용하여 정거장이 닿는 순서를 결정합니다.

Answer 2

나는 Djikstra의 알고리즘을 사용했습니다. 참고 : 버스에서 노드에서 멈 추면 이미 버스에있을 수 있습니다.

Answer 3

아마도 포인트 2 (다른 가중치를 갖는 경로의 일부)를 주소 지정하기 위해 여기에 작은 수정/가정으로 여행 판매원 알고리즘을 사용할 수 있습니다.

는 "

심지어는 단일 경로 불구하고, 우리가 가정하여 문제를 단순화 할 수 있습니다 (시간의 어느 시점에서, 말 트래픽)이 개 가중치를 갖고"A "는"B "를 포인트 지점에서 경로를 말할 수 있습니다 가상 꼭지점 "은"A "와"B "사이에있는"C "를 가리키며 각 가장자리에 고정 가중치가 있습니다.

------- 중량 = 10 ------ ------ C는 새로운 그래프 중량 = 15 ------ B

, 주행을 실행할 세일즈맨 알고리즘.

Answer 4

버스 경로는 컴퓨터가 아닌 사람이 만듭니다. 사람들 만이 어디서 얼마나 자주 여행해야 하는지를 알고 있습니다. 사람들의 요구에 가장 적합한 경로 집합을 찾는 것에 대해 생각할 때 최소한 이러한 데이터가 필요합니다. 그 점에 관해서는 당신의 질문이 과소 정의되어 있다고 생각합니다.