Во всем виноват стрелочник
От: UgN  
Дата: 24.03.03 10:39
Оценка: 15 (1)
Вот, сам придумал!

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

Итак:

На неком железнодорожном узле 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




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