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.

(N-1) olan disk orta çubuğa taşınır.

En altta kalan disk direkt sağa konulur.

(N-1) olan disk sağa taşınır.
Örneğin 4 diskli bir çözüm uyguladığımızı varsayalım. Bunun çıktısı şöyle olur:

Diski A çubuğundan B çubuğuna koy
Diski A çubuğundan C çubuğuna koy
Diski B çubuğundan C çubuğuna koy
Diski A çubuğundan B çubuğuna koy
Diski C çubuğundan A çubuğuna koy
Diski C çubuğundan B çubuğuna koy
Diski A çubuğundan B çubuğuna koy
Diski A çubuğundan C çubuğuna koy
Diski B çubuğundan C çubuğuna koy
Diski B çubuğundan A çubuğuna koy
Diski C çubuğundan A çubuğuna koy
Diski B çubuğundan C çubuğuna koy
Diski A çubuğundan B çubuğuna koy
Diski A çubuğundan C çubuğuna koy
Diski B çubuğundan C çubuğuna koy

4 adet disk kullanılan bir durumda n = 1 oluyorsa toplam 3 durum ve çözüm için K1 = 1 olur.

Yine disk sayısının n = 2 olduğu durumda toplam 9 durum ve çözüm için K2 = 3 olur.

n = 3 disk sayısında 27 durum ve çözüm için K3 = 7 olmakta.

Disk sayısı n = 4 olduğunda toplam durum sayısı 81 ve çözüm ise K4 = 15 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.

def hanoi_tower_algorithm(n, x, y, z):
    if n == 1:
        print("Diski %s çubuğundan %s çubuğuna koy" % (x,z))
    else:
        hanoi_tower_algorithm(n-1, x, z, y)
        hanoi_tower_algorithm(1, x, y, z)
        hanoi_tower_algorithm(n-1, y, x, z)

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.

def hanoi_tower_algorithm_main(ndisc):
    # ndisc = Number of Disc
    hanoi_tower_algorithm(ndisc, "A", "B", "C")

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

python -m profile hanoi_tower_algorithm.py

6654 function calls (5121 primitive calls) in 0.078 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     2046    0.000    0.000    0.000    0.000 :0(charmap_encode)
        1    0.000    0.000    0.078    0.078 :0(exec)
     1023    0.062    0.000    0.078    0.000 :0(print)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
     2046    0.016    0.000    0.016    0.000 cp857.py:18(encode)
        1    0.000    0.000    0.078    0.078 hanoi_tower_algorithm.py:1()
   1534/1    0.000    0.000    0.078    0.078 hanoi_tower_algorithm.py:1(hanoi_t
ower_algorithm)
        1    0.000    0.000    0.078    0.078 hanoi_tower_algorithm.py:44(hanoi_
tower_algorithm_main)
        1    0.000    0.000    0.078    0.078 profile:0( at
 0x01DCC2A0, file "hanoi_tower_algorithm.py", line 1>)
        0    0.000             0.000          profile:0(profiler)

Kaynaklar:

Sadri Evren Şeker