Dijkstra 's 알고리즘을 사용한 시간표 구현

Question

여행 계획을 세우기 위해 코치 시간표를 읽는 시스템을 구현하려고합니다.

다음은 나의 시나리오입니다.
여행 날짜, 출발역 및 종점을 입력하고 싶지만 A에서 B로 가려면 3 ~ 4 회의 연결 여행이 필요합니다. 몇 가지 옵션을 반환하고 필요한 총 시간으로 정렬합니다. 내 데이터베이스 설정에는 방송국 테이블, 여행 표 및 여행 인스턴스 표가 있습니다 (예 : 여행 일수가 포함 된 날짜 포함).

나는 Dijkstra 알고리즘의 C#에서 좋은 구현을 얻었지만, 여행을 연결하기 위해 버스 정류장에서 기다리는 시간을 포함하는 방법과 많은 여행이 갈 수 있다는 사실을 알 수 없기 때문에 제한적이라는 것을 알았습니다. 다른 시간에 한 방송국에서 다른 방송국으로 혼란에 가중됩니다. 여행이 하루 또는 2 일 걸려 완료해야하는 경우에도 고려해야하며, 번거 로움이 입증되었습니다. Dijkstra는 여기에 참을 가치가 있습니까? 아니면 누구에게 더 적합한 다른 것을 알고 있습니까?

MVC3, C# 및 EF4 asp.net을 사용하고 있습니다.하지만 여기에 나오는 코드가 많지 않습니다. 프로세스의 올바른 방향에 대한 요점은 다음과 같습니다. 전에 한 적이없는 무엇보다. (나는이 프로젝트에 자원했을 때 내가 씹을 수있는 것보다 더 많은 것을 물어 뜯을 수있다.) 누군가가 조언이나이 상황을 도울 수있는 문서에 대한 링크를 제공 할 수 있다면 엄청나게 도움이 될 것이다. 감사합니다

Answer 1

우선 : 야심적인 프로젝트에 자원하여 당신을 잘합니다. 둘째 : 이것은 도전하고, 아래에 링크 된 다른 StackOverflow 게시물로 판단 할 수 있습니다 : NP-Complete.

Dijkstra의 알고리즘은 정적 그래프에서 단일 소스 최단 경로를 찾습니다. 그러나이 문제에서 여러분이하는 것은 아닙니다. 이러한 그래프의 정점은 아마도 중복 시간적 스페이스에 존재하는 것 때문에, ₂에 ₁에서 빠른 버스는 ₃에 ₂ ~ 12 시까지만 빠른 버스에 남아있을 같은 날 오전 11시 59 분에 출발 할 수 있습니다. 그건 비 스타터 다.

분명히 생각해 보았지만 문제를 보는 추상적 인 방법은 그래프에서 최단 경로를 찾으려는 것이 아니라 가장 짧은 경로를 찾기 위해 노력하고 있다는 것입니다. 효과적으로 3 차원 공간 (3 차원으로서의 시간)이다. 그럼에도 불구하고 소규모 그래프의 경우 무차별 대입 (brute force) 접근법은 시간에 따라 노드를 위상 적으로 노드를 정렬한다고 가정 할 때 폭 넓은 첫 번째 검색으로 구현 될 수 있습니다.

관련 링크는 여기에 있습니다 : 주제에 Bus public transport algorithm

일부 읽기 :

http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/2792

• http://web.archive.org/web/20121224231948/http://www2.isye.gatech.edu/~mwps/publications/archetti-savelsbergh-revision.pdf
는 포스가 당신과 함께 할 수 있음.