Вот, сам придумал!

Задачка, в общем-то простая, и решение ее довольно известно,
но может кому-нибудь будет интересно...

Итак:

На неком железнодорожном узле N, имеющем 8 путей,
необходимо сделать сортировку проходящих составов.

Составы имеют следующие важные признаки:
Э — Электровоз
Т — Тепловоз
П — Пригородный
Д — Дальнего следования
З — Зеленый
С — Синий

На вход узла N одновременно прибывают 8 различных составов.
Каждый состав прибывает по случайному пути.
На выходе узла N составы должны двигаться в строго определенном порядке:

     ------ . . .  -----    
? --| 1              1  |-- Э.П.З
? --| 2              2  |-- Э.П.С
? --| 3              3  |-- Э.Д.З
? --| 4    Узел N    4  |-- Э.Д.С
? --| 5              5  |-- Т.П.З
? --| 6   ------->   6  |-- Т.П.С
? --| 7              7  |-- Т.Д.З
? --| 8              8  |-- Т.Д.С
     ----- . . . -------

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

Предписание дается один раз при установке стрелки.

Пример стрелки:

      Э
     /------
----*
     \------
      Т
Предписание: Электровозы налево, тепловозы направо.

Путь от стрелки до стрелки — перегон.
На одном перегоне может находиться только один состав.
Движение будем считать дискретным.
Прохождение одного перегона занимает один такт.

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

--------------------------------------------

Нужно создать оптимальную структуру узла, 
минимизировав количество стрелок и время прохождения составов.

X = ? - количество стрелок
T = ? - количество тактов для прохождения узла (пессимистик) 

--------------------------------------------

(С) UgN




ЗЫ: Задача-то программерская, и я просто устал извращать условие...

Здравствуйте, UgN, Вы писали:

UgN>Пример стрелки:
UgN>

UgN>

UgN>      Э
UgN>     /------
UgN>----*
UgN>     \------
UgN>      Т
UgN>Предписание: Электровозы налево, тепловозы направо.
UgN>

Правильно ли я понял, что существуют не только расщепляющие, но и сливающие стрелки? Типа такой:

----
     \
       *-----
     / 
----

Они тоже считаются при минимизации? Или это вообще не стрелки?

Здравствуйте, Pushkin, Вы писали:


P>Правильно ли я понял, что существуют не только расщепляющие, но и сливающие стрелки?

Это не стрелка. Это просто слияние двух путей.
Будем считать, что там стоит семафор.

На стрелке сидит стрелочник и рулит. А тут нет.

P>

P>----
P>     \
P>       -----
P>     / 
P>----
P>

P>Они тоже считаются при минимизации?

Нет.
Считаются только стрелки и время прохождения.

Здравствуйте, Pushkin, Вы писали:

P>Правильно ли я понял, что существуют не только расщепляющие, но и сливающие стрелки? Типа такой:

У ж/дорожников это называется "противошерстные" и "пошерстные".
Кстати, есть классная программуля BAHN одного немецкого хлопца для симуляции железных дорог.

Здравствуйте, UgN, Вы писали:

UgN>Это не стрелка. Это просто слияние двух путей.
UgN>Считаются только стрелки и время прохождения.

Тогда требую приз за самое тупое решение
Всё слить в одну за 7 слияний и разщепить обратно за 7 стрелок.
Неужели можно меньше стрелок?

Здравствуйте, Аноним, Вы писали:

А>У ж/дорожников это называется "противошерстные" и "пошерстные".
Возможно, я не железнодорожник. У меня только один тип стрелки.
А>Кстати, есть классная программуля BAHN одного немецкого хлопца для симуляции железных дорог.
Эта задача совсем о другом. И поезда тут просто маскируют истинное лицо...

Здравствуйте, Pushkin, Вы писали:

P>Тогда требую приз за самое тупое решение
Не получишь.
По итогам всех задач в Этюдах приз мой!
И не надейся!
P>Всё слить в одну за 7 слияний и разщепить обратно за 7 стрелок.
Ну в одну слить-то можно, но это уже даст задержку в 8 тактов на прохождение узкого места.
+ еще 2 на расщепление ( если я правильно понял как ты будешь их расщеплять )
Итого 7 стрелок и 10 тактов
P>Неужели можно меньше стрелок?
Меньше нет. Но можно быстрее, хотя и сбольшим количеством стрелок.
К сожалению, я так и не придумал точного критерия.
Поэтому я просто хочу увидеть "задуманный" вариант. (24 стрелки и 5 тактов)
Или может какое-нибудь другое решение.

UgN>Итого 7 стрелок и 10 тактов
Всегда
UgN>Поэтому я просто хочу увидеть "задуманный" вариант. (24 стрелки и 5 тактов)
В худшем случае. В лучшем 3 такта.

Здравствуйте, UgN, Вы писали:

UgN>Меньше нет. Но можно быстрее, хотя и сбольшим количеством стрелок.
UgN>К сожалению, я так и не придумал точного критерия.
UgN>Поэтому я просто хочу увидеть "задуманный" вариант. (24 стрелки и 5 тактов)

Пожалуй, по уму самый правильный критерий — скорость. А точее так:

Скорость_поездов=1, длина_поездов=1.
Поезда не могут пересекаться.
К узлу все подошли в момент времени 0.
Минимизировать время выхода последнего поезда.

Здравствуйте, Pushkin, Вы писали:

P>Пожалуй, по уму самый правильный критерий — скорость.

Решение: 56 стрелок, 3 такта всегда.

Нужна золотая середина...

Здравствуйте, UgN, Вы писали:

P>>Пожалуй, по уму самый правильный критерий — скорость.
UgN>Решение: 56 стрелок, 3 такта всегда.
UgN>Нужна золотая середина...

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

Здравствуйте, Pushkin, Вы писали:

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

Нихт ферштейн.

При единичной скорости и единичной длине перегона с порождающей стрелкой, время прохождения будет равно кол-ву тактов.
Или нет?

Требований к планарности не было...
Пересекаться пути могут.


Просто пересечение — один поверх другого.

   |
---|---
   |

Соединение — с семафорами
(т.е. в этом кресте может быть только один состав)

   |
---*---
   |

В общем, как в эл. цепях.

Здравствуйте, UgN, Вы писали:

UgN>Требований к планарности не было...
UgN>Пересекаться пути могут.

Пути могут, составы — нет. Никогда.
Иначе нереальная задача получается — не бывает эстакад на жд
Да и лучше задача получается имхо — чётче условие, понятней критерий, неясно как решать

Здравствуйте, Pushkin, Вы писали:

UgN>>Требований к планарности не было...
UgN>>Пересекаться пути могут.

P>Пути могут, составы — нет. Никогда.

Просто пересечение — один поверх другого — эстакада

   |
---|---
   |

P>Иначе нереальная задача получается — не бывает эстакад на жд

railroad overpass — железнодорожная эстакада

P>Да и лучше задача получается имхо — чётче условие, понятней критерий, неясно как решать

Пусть будут 2 задачи — одна с требованием планарности, другая без.

Здравствуйте, UgN, Вы писали:
UgN>минимизировав количество стрелок и время прохождения составов.
Условие-то неоднозначное. Очевидно, что увеличение одного, уменьшает другое ( вразумных пределах )
г-н Пушкин привел ответ с минимумом стрелок
Минимальное время получится, если не жалеть стрелок:
После каждого входа отдельно поделить как надо и слить одинаковые с разных входов — задержек вообще не будет. Стрелок будет наверное 56. А время прохождения равно 7.

Можно как-то оптимизировать соотношение между стрелками и временем. Например сливать входы попарно и делить как надо потом сливать -> стрелок в два раза меньше, но уже могут быть конфликты. Поезда все приходят одновременно? Тогда с каждого второго входа каждый поезд задержать на один ход и конфликтов не станет. Ясно, что необязательно попарно...

