Hanoi Kuleleri Algoritması

Hanoi kuleleri, Fransız matematikçi, Edouard Lucas tarafından önerilen bir çözüm yöntemidir. A,B ve C gibi dik konumda yerleştirilmiş üç çubuk ve N kadar disk içermektedir. İşleyiş şöyledir:

Başlangıçta diskler, üstteki her diskin çapı daha büyük olmak şartıyla A çubuğuna yerleştirilir. Her seferinde sadece bir diskin hareketine izin verildiğinde, büyük disk, küçük diskin üzerine yerleştirilmeden, disklerin C çubuğuna taşınması gerekmektedir. Hanoi problemi, problem alt problemlere parçalanarak çözülebilir. Problemde N kadar disk olduğunu varsayarsak recursive şekilde bir çözüm şu şekilde olabilir:

Sadece bir disk direkt olarak 3. çubuğa konulur N kadar disk 3. adıma yerleştirilmeli Bu da şöyle uygulanabilir.

Örneğin 4 diskli bir çözüm uyguladığımızı varsayalım. Bunun çıktısı şöyle olur:

Çubuk sayısı 3 olduğunda N adet disk için en düşük geçişler, recursive biçinmde Kn = (2 Kn-1 +1) ya da n’ye bağlı şekilde Kn = 2^n – 1 şeklinde bulunmaktadır.

Bu durumun Python ile çözümlenmiş hali ise şöyledir. Algoritmanın ana işlenilen işlevi hanoitoweralgorithm ile tanımlanıp 4 parametre alır. Bu işlev, parametreleri recursive olarak işler.

Disk sayısının belirlenmesi içinse ayrıca bir işlev oluşturulur. Tek parametre alır. Bu parametre çözümdeki N disk sayısını belirtir. N adet disk bu işlevde belirtilir. Buradan alınan parametre bir üstteki ana işlevine yollanılır. Ve diskler de A, B ve C şeklinde parametre olarak yollanılır.

10 adet disk için çıkarılan profile sonucu ise şöyledir:

Kaynaklar:

Sadri Evren Şeker