Комментарии 30
Молодец. Сразу понятно для кого железная дорога в действительности предназначалась ;)
На мой взгляд, наиболее элегантны те дороги, в которых паровозик циклически проходит абсолютно все перегоны. И если я всё правильно промоделировал, то если все стрелки установить в 1 и паровозик начинает с проезда 3->1, то
вот так замкнется дорога на картинке в конце статьи
№ A B C D E F
0 1 1 1 1 1 1 Паровозик начинает в А3→1
1 1 1 1 1 1 1 C
2 1 1 1 2 1 1 E
3 1 1 1 2 1 1 D
4 1 1 1 2 2 1 F
5 2 1 1 2 2 1 A
6 2 1 1 2 2 1 B
7 2 1 1 2 2 2 D
8 2 1 1 2 2 2 E
9 2 1 1 2 2 2 C
10 1 1 1 2 2 2 A
11 1 1 1 2 2 2 B
12 1 1 1 2 2 2 D
13 1 1 1 2 2 2 E
14 1 1 1 2 2 2 C
15 1 1 1 2 2 2 A
Да, так задача и ставилась — обойти все перегоны. Таблицу не понял, как ее читать :-((( Если это просто счетчик узлов, то можно таблицу переписать в последовательность (все стрелки в зафиксированы в 1):
A->C->E->D->F->A->B->D->E->B->A->…
Т.е. перегон CF никогда не посещается
A->C->E->D->F->A->B->D->E->B->A->…
Т.е. перегон CF никогда не посещается
Не, стрелки фиксировать не надо. Как раз-таки на том, что они не взрезаются, а просто переводятся, и строится проход всех перегонов.
Если стрелки будут переводиться, то решения нет. Я таблицу не пойму как читать — можешь переделать так как в посте?
Если стрелки будут переводиться, то см https://habrahabr.ru/post/319702/#comment_10017508
Автоперевод стрелок это воообще ключевой момент.
Таблица: шаг — это проход стрелки, следующие столбцы — состояние стрелок после этого шага, последний — только что пройденная стрелка. Ну собственно выставляешь все стрелки в положение 1 и заходишь в стрелку А.
А вы ищете треки, на которых поезд проезжает все стрелки или все перегоны? Потому что все стрелки проехать — это не проблема.
Вот пример для четырех стрелок
В верхний перегон всегда можно вставить еще две стрелки, и так до бесконечности.
А вот все перегоны проехать не получится даже если стрелок всего две.
У вас, если паровозик идет из А в Б, то потом идет в Д и участок пути ДФ становится недостижим.
Для размышления: в качестве борьбы с зацикливанием как-то раз переделал стрелку так чтобы выход был всегда на '1'. Т.е. при проходе 1->3 стрелка отжимается колесами поезда и возвращается сама обратно. Сделал с помощью тонкой пластины 2*8 и «шланга» из набора в качестве пружины. Крайне рекомендуется смазать стрелку (силиконовым спреем) для легкости хода.
Надеюсь понятно написал.
Пока не купили мост — строили его из пластинок, добавляли/убирали под каждый следующий стык пластинки в половину высоты стандартного кубика.
Надеюсь понятно написал.
Пока не купили мост — строили его из пластинок, добавляли/убирали под каждый следующий стык пластинки в половину высоты стандартного кубика.
Спасибо за статью. Интересная задача и решение.
Настолько просто, что я два дня бился головой об стол и пошел в итоге просить совета на stackoverflow, где мне выдали несколько решений на блюдечке за считанные минуты.Ссылочку на обсуждение stackoverflow дадите?
Для размышления:
На мой взгляд, чтобы обойти все перегоны во всех направлениях должно выполнятся простое условие для каждой стрелки: после перехода 3->1 должен выполнятся переход 2->3 и после перехода 3->2 должен состоятся переход 1->3. При этом важна последовательность переходов, но между ними могут быть переходы других стрелок и количество переходов 3->1 и 3->2 не важна, то есть после перехода 3->1 может повторно случится неограниченное количество переходов 3->1, но в последовательности обязательно должен присутствовать переход 2->3. Аналогично для перехода 3->2. Используя это правило можно достаточно легко построить связку из 2, 3, 4, и т.д. стрелок. Цикл для двух стрелок для примера будет выглядеть как: А23-В31-В23-А32-А13-В32-В13-А31-А23 и т.д.
На мой взгляд, чтобы обойти все перегоны во всех направлениях должно выполнятся простое условие для каждой стрелки: после перехода 3->1 должен выполнятся переход 2->3 и после перехода 3->2 должен состоятся переход 1->3. При этом важна последовательность переходов, но между ними могут быть переходы других стрелок и количество переходов 3->1 и 3->2 не важна, то есть после перехода 3->1 может повторно случится неограниченное количество переходов 3->1, но в последовательности обязательно должен присутствовать переход 2->3. Аналогично для перехода 3->2. Используя это правило можно достаточно легко построить связку из 2, 3, 4, и т.д. стрелок. Цикл для двух стрелок для примера будет выглядеть как: А23-В31-В23-А32-А13-В32-В13-А31-А23 и т.д.
И скорей всего задача решения иметь не будет. Вот в приведенном в конце случае прогоны СЕ и ФС — однонаправленные
Ну во-первых, стрелка С фиксированная, а во вторых — для нее нарушено правило последовательности, о котором я говорю, поэтому поезду приходится на ней «прыгать» А вообще, на картинке только одна стрелка А, а остальные вообще могут быть выброшены, поскольку никакого влияния не оказывают. Просто местами поезд проходит по одним и тем же перегонам куски из разных логических циклов.
Просто напиши последовательность, удовлетворяющую моим условиям и посмотрим, сможем ли мы это нарисовать.
Ну а как ты ее напишешь-то? Вот у тебя есть 12 узлов — напиши последовательность :-)
Ну вот ни разу не слабо. Хотелось решить задачу в общем виде, но чересчур много времени отнимают попытки вспомнить Пролог (на мой взгляд лучший подход для решения подобных задач). Может быть на выходных вернусь к решению этой задачи, но тем не менее уже пришел к некоторым выводам:
1. Мои правила не учитывают геометрию, поскольку пройдя переход в одном направлении ты автоматически фиксируешь цепочку в другом месте в соответствии с геометрией.
2. Из геометрии так же вытекает, что стрелок должно быть четное количество, для нечетного количества решения не существует.
3. Граф связей между стрелками должен быть связанным, то есть из любой точки можно достигнуть любой. Это должно работать еще до наложения парадигмы стрелок на вершины графа.
4. Нашел простой способ построить сеть с любым четным количеством стрелок — в простейшей схеме из двух стрелок разрывается один из циклов и заменяется на две стрелки с циклами — получается такая сампоподобная сеть.
5. Ну и наконец, последовательность для 12 узлов (4-х стрелок):
A13-B13-C31-C23-B32-D31-D23-B23-C32-C13-B31-A32-A13-B13-C31-C23-B32-D32-D13-B23-C32-C13-B31-A31-A23-B13.
1. Мои правила не учитывают геометрию, поскольку пройдя переход в одном направлении ты автоматически фиксируешь цепочку в другом месте в соответствии с геометрией.
2. Из геометрии так же вытекает, что стрелок должно быть четное количество, для нечетного количества решения не существует.
3. Граф связей между стрелками должен быть связанным, то есть из любой точки можно достигнуть любой. Это должно работать еще до наложения парадигмы стрелок на вершины графа.
4. Нашел простой способ построить сеть с любым четным количеством стрелок — в простейшей схеме из двух стрелок разрывается один из циклов и заменяется на две стрелки с циклами — получается такая сампоподобная сеть.
5. Ну и наконец, последовательность для 12 узлов (4-х стрелок):
A13-B13-C31-C23-B32-D31-D23-B23-C32-C13-B31-A32-A13-B13-C31-C23-B32-D32-D13-B23-C32-C13-B31-A31-A23-B13.
А где же видео с результатом?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Duplo Railroad Tycoon: Синтез железнодорожной сети с максимальным покрытием