@KarmaMaker

Железнодорожная сеть задана набором станций. Между некоторыми станциями проложены пути. Длина путей задается целыми числами. Пути двунаправленные одноколейные ( Поезда идущие навстречу друг другу сталкиваются ). Станция - точка ( поезда оказавшиеся на станции в один момент времени, сталкиваются ). Маршруты поездов заданы списком станций, через которые они проезжают. Скорости одинаковые( скажем равны единице ). Поезда начинают движение одновременно. Последостижения конечной станции поезд исчезает. Поезд представляет собой точку.

Задача: По заданной конфигурации сети и поездов определить возникнет ли столкновение

______________________________________________________________

Единственная идея которая у меня возникает в качестве реализации алгоритма, - прогнать эту "сеть" в режиме симуляции с шагом в 0.5 часов, и если совпадут "координаты" поездов ( станция 1, станция 2, точка на линии от станции 1 к станции 2 ) , то считать что авария произошла.

Что-то мне подсказывает, что это - хреновое решение.
Хотелось бы услышать другие идеи по реализации ( код не обязателен ).

0

@turbanoff

не понял что за шаг 0,5 часов.
Я бы для каждого скписка станций(маршрута каждого поезда) посчитал время прибытия.
например
поезд A: 0 - станция 1, 9 - станция 2, 15 - станция 3
поезд B: 0 - станция 5, 6 - станция 3, 12 - станция 2, 21 - станция 1

далее смотрим интервалы движения, но не получасовые, или какие то другие, а те которые соответствуют граничным значениям, для каждого шага поездов.
то есть нужные интервалы:
[0..6], [6..9], [9..12], [12..15], [15..21].

поезд A:

[0..6]	0⇒0:2
[6..9]	0:2⇒2
[9..12]	2⇒2:3
[12..15]	2:3⇒3

поезд B:

[0..6]	5⇒3
[6..9]	3⇒2:3
[9..12]	2:3⇒2
[12..15]	2⇒1

ищем граничные целые, и встречные маршруты.

0

@KarmaMaker

Учитывая что скорость поездов одинакова и равна единице скорость их сближения будет 2 крокодила тогда если запустить симуляцию с шагом 0,5 попугаев, то ( помним что все расстояния целые ) если должна произойти авария то поезда в какой то момент времени будут находится в одной точке ( Впрочем это решение явно неоптимально и являет собой пример костылестроения ).

Добавлено через 8 минут
Т.е. ты предлагаешь сначала для каждого поезда вычислить время прбытия для каждой станции в маршруте и дальше что?

0

@nio

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

Если же у тебя простая учебная задача (из точек А и Б навстречу друг другу с одинаковой скоростью вышли 2 поезда. Найти точку столкновения), то она и выеденного яйца не стоит. Я тебе без всяких алгоритмов скажу, столкнуться они ровно в середине отрезка. Зная скорость движения, нужно высчитать время за которое один поезд пройдет ровно пол пути, это и будет время столкновения. В общем - начальные классы.

0

@KarmaMaker

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

К счастью или к сожалению она не такова.

0

@chessman1

Построить таблицу состояний.

0

@KarmaMaker

Не очень понимаю твою идею, приведи пример таблицы состояний для этой задачи пожалуйста.

0

@chessman1

Таблицы состояний - это давно испытанный метод решения
алгоритмических задач, который позволяет резко избежать,
сложного кода с использованием if-else-case
Раз'яснять здесь места нет - в гугле вся теория по этому
вопросу есть.

0

@KarmaMaker

Вопрос был не в том что такое таблица состояний ( требование перепечатывать учебник с моей стороны было бы как минимум неразумным ), а в том, как применить таблицу состояний к данной задаче.

0

@grigorill2

Да мне недавно задали точно такую же задачу. Тоже сижу думаю над ней.

0

@KarmaMaker

Транзас?

0

@grigorill2

Да он самый

0