Raport z projektu
Przedmiot: Algorytmy i złożoność
PROJEKT: WIEŻE HANOI
Autor: Kamil Adamuszek
Raport z projektu
Przedmiot: Algorytmy i złożoność
PROJEKT: WIEŻE HANOI
Autor: Kamil Adamuszek
1.
Opis problemu wież Hanoi
“W wielkiej świątyni Benares w Hanoi, pod kopułą, która zaznacza środek świata, znajduje się płytka z
brązu, na której umocowane są trzy diamentowe igły, wysokie na łokieć i cienkie jak talia osy. Na jednej z
tych igieł, w momencie stworzenia świata, Bóg umieścił 64 krążki ze szczerego złota. Największy z nich leży
na płytce z brązu, a pozostałe jeden na drugim, idąc malejąco od największego do najmniejszego. Jest to
wieża Brahma. Bez przerwy we dnie i w nocy kapłani przekładają krążki z jednej diamentowej igły na drugą,
przestrzegając niewzruszonych praw Brahma. Prawa te chcą, aby kapłan na służbie brał tylko jeden krążek
na raz i aby umieszczał go na jednej z igieł w ten sposób, by nigdy nie znalazł się pod nim krążek mniejszy.
Wówczas, gdy 64 krążki zostaną przełożone z igły, na której umieścił je Bóg w momencie stworzenia świata,
na jedną z dwóch pozostałych igieł, wieża, świątynia, bramini rozsypią się w proch i w jednym oka mgnieniu
nastąpi koniec świata.”
2.
Rozwiązanie dla 3 krążków
Problem dla 3 krążków można rozwiązać za pomocą algorytmu rekurencyjnego lub iteracyjnego.
Przykład algorytmu rekurencyjnego:
void Hanoi(int k, int s)
{
if (k == 0) return;
Hanoi(k – 1, -s);
Przenies(k, s); // Przenoszenie k-tego krążka od s pozycji
Hanoi(k– 1, -s);
}
Problem ten można rozwiązać za pomocą algorytmu iteracyjnego. Aby tego dokonać należy zauważyć, że
krążki są przemieszczane za pomocą wzoru: przykładowo k-ty krążek jest przenoszony z 1 słupka co
2
k
-2
k-1
o y=(-1)
k+1
, gdzie gdy y= 1 to krążek jest przenoszony na wieżę po swojej prawej stronie, a gdy y= -1
to krążek jest przenoszony na wieżę po swojej lewej stronie.
int il_przenies = pow(il_do_przel) - 1;
for (int j = 1; j <= il_przenies; j++)
{ //Sprawdzanie który krazek ma byc przesuniety
int k = 0;
while (true)
{
int a = pow(k);
int b = a * 2;
//Korzystajac z numeru przeniesienia obliczane jest ktory krazek ma
//zostać przemieszczony. Wykonywane to jest przy wykorzystaniu
// j-2
k
% 2
k+1
==0, gdzie a=2
k
, b=2
k+1
if (((j - a) % b) == 0)
{ //Przesuwanie krazka
kreg[k] += ((k + 1) % 2) ? 2 : 1;
kreg[k] = kreg[k] % 3;
il_przel++;
ofstream plik;
plik.open("wynik.txt", ios::app | ios::ate);
plik << "Przeniesienie " << k + 1 << "-tego krazka na " << kreg[k] + 1 << " slupek" <<endl;
plik.close();
break;
}
k++;
}
3.
Testy dla k krążków i s słupków(wież)
Il. kr.
3 słup.
4 słup.
5 słup.
6 słup. 7 słup. 8 słup.
9 słup.
10 słup. 11 słup.
12 słup.
1
1
1
1
1
1
1
1
1
1
1
2
3
3
3
3
3
3
3
3
3
3
3
7
7
5
5
5
5
5
5
5
5
4
15
15
9
7
7
7
7
7
7
7
5
31
31
15
11
9
9
9
9
9
9
6
63
63
27
17
13
11
11
11
11
11
7
127
127
49
27
19
15
13
13
13
13
8
255
255
93
47
29
21
17
15
15
15
9
511
511
179
85
47
31
23
19
17
17
10
1023
1023
351
159
83
49
33
25
21
19
11
2047
2047
693
307
153
83
51
35
27
23
12
4095
4095
1377
601
291
151
85
53
37
29
13
8191
8191
2743
1187
565
285
151
87
55
39
14
16383
16383
5475
2359
1113
551
283
153
89
57
15
32767
32767
10937
4701
2207
1081
545
283
155
91
16
65535
65535
21861
9383
4393
2139
1067
543
285
157
17
131071 131071
43707
18747
8763
4255
2109
1061
543
287
18
262143 262143
87399
37473
17503
8485
4191
2095
1059
545
4.
Wykresy
0
50000
100000
150000
200000
250000
300000
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18
Il
o
ść
p
rz
e
n
ie
si
e
ń
Ilość krążków
3 słupki
4 słupki
5 słupków
6 słupków
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18
Il
o
ść
p
rz
e
n
ie
si
e
ń
Ilość krążków
7 słupków
8 słupków
9 słupków
10 słupków
11 słupków
12 słupków
5.
Algorytm dla 3 słupków
Wieżę Hanoi z k krążkami oznaczamy przez s
n
. Z wyników testów wynika, że
s
1
=2
1
-1; s
2
=2
2
-1; s
3
=2
3
-1;s
4
=2
4
-1;… Na tej podstawie należy przypuszczam, że s
n
=2
n
-1 dla pewnej liczby
krążków n. Powyższą zależność można sprawdzić indukcyjnie. Wiemy że s
1
=2
1
-1=1, załóżmy że s
n
=2
n
-1, a
więc s
n+1
=2*s
n
+1=2*(2
n
-1)+1=2
(n+1)
-1. Pokazałem zatem że złożoność algorytmu wynosi O(2
n
).
6.
Algorytm dla 4 słupków
Pomimo tego, że dla 4 słupków algorytm zachowuje się w inny sposób niż dla 3 słupków to
złożoność obliczeniowa jest taka sama jak dla 3 słupków. Jest to wynikiem tego, że np. dla n
krążków pierwszym krokiem jest przeniesienie k-1 krążków na inny słupek metodą dla 3 słupków, a
następnie k-tego krążka. Krok ten powtarza się do momentu przeniesienie wszystkich krążków.
7.
Algorytm dla 5 słupków
Analizując wyniki dla 5 słupków otrzymuję poniższy wzór rekurencyjny:
2*n-1
dla n=1,2,3
s
n
=
2*s
n-1
-n+2
dla n=2*k+3
2*s
n-1
-n+3
dla n=2*k+2
Nieudało mi się uprościć tej funkcji rekurencyjnej, ale można zauważyć złożoność algorytmu dla 5
słupków. Na przykład:
S
6
=2*(s
5
)-n+3=2*(2*(s
4
)-n+2)-n+3=2*(2*(2*(s
3
)-n+3)-n+2)-n+3=2*(2*(2*(2*3-1)-n+3)-n+2)-n+3=
=2*(2*(2
2
*3-2-n+3)-n+2)-n+3=2*(2*(2
2
*3-n+1)-n+2)-n+3=2*(2
3
*3-2*n+2-n+2)-n+3=
=2*(2
3
*3-3*n-4)-n+3=2
4
*3-6n+8-n+3=3*2
4
-7n+11
Uogólniając wzór i podpierając się notacją asymptotyczną złożoność algorytmu wynosi
O(3*2
n
)=3*O(2
n
)
8. Wnioski
Algorytm dla 3 słupków ma złożoność obliczeniową O(2
n
). Wraz z wzrostem ilości słupków
wydajność algorytmu wzrasta, a ilość potrzebnych przełożeń maleje. Nie znaleziono dotychczas algorytmu,
który dokonał by przełożenia wszystkich krążków w minimalnej liczbie ruchów. Akceptowane więc są
wszystkie rozwiązania, które dadzą wynik nie gorszy od naszego i będą miały nie gorszą złożoność.