Здравствуйте, Рома Мик, Вы писали:

UgN>>минимизировав количество стрелок и время прохождения составов.
РМ>Условие-то неоднозначное. Очевидно, что увеличение одного, уменьшает другое ( вразумных пределах )
Да.
РМ>г-н Пушкин привел ответ с минимумом стрелок
Да.
РМ>Минимальное время получится, если не жалеть стрелок:
Да.
РМ>После каждого входа отдельно поделить как надо и слить одинаковые с разных входов — задержек вообще не будет. Стрелок будет наверное 56. А время прохождения равно 7.
не 7, а 3.
Считаем стрелку с последующим перегоном (или вообще не считаем стрелки)

РМ>Можно как-то оптимизировать соотношение между стрелками и временем. Например сливать входы попарно и делить как надо потом сливать -> стрелок в два раза меньше, но уже могут быть конфликты. Поезда все приходят одновременно? Тогда с каждого второго входа каждый поезд задержать на один ход и конфликтов не станет. Ясно, что необязательно попарно...

Поезда приходят одновременно.
Как вы хотите сливать?



Я не претендую на знание правильного ответа.
Каждый будет внимательно рассмотрен.
Потом я покажу свой вариант.
Точнее, структуру, с которой все и началось.
Возможно это и не оптимальный вариант, но он мне нравится.

Здравствуйте, UgN, Вы писали:
UgN>>>минимизировав количество стрелок и время прохождения составов.
UgN>Как вы хотите сливать?
Пока я писал предыдущий пост, упоминалась планарность, так вот я таких ограничений не накладывал. А сливать я предлагал по два. Т.е. 1 + 2, 3 + 4, 5 + 6, 7 + 8. А дальше все как раньше, но входов 4, а не 8.

Здравствуйте, Рома Мик, Вы писали:

UgN>>>>минимизировав количество стрелок и время прохождения составов.
UgN>>Как вы хотите сливать?
РМ>Пока я писал предыдущий пост, упоминалась планарность, так вот я таких ограничений не накладывал.
У меня без планарности. С эстакадами.
РМ>А сливать я предлагал по два. Т.е. 1 + 2, 3 + 4, 5 + 6, 7 + 8. А дальше все как раньше, но входов 4, а не 8.

Входов должно быть 8.
Состав может остановиться на стрелке и переждать, пока освободится путь.
На стрелке может скопиться несколько поездов.

Еще варианты?

* Допустимы эстакады.
* Поезда могут ныкаться от столкновения только в стрелках. Просто так, сразу на входе, их слить нельзя.
* Должно быть 8 входов-въездов в стрелки.

* Подсчет тактов:

-o-o-o-   это 3 стрелки и соединяющие их пути = 3 такта (первый отрезочек пропускаем)

Считаем, что стрелка и исходящий путь требуют 1 такт.


Эффективность (эмпирическая формула)

X   (Tmax - Tmin)
- + -------------
N         2

N = 8 кол-во составов

X = кол-во стрелок

Tmax = худшее время разъезда составов
Тmin = лучшее время разъезда составов


Вообще-то, вместо второго слагаемого нужно брать что-то вроде матожидания, но я уже забыл теор. вер.

Здравствуйте, UgN, Вы писали:
UgN>У меня без планарности. С эстакадами.
Ну вот и ладушки.
РМ>>А сливать я предлагал по два. Т.е. 1 + 2, 3 + 4, 5 + 6, 7 + 8. А дальше все как раньше, но входов 4, а не 8.
UgN>Входов должно быть 8.
Конечно 8. Если слить пути как я предложил, то получим 8 поездов на 4-х путях по 2 друг за другом. Дальше каждый из 4-х путей делиться на 8 7-ю стрелками. Итого 28 стрелок и время 4.
Если слить по четыре, то получится 14 стрелок, но время уже 6. А дальше вариант Пушкина.
Вот такие вот варианты соотношения цена/производительность...