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

Ось і все, поки!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.