Башни Ханоя с K колышками

Question

Проблема Ханойских - это классическая проблема рекурсии.Вам предоставляется 3 колышка с дисками на одном из них, и вы должны переместить все диски с одного колышка на другой, следуя приведенным правилам.Вы также должны сделать это с минимальным количеством ходов.

Вот рекурсивный алгоритм, который решает проблему:

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

Теперь представьте себе ту же проблему, только с 4 колышками, поэтому мыдобавьте еще одну промежуточную привязку.Столкнувшись с проблемой необходимости выбора промежуточного колышка в какой-либо одной точке, мы выберем самый левый, если больше 1 свободно.

У меня есть следующий рекурсивный алгоритм для этой задачи:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

Теперь мой вопрос: как бы я обобщил этот рекурсивный подход для работы с K колышками?Рекурсивная функция получит char[], который будет содержать метки каждого стека, поэтому функция будет выглядеть примерно так:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

Я знаю об алгоритме Фрейма-Стюарта, который, скорее всего, оптималенно не доказано, и которое дает вам число ходов.Однако меня интересует строго рекурсивное решение, которое следует шаблону рекурсивных решений для 3 и 4 колышков, то есть оно печатает фактические ходы.

По крайней мере, для меня псевдокод алгоритма Фрейма-Стюартапредставленный в Википедии довольно абстрактный, и мне не удалось перевести его в код, который печатает ходы.Я бы принял эталонную реализацию этого (для случайного k) или даже более подробный псевдокод.

Я пытался придумать какой-то алгоритм, который соответствующим образом переставляет массив меток, но я имелне повезло заставить его работать.Любые предложения приветствуются.

Обновление:

Кажется, что это намного проще решить на функциональном языке.Вот реализация F #, основанная на решении Haskell от LarsH:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

И без обработки 3 колышков как крайнего случая:

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

Обратите внимание, что это не обрабатывает вырожденные случаи, для которых естьнет решения, например HanoiK 2 [1; 2]

Answer 1

Вот реализация на Haskell (обновление: позаботилась о случае с 3 колышками, сделав k = n-1, когда r = 3):

-- hanoi for n disks and r pegs [p1, p2, ..., pr]
hanoiR :: Int -> [a] -> [(a, a)]

-- zero disks: no moves needed.
hanoiR 0 _ = []

-- one disk: one move and two pegs needed.
hanoiR 1 (p1 : p2 : rest) = [(p1, p2)] -- only needed for smart-alecks?

{-
-- n disks and 3 pegs -- unneeded; covered by (null rest) below.
hanoiR n [p1, p2, p3] =
    hanoiR (n - 1) [p1, p3, p2] ++
    [(p1, p2)] ++
    hanoiR (n - 1) [p3, p2, p1]
-}

-- n disks and r > 3 pegs: use Frame-Stewart algorithm
hanoiR n (p1 : p2 : p3 : rest) =
    hanoiR k (p1 : p3 : p2 : rest) ++
    hanoiR (n - k) (p1 : p2 : rest) ++
    hanoiR k (p3 : p2 : p1 : rest)
    where k
        | null rest   = n - 1
        | otherwise   = n `quot` 2

Так что загрузите это в GHCi и введите

hanoiR 4 [1, 2, 3, 4]

т.е. запустить Ханойские башни с 4 дисками и 4 колышками. Вы можете назвать 4 колышка как хотите, например

hanoiR 4 ['a', 'b', 'c', 'd']

Выход:

[(1,2),(1,3),(2,3),(1,4),(1,2),(4,2),(3,1),(3,2),(1,2)]

т.е. переместите верхний диск из колышка 1 в колышек 2, затем верхний диск из колышка 1 в колышек 3 и т. д.

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

Как видно из кода, эвристика для k - это просто floor (n / 2). Я не пытался оптимизировать k, хотя n / 2 показалось мне удачным.

Я проверил правильность ответа для 4 дисков и 4 колышков. Слишком поздно для меня, чтобы проверить больше, без написания симулятора. (@ _ @) Вот еще несколько результатов:

ghci>  hanoiR 6 [1, 2, 3, 4, 5]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,4),(1,5),(1,2),
 (5,2),(4,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 6 [1, 2, 3, 4]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,2),(1,4),(2,4),(1,2),
 (4,1),(4,2),(1,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 8 [1, 2, 3, 4, 5]
[(1,3),(1,2),(3,2),(1,4),(1,3),(4,3),(2,1),(2,3),(1,3),(1,2),
 (1,4),(2,4),(1,5),(1,2),(5,2),(4,1),(4,2),(1,2),
 (3,2),(3,1),(2,1),(3,4),(3,2),(4,2),(1,3),(1,2),(3,2)]

Это проясняет алгоритм?

Действительно существенная часть

hanoiR k (p1 : (p3 : (p2 : rest))) ++      -- step 1; corresponds to T(k,r)
hanoiR (n-k) (p1 : (p2 : rest)) ++         -- step 2; corresponds to T(n-k, r-1)
hanoiR k (p3 : (p2 : (p1 : rest)))         -- step 3; corresponds to T(k,r)

, где мы объединяем последовательности ходов для шагов 1, 2 и 3 алгоритма Фрейма-Стюарта. Чтобы определить ходы, мы комментируем шаги F-S следующим образом:

• Обычно, когда вызывается Ханой, цель определяется (без потери общности) как перенос дисков с первого штифта на второй, используя все оставшиеся штыри для временного хранения. Мы используем это соглашение при повторении, чтобы определить источник, место назначения и разрешенное хранилище разделенных и побежденных подзадач.
• Таким образом, исходный колышек равен p1, а конечный колышек - p2. Все оставшиеся колышки доступны как временное хранилище для проблемы Ханоя верхнего уровня.
• Шаг 1, «Для некоторых k, 1 <= k <n, перенести верхние k дисков на один другой колышек»: мы выбираем p3 в качестве «одного другого колышка». </li>
• Таким образом, «не нарушая колышек, который теперь содержит верхние k дисков» (шаг 2), означает рекурсивно использовать все колышки, кроме p3. То есть р1, р2, а остальные за р3.
• «Перенести верхние k дисков на конечный колышек» (шаг 3) означает переход с «другого колышка» (p3) на p2.

Это имеет смысл?

Answer 2

Хинце, Ральф. Функциональная жемчужина: La Tour D'Hanoi , http://www.comlab.ox.ac.uk/ralf.hinze/publications/ICFP09.pdf

Эта жемчужина призвана продемонстрировать идеи цельнозерновой муки и проективного программирования с использованием головоломки «Ханойские башни» в качестве рабочего примера.У головоломки есть своя красота, которую мы надеемся раскрыть по пути.

Answer 3

Чтобы решить Башни Ханоя, все, что вам нужно сделать, это:

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

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

Кроме того, если k >= 3, вы можете решить ее точно так же, как 3-х башенные башни Ханоя, просто игнорируя остальные колышки, хотя это не будет оптимальным.

Answer 4

Загадка «Ханойские башни» была опубликована в западном мире в 1883 году французским математиком Эдуардом Лукасом под псевдонимом Н. Лукас де Сиам. «Легенда», сопровождавшая игру, гласила, что в Бенаресе во времена правления императора Фо Хи был индийский храм с куполом, который обозначал центр мира (Каши Вишванат). Внутри купола (брамины) священники перемещали золотые диски между 3 алмазными иголками (изношенными столбами), высотой в локте и толщиной с тело пчелы. Бог (Брахма) поместил 64 золотых диска на одну иглу во время творения. (Диски были перемещены в соответствии с неизменными законами от Брахмы, чтобы перенести их с одного колышка на другой) Говорили, что когда они выполнят свою задачу, вселенная придет к концу. Легенда варьируется в зависимости от нескольких сайтов, но в целом она соответствует. «Законы», установленные Брахмой, таковы: 1) Одновременно можно перемещать только 1 диск 2) Нельзя размещать диск на меньшем диске 3) Только верхний диск может быть удален, а затем помещен в верхнюю часть другого колышка, и его диски Игра заканчивается, когда весь стек дисков перемещен в другую колышек. Было быстро обнаружено, что решение с 3 колышками существует, но ни одно не решено для решения с 4 колышками. В 1939 году Американский математический ежемесячник провел конкурс по поиску дисков и дисков. Два года спустя Дж. С. Фрейм и Б. М. Стюарт опубликовали два отдельных (но позже доказавших, что они совпадают) алгоритма. И то, и другое еще не доказано правильно, хотя они, как правило, считаются правильными. Там не было никаких дальнейших достижений по правильному решению. ***** Это работает только на проблемах с 3 колышками ***** Минимальное количество ходов для башни из n дисков быстро оказалось равным 2n − 1, а простое рекурсивное решение выглядит следующим образом: обозначьте три колышка start, goal и temp. Чтобы переместить n колышков от стартового колышка к целеуказателю через временный колышек: Для n> 1, (i) Рекурсивно перемещать верхние n-1 диски от начала к температуре через цель. (ii) Переместите n-й диск от начала до цели. (iii) Рекурсивно перемещать n − 1 дисков от темпов к цели через запуск. Это решение занимает 2n − 1 ходов: (1) Если n = 1, f (n) = 1 = 2n − 1 (2) Если n> 1, f (n) = 2 ∗ (2n − 1−1) +1 = 2n − 2 + 1 = 2n − 1 Простой способ решить эту проблему ... 1,3,7,15,31 - это решения первых нескольких n дисков. Рекурсивно это напоминает nk = 2nk-1 + 1. Отсюда можно сделать вывод, что n = 2n-1. Доказывая по индукции, я ухожу к вам. ***** Базовый алгоритм Фрейма / Стюарта ***** Для дисков m peg и n выберите l, такое, что 0 ≤ l l минимизировано *****Проще простого!! Не!***** Проверить, что это работает против нашего 3-х коленного решения, должно быть легко. Используя k = 2; положим H2 (0) = 0, H2 (1) = 1 и H2 (n> 1) = ∞. Для k = 3 мы можем положить l = n-1. (Это приводит к тому, что наша H2 (n-1) становится конечной) Это позволит нам написать H3 (n) = 2H3 (n-1) + H2 (1), что равно 2n − 1. Это немного игра слов, но это работает. ***** Немного другое описание, чтобы помочь уточнить ***** Алгоритм Фрейма-Стюарта, дающий предположительно оптимальное решение для четырех (или даже более) колышков, описан ниже: Определите H (n, m) как минимальное количество ходов, необходимое для переноса n дисков, используя метки Алгоритм может быть описан рекурсивно: 1. Для некоторого л, 1

