Duplo Railroad Tycoon: Синтез железнодорожной сети с максимальным покрытием

    image

    Детям Дед Мороз принес железную дорогу Duplo. Сегменты рельс очень легко соединяются между собой, и можно построить какой-нибудь небольшой, скорее всего просто замкнутый путь, поставить станцию и смотреть, как паровозик бегает по кругу. Иногда он останавливается и детёнок должен паровоз «заправить» из колонки, после чего паровоз снова поедет.

    Вот пример простейшего пути:

    image

    Мне этот паровозик очень быстро наскучил, круга после третьего, и я пошел опять копаться на Thingiverse, чтобы в стотысячный раз попытаться применить 3Д принтер для чего-то полезного. И внезапно нахожу я там сегмент-стрелку как раз для паровоза Duplo.

    Стрелка работает так: у нее есть три входа-выхода, назовем их первый, второй и третий. Если поезд въезжает в первый или второй узел, то он покидает стрелку всегда через третий. При этом стрелка переключается на соответствующий узел (т.е. если въехал через первый, то переключится на первый, если через второй — то на второй). А вот если он въезжает в третий узел, то выход зависит от состояния стрелки и он может выехать как через первый так и через второй. Т.е.:

    '1' -> '3' (стрелка переводится на '1')
    '2' -> '3' (стрелка переводится на '2')
    '3' -> если стрелка на '1', то '1', иначе '2'

    Распечатал я таких стрелок парочку, и стал собирать «нормальную» железную дорогу. Только все получалось как-то уныло — паровоз ездил только по части пути, залипая на каком-нибудь кольце, и выезжать оттуда не желал.

    Задачка первая (простая): Сколько должно быть сегментов-стрелок в сети, чтобы все узлы были связаны между собой? Дорога должна быть непрерывна и не иметь тупиков.

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

    Но поднапрягшись, я для простейшего варианта задачу решил за несколько дней. Друг, пришедший в гости, решил ее за 5 минут, не напрягаясь :)

    Обозначим каждую стрелку буквой, узлы так же, как в примере выше. Т.е. в нашей сети есть узлы ['a1','a2','a3','b1','b2','b3'].

    Решение
    Для двух стрелок:
    [('a1','a2'),('a3','b3'),('b1','b2')]
    Так и только так поезд будет проезжать все сегменты дороги в разных направлениях. На самом деле для двух стрелок есть всего два варианта решения — вот этот и неправильный. Бред написал, а никто и не заметил. Ля-ля-ля…

    А что, если взять больше стрелок? Хм, если я над простым решением столько думал, то больше я явно не осилю. Но осилит компьютер! Только как вот к этой задаче подобраться? Я бился несолько дней, все пытаясь присобачить к этому какой-нибудь поиск в глубину, и уже почти все бросил, как вдруг мне пришла в голову идея написать решение на бумажке.

    Я просто разбил весь трэк на шаги:

    Текущее состояние → Переход по стрелке → Переход по соединяющему сегменту → Запомнить новое состояние стрелок

    Т.е. для приведенного выше решения переходы будут такие (состояние стрелок по умолчанию: a3-> a1; b3->b1):

    a1 -> a3 -> b3 (a3-> a1; b3->b1)
    b3 -> b1 -> b2 (a3->a1; b3->b1)
    b2 -> b3 -> a3 (a3->a1; b3->b2) ## обратите внимание, что стрелка b3 переключилась

    Дальше просто:

    • Генерируем все возможные конфигурации дороги при заданном количестве стрелок
    • По каждой дороге:
      • Прогоняем поезд 10 раз и считаем количества проезда по каждому узлу
      • Если есть узлы с 0 или 1 проездом, то это значит система после выхода на режим свалилась в бесконечный цикл
      • Если таких узлов нет, значит поезд благополучно носится по всей дороге, что нам и надо!

    Настолько просто, что я два дня бился головой об стол и пошел в итоге просить совета на stackoverflow, где мне выдали несолько решений на блюдечке за считанные минуты.

    Генератор треков (объявлять задачей и убирать в спойлер не буду — для кого-то вроде меня это может быть очень жестокой шуткой, но попробуйте сами ради интереса решить):

    def getTrack(l):
        # recursion anchor, basic case:
        # when we have 2 nodes only one pair is possible
        if len(l) == 2:
            yield [tuple(l)]
        else:
            # Pair the first node with all the others
            for i in range(1, len(l)):
                # Current pair
                pair1 = [(l[0], l[i])]
                # Combine it with all pairs among the remaining nodes
                remaining = l[1:i] + l[i+1:]
                for otherPairs in getTrack2(remaining, 1):
                    yield pair1 + otherPairs

    Решалка треков:

    def solveTrack(track):
        #контейнер для считалки прохода по нодам с инициализацией
        nodeCount = {}
        for n in nodes:
            nodeCount[n] = 0         
    
        railTr = None
        jointTr = 'a1'
    
        while True:
            pos = jointTr   #текущая позиция
            nodeCount[pos] += 1 #посчитаем ее
            railTr = getTransition(track, pos) #переход по соединяющим рельсам (зависит только от конфигурации трека)
            nodeCount[railTr] += 1  #посчитаем этот узел тоже
            jointTr = tj[railTr] #переход по стрелке (зависит только от состояния стрелки, которое зависит от предыдущего прохода или начального состояния)
            if railTr[1] in ['1','2']: ##Перевести стрелку
                tj[railTr[0]+'3'] = railTr
    
            if max(nodeCount.values()) > nodesTrace and min(nodeCount.values()) < 3: #здесь мы просто после определенного числа прогонов nodesTrace смотрим, не осталось ли заброшенных участков. Если остались - значи поезд где-то залип и конфигурация не годится.
                #print "Infinite cycle detected"
                break
                    
            #sol = "{}\t{}\t{}\t{}\t{}".format(pos, railTr, jointTr, tj['a3'], tj['b3'])
            #print sol
            if max(nodeCount.values()) > nodesTrace * 1.5:
                print "-------------------------------------------------------\n"
                print "Simulation complete!"
                print '\nNodes: ', nodeCount, "\n"
                print "Solution: ", track
                break
        return

    Осталось только задать список узлов для входных данных, переходы между узлами стрелки и начинаем поиск решения! Ура!

    tj = {} #словарь переходов
    nodes = [] #список узлов
    ##create joints transition table
    for jt in range(nJoints):
        tj[idxs[jt]+'1'] = idxs[jt]+'3'
        tj[idxs[jt]+'2'] = idxs[jt]+'3'
        tj[idxs[jt]+'3'] = idxs[jt]+'1'
        nodes.extend((idxs[jt]+'1', idxs[jt]+'2', idxs[jt]+'3'))

    Хм, а решения-то у дороги с четырьмя стрелками нет. И с шестью (я ждал несколько часов) — тоже нет. Вот и все. Мечте конец.

    Хотя. А что, если сделать только часть стрелок переключаемыми, а остальные заморозить? Например, так:

    if railTr[0] in idxs[:nSwitchableJoints]: ## nSwitchableJoints - это количество переключаемых стрелок
                if railTr[1] in ['1','2']: ##Перевести стрелку
                      tj[railTr[0]+'3'] = railTr

    И вуаля — решения есть и их много! Я постарался выбрать что-то покрасивее :)

    image

    Здесь только стрелка 'а' — переключаемая, остальные тройку всегда разрешают в единицу.
    Этот трек соответствует решению:

    [('a1', 'c3'), ('a2', 'f3'), ('a3', 'b3'), ('b1', 'd2'), ('b2', 'e1'), ('c1', 'e2'), ('c2', 'f1'), ('d1', 'f2'), ('d3', 'e3')]
    nSwitchableJoints = 1

    Вот и все, пока!
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 30

      +14
      Молодец. Сразу понятно для кого железная дорога в действительности предназначалась ;)
        0

        Спошлю но: "Что общего между женской грудью и игрушечной железной дорогой?"

      0

      На мой взгляд, наиболее элегантны те дороги, в которых паровозик циклически проходит абсолютно все перегоны. И если я всё правильно промоделировал, то если все стрелки установить в 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
      
        0
        Да, так задача и ставилась — обойти все перегоны. Таблицу не понял, как ее читать :-((( Если это просто счетчик узлов, то можно таблицу переписать в последовательность (все стрелки в зафиксированы в 1):
        A->C->E->D->F->A->B->D->E->B->A->…
        Т.е. перегон CF никогда не посещается
          0

          Не, стрелки фиксировать не надо. Как раз-таки на том, что они не взрезаются, а просто переводятся, и строится проход всех перегонов.

            0
            Если стрелки будут переводиться, то решения нет. Я таблицу не пойму как читать — можешь переделать так как в посте?
              0

              Если стрелки будут переводиться, то см https://habrahabr.ru/post/319702/#comment_10017508
              Автоперевод стрелок это воообще ключевой момент.
              Таблица: шаг — это проход стрелки, следующие столбцы — состояние стрелок после этого шага, последний — только что пройденная стрелка. Ну собственно выставляешь все стрелки в положение 1 и заходишь в стрелку А.

                0
                Ошибка на втором шаге, при проходе стрелки Е меняется состояние стрелки Е, а не D
        0

        А вы ищете треки, на которых поезд проезжает все стрелки или все перегоны? Потому что все стрелки проехать — это не проблема.


        Вот пример для четырех стрелок

        В верхний перегон всегда можно вставить еще две стрелки, и так до бесконечности.


        А вот все перегоны проехать не получится даже если стрелок всего две.

          +3
            _       _
           / \     / \
           |  >- -<  |
           \_/     \_/

          Вот так это делается с 2 стрелками.

            0

            Пардон, вы правы конечно же.

            +1
            Конечно же перегоны. В проходе всех стрелок радости никакой. Из стрелок можно круг слепить — ну и что толку-то?
            –1
            У вас, если паровозик идет из А в Б, то потом идет в Д и участок пути ДФ становится недостижим.
              0
              Несколько раз проверил, все перегоны включены в цикл.
                0
                Не обратил внимания, что стрелки зафиксированы.
              +1
              Для размышления: в качестве борьбы с зацикливанием как-то раз переделал стрелку так чтобы выход был всегда на '1'. Т.е. при проходе 1->3 стрелка отжимается колесами поезда и возвращается сама обратно. Сделал с помощью тонкой пластины 2*8 и «шланга» из набора в качестве пружины. Крайне рекомендуется смазать стрелку (силиконовым спреем) для легкости хода.
              Надеюсь понятно написал.

              Пока не купили мост — строили его из пластинок, добавляли/убирали под каждый следующий стык пластинки в половину высоты стандартного кубика.
                0
                Да, именно это я и делаю в конце статьи:
                nSwitchableJoints — переключающиеся стрелки, остальные «заморожены»
                Причем на покупной стрелке ее достаточно просто зщафиксировать чем-нибудь наглухо, поезд через нее перепрыгивает :-)
                0
                Спасибо за статью. Интересная задача и решение.

                Настолько просто, что я два дня бился головой об стол и пошел в итоге просить совета на stackoverflow, где мне выдали несколько решений на блюдечке за считанные минуты.
                Ссылочку на обсуждение stackoverflow дадите?
                0
                Для размышления:
                На мой взгляд, чтобы обойти все перегоны во всех направлениях должно выполнятся простое условие для каждой стрелки: после перехода 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 и т.д.
                  0
                  И скорей всего задача решения иметь не будет. Вот в приведенном в конце случае прогоны СЕ и ФС — однонаправленные
                    0
                    Ну во-первых, стрелка С фиксированная, а во вторых — для нее нарушено правило последовательности, о котором я говорю, поэтому поезду приходится на ней «прыгать» А вообще, на картинке только одна стрелка А, а остальные вообще могут быть выброшены, поскольку никакого влияния не оказывают. Просто местами поезд проходит по одним и тем же перегонам куски из разных логических циклов.
                      0
                      Просто напиши последовательность, удовлетворяющую моим условиям и посмотрим, сможем ли мы это нарисовать.
                        0
                        Ну а как ты ее напишешь-то? Вот у тебя есть 12 узлов — напиши последовательность :-)
                          0
                          Ну вот ни разу не слабо. Хотелось решить задачу в общем виде, но чересчур много времени отнимают попытки вспомнить Пролог (на мой взгляд лучший подход для решения подобных задач). Может быть на выходных вернусь к решению этой задачи, но тем не менее уже пришел к некоторым выводам:
                          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.
                            0
                            Стрелка B будет давать доступ только к двум кольцам из трех
                    0
                    А где же видео с результатом?
                      0
                      Сними, запость :-)

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое