LINUX.ORG.RU
ФорумTalks

Отцы матана, подскажите решение

 


1

2

Всем привет

У меня в graphviz есть граф, описывающий маршруты транспорта в некоем городе, nodes - остановки, edges - дороги между ними. Набор узлов и рёбер составляет собой маршрут. Маршрутов много, спланированы они убого, хочется спланировать новые. То есть граф надо заново поделить на наборы узлов и рёбер, маршруты.

Для начала условия такие:

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

Возможные решения, в порядке убывания моей радости:

  • функция типа SplitToRoutes() в octave
  • готовый алгоритм из теории, который надо закодить самому
  • придумывание своего алгоритма
  • брутфорс

Посоветуйте что-нибудь толковое.

А то придётся списывать^U

★★★★

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

dikiy ★★☆☆☆ ()
Последнее исправление: dikiy (всего исправлений: 2)

Комбинация метода Монте-Карло на графах с методом локальной оптимизации, например:
«Алгоритм статистических испытаний для определения параметров структур сетей связи по методу Монте-Карло» ©.

Ещё можно «потыкать» генетические алгоритмы на графах.

quickquest ★★★★★ ()
Ответ на: комментарий от quickquest

Ещё можно «потыкать» генетические алгоритмы на графах.

Я тыкал в свое время. То еще удовольствие, хочу сказать...

dikiy ★★☆☆☆ ()

Посоветуйте что-нибудь толковое

Как тебе уже сказали, твои условия кривые. Если тебе такую задачку задали, то можешь потроллить препода и сделать один маршрут.

Может быть стоит добавить условие, что время в пути между любыми узлами должно быть минимальным?

no-such-file ★★★★★ ()
Последнее исправление: no-such-file (всего исправлений: 1)

Набор узлов и рёбер составляет собой маршрут.

Каких? Подозреваю, что последовательно соединённых, но всё же не ясно, например, может/должен ли он быть циклическим.

f1u77y ★★★ ()

Как уже сказали выше — гамильтонов цикл.

Типичный пример говнозадачи, когда хорошая практическая проблема подтянута под желаемый ответ, который практически никакой пользы не несет. В результате у одних студентов складывается впечатление, что гамильтонов цикл это то, что нужно в задачах составления маршрутов, а у других, что вся эта теория нужна есть сферический конь в вакууме.

soomrack ★★★ ()

* от любого до любого узла можно добраться с двумя (или меньше) пересадками

Думаю, это невыполнимо для произвольного графа. Пример - бинарное дерево.

tyakos ★★★ ()
Ответ на: комментарий от no-such-file

Не, один точно не получится, там куча веток в районы. Ну и про «списывать» это шуточка была.

muon ★★★★ ()
Ответ на: комментарий от tyakos

Невыполнимо. Если с двумя решение не найдётся, то подниму до трёх.

muon ★★★★ ()
Ответ на: комментарий от f1u77y

Хорошее замечание! Циклических не хотелось бы, лучше туда-обратно. Но тогда непонятно, что делать с дорогами с односторонним движением.

muon ★★★★ ()
Ответ на: комментарий от thunar

Измерить и учитывать можно расстояние, но на время оно влияет слабо. Проще не учитывать.

muon ★★★★ ()
Ответ на: комментарий от muon

Циклических не хотелось бы, лучше туда-обратно

Но ведь это просто цикл по одним и тем же узлам. У тебя же нет маршрутов в один конец.

no-such-file ★★★★★ ()

Второе условие заменить на адекватное «не использовать одно ребро больше m раз».

Если не поменять, то всё, как уже сказали выше, сведётся к гамильтоновым циклам либо на весь граф, либо внутри отдельных его областей с транзитными маршрутами между ними (привет московским автобусам).

chupasaurus ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.