сортировка бункеров по два за раз

Я столкнулся со следующей проблемой в случае, когда есть только 4 бункера. Я могу сделать это на 6 или 8, но не на 4. Кроме того, может ли кто-нибудь помочь мне придумать обобщенный алгоритм для этого?сортировка бункеров по два за раз

У вас есть n бункеров (расположенных в альтернативном порядке B A B A ...), которые вы можете перемещать по 2 за раз и давать 2n слота. Отсортируйте их так, чтобы в конце все ячейки «А» остались от всех «B» бункеров. Все они должны быть смежными, то есть нет пробелов в конце. Например:

_ _ _ _ B A B A

Благодаря

Edit: Да, вы должны переместить два смежных бункеров одновременно в двух соседних точках.

Редактировать 2: Нет, вы не можете транспонировать контейнеры. Вот пример с 6 бункеров:

_ _ _ _ _ _ бабаба

_ _ _ _ ABB _ _ ABA

_ _ _ _ ABBBAA _ _

_ _ AAABBB _ _ _ _

источник

2014-10-18 Riz

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

да @MikeDinescu, я отредактировал вопрос – Riz

Когда вы перемещаете 2 бункера, можете ли вы транспонировать их при их перемещении? (Т. Е. '__BA' =>' AB__'? Когда вы перемещаете 2 бункера в два соседних пятна, должны ли эти пятна быть пустыми? – dbc

Простой поиск в первом месте достижимых позиций для случая с четырьмя ящиками показал, что он фактически не может быть разрешен. Вот грубый псевдокод, так что вы можете попробовать написать, что для себя:

todo_queue = ["____BABA", []] 
path_to_position = {} 
while things in todo_queue: 
    (position, path) = todo_queue.next() 
    if position in path_to_position: 
     continue # We've been here before. 
    if position is success: 
     print path 
     EXIT HERE 
    for my move in possible_moves(position): 
     todo_queue.add([position after move, path + [move]])

Для общего решения, достаточно, чтобы сделать это в ширину первого поиска для случаев 6, 8, 10 и 12 бункеров в качестве специальных случаев. Для любых больших ячеек с четными числами вы можете решить один из этих 4, чтобы создать середину решения, а затем разрешить блоки из 8. Затем вы можете легко перемещать и переставлять эти решенные пары по паре в окончательное решение.

источник

2014-10-19 18:51:07 btilly

сортировка бункеров по два за раз

ответ

Смежные вопросы