`Option VBASupport 1
Option Explicit
Dim n as double
dim m as double
dim l as double
dim rx as double
dim rxtra as double
dim r as double
dim x as double
dim s1 as double
dim s2 as double
dim i as integer
dim a ()
dim b ()
dim c ()
dim d ()
dim aa as double
dim bb as double
dim cc as double
dim dd as double
dim total as double

Sub Hanoi
on error goto errorhandler

m=inputbox ("m# pegs=??")
n=inputbox ("n# discs=??")
x=-1
l=m-1
rx=1
s1=0
s2=0
aa=0

while n>rx
        x=x+1
        r=(l+x)/(x+1)
        rx=r*rx
wend
rx=1
for i=0 to x-1
        r=(l+i)/(i+1)
        rx=r*rx
        redim a (-1 to x)
        redim b (-1 to x)
        redim c (-1 to x)
        redim d (-1 to x)
            a(i)=rx
            b(i)=i
            bb=b(i)
            c(i)=rx-aa
            aa=a(i)
            cc=c(i)
            d(i)=cc*2^bb
            dd=d(i)
            s1=s1+dd
next

rxtra=n-aa
s2=rxtra*2^(bb+1)
total = 2*(s1+s2)-1
msgbox total

exit sub
errorhandler: msgbox "dang it!!"
'1, 3, 5, 9, 13, 17, 25, 33 first 8 answers for 4 peg
'16=161,25=577,32=1281,64=18433
End Sub`

Раскрытие: эти источники были использованычтобы подтвердить ответы и для некоторой истории проблемы. Трудно точно сказать, где это произошло, потому что для проверки использовалось несколько сайтов ... так что они являются источниками для многих частей истории.

Answer 5

http://tristan -interview.blogspot.com / 2012/02 / п-диски-и-к-колышки-разгибания проблемно-of.html

Answer 6

Facebook k-peg N ​​дисков Ханоя можно решить с помощью алгоритмов BFS.Для решения посетите http://www.woolor.com/InterviewMitra/41/facebook-k-peg-of-tower-of-hanoi-solution