Башни Ханоя, как проблема

Question

Есть четыре стека. На первом стеке находятся n чисел 1, 2, ... n в случайном порядке. Остальные три стека пусты. Цель состоит в том, чтобы определить, учитывая состояние первого стека, можно ли переместить все элементы в последний стек, чтобы они были отсортированы. Разрешенные ходы - это перемещение элемента из первого стека во второй или третий стэк и из второго или третьего в четвертый (1> 2, 1> 3, 2> 4, 3> 4). В отличие от ханойских башен, более крупные элементы могут располагаться поверх меньших.

Я должен написать программу для этого, но я не могу придумать алгоритм. Помогите пожалуйста.

Answer 1

Ханойская башня - четыре колышка и дальше : используйте алгоритм Фрейма-Стюарта или представьте состояние игры в виде неориентированного графа и запустите алгоритм поиска кратчайшего пути, например алгоритм Дейкстры .

Answer 2

В отсутствие дальнейшего понимания я бы сделал это как поиск по графику.

Каждое игровое состояние представляет собой массив стеков. Обратите внимание, что для равенства второй и третий стек являются взаимозаменяемыми, поэтому следующее должно быть считается одинаковым:

((1 3 5)
 (2 4)
 (7 9)
 (0))

((1 3 5)
 (7 9)
 (2 4)
 (0))

Граф является ориентированным ациклическим графом. Вершины - это игровые состояния, и края движутся.

Алгоритм состоит в том, чтобы создать этот граф, начиная с заданного первого состояние, но обрезать все состояния, которые не могут привести к целевому состоянию, и объединить все состояния, которые одинаковы (для этого нужно идти в ширину).

Состояния, которые не могут привести к целевым состояниям, являются состояниями

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

Возможны дополнительные ограничения. В частности, я не уверен нет ли способа определить результат из заказа в первый стек напрямую (что сделало бы этот алгоритм лишний).

Answer 3

Это эквивалентно гораздо более простой проблеме. Представьте себе два стека. Первый имеет тот же случайный стек из N дисков, второй - пустой. Переместите диски один за другим из первого стека во второй, придерживаясь следующих правил:

• Нельзя ставить меньший диск на больший.
• Если диск является самым большим или самым маленьким в игре, удалите его из игры. Если это делает один из дисков во втором стеке самым большим или самым маленьким, удалите его тоже (повторяйте, пока самый большой и самый маленький диски в игре не окажутся в первом стеке).

Эта проблема не предполагает выбора и является O (n).

Эти две проблемы эквивалентны, потому что вы должны зарезервировать один из средних стеков (скажем, второй) для укладки самых маленьких дисков, чтобы они оставались там до конца. Таким образом, вы можете заменить этот стек и четвертый стек одной корзиной для мусора, в которую вы всегда можете бросить самый большой или самый маленький диск, который был сыгран. Это оставляет один стек (третий), в котором все еще могут быть конфликты.

EDIT:

Ack! Спасибо Рафалу Доугирду за то, что он поймал мою ошибку. Я постараюсь это исправить, но пока / если я не смогу , этот метод бесполезен .

Answer 4

Я бы использовал A * поиск с эвристикой, основанной на количестве несортированных элементов в любом стеке, причем несортированные элементы в нижней части стека являются наивысшим штрафом для эвристики.