реализация расписания с помощью алгоритма Дейкстры - PullRequest
2 голосов
/ 22 февраля 2012

Я пытаюсь внедрить систему чтения расписаний автобусов для планирования поездки.

Вот мой сценарий:
Я хотел бы просто ввести дату поездки, начальную станцию ​​и конечную станцию, но чтобы добраться из А в В, может потребоваться 3 или 4 стыковочных рейса, и я хотел бы вернуть несколько вариантов, упорядоченных по сумме. необходимое время. В моей настроенной базе данных есть таблица для станций, таблица для поездок и таблица для экземпляров поездок (т. Е. Содержащая включенные даты выполнения поездок).

У меня есть хорошая реализация в алгоритме Дейкстры c # алгоритма, но я нахожу его ограниченным, так как не могу понять, как включить время ожидания на автобусных станциях для соединения рейсов, а также тот факт, что многие поездки могут происходить из одна станция на другую в разное время добавляет путаницы. Я также должен принять во внимание, если поездка занимает один день или даже два, что оказалось проблематичным. Является ли Дейкстры стоит настойчивая с здесь, или кто-нибудь знает что-нибудь другое, что может быть лучше подходит?

Я использую asp.net MVC3, C # и EF4, но я здесь не столько кода, сколько просто точка в правильном направлении процесса, которую я бы лучше использовал, так как это хорошо за все, что я делал раньше. (Возможно, я откусил больше, чем смог бы пережевать, когда вызвался участвовать в этом проекте!) Если бы кто-нибудь мог дать какой-нибудь совет или ссылку на документацию, которая могла бы помочь в этой ситуации, это бы очень помогло. Спасибо

1 Ответ

2 голосов
/ 23 февраля 2012

Во-первых: хорошо, что вы добровольно участвуете в амбициозном проекте. Во-вторых: это может быть немного сложным, и судя по другому сообщению StackOverflow, связанному ниже: NP-Complete .

Алгоритм Дейкстры находит кратчайшие пути из одного источника в статическом графе, но это не то, что вы делаете в этой задаче. Поскольку вершины в таком графике, вероятно, будут существовать в перекрывающихся временных пространствах, самая быстрая шина от 1 до 2 может отправиться в 12:00 вечера, но самая быстрая шина из 2 до 3 может отправиться в 11:59 того же дня. Это не стартер.

Очевидно, вы думали об этом, но абстрактный взгляд на проблему заключается в том, что вы не пытаетесь найти кратчайший путь в графе, но вы пытаетесь найти кратчайший путь в том, что фактически трехмерное пространство (время как третье измерение). Подход с использованием грубой силы (который, тем не менее, подходит для небольших графов) может быть реализован как поиск в ширину, при условии, что вы топологически упорядочиваете узлы по времени.

Ссылка по ссылке здесь: Алгоритм общественного транспорта

Некоторые чтения по теме:

Да пребудет с тобой Сила.

...