Towers Of Hanoi

Menara Hanoi

Menara Hanoi (juga disebut Menara Brahma atau Lucas Tower, dan terkadang pluralised) adalah permainan matematika atau teka-teki . Ini terdiri dari tiga batang, dan sejumlah disk dengan ukuran yang berbeda yang dapat meluncur ke batang apapun. Teka-teki ini dimulai dengan disk dalam tumpukan rapi dalam urutan dari ukuran pada satu tongkat, yang terkecil di bagian atas, sehingga membuat bentuk kerucut.

Tujuan dari teka-teki adalah untuk memindahkan seluruh tumpukan ke batang lain, mematuhi aturan berikut:

Hanya satu disk dapat dipindahkan pada suatu waktu.
Setiap langkah terdiri dari mengambil disk atas dari salah satu batang dan menggesernya ke batang yang lain, di atas disk lain yang mungkin sudah ada pada batang itu.
Disk Tidak dapat ditempatkan di atas sebuah disk lebih kecil.

Dengan tiga disk, teka-teki dapat diselesaikan dalam tujuh langkah.

Asal

Teka-teki ini ditemukan oleh Perancis matematika Edouard Lucas pada tahun 1883. Ada legenda tentang India candi yang berisi sebuah ruangan besar dengan tiga waktu yang dikenakan di posting di dalamnya dikelilingi oleh 64 disk emas. Brahmana imam, dengan memerankan komando ramalan kuno, telah memindahkan disk ini, sesuai dengan aturan dari teka-teki, sejak saat ituTeka-teki ini karena itu juga dikenal sebagai Menara Brahma teka-teki. Menurut legenda, ketika langkah terakhir dari teka-teki selesai, dunia akan berakhir. ^[2] Tidak jelas apakah Lucas menemukan legenda ini atau terinspirasi olehnya.

Jika legenda itu benar, dan jika imam mampu memindahkan disk dengan laju satu per detik, dengan menggunakan jumlah terkecil bergerak, itu akan membawa mereka 2 ⁶⁴ -1 detik atau sekitar 585 miliar tahun atau 18.446.744.073.709.551.615 bergantian sampai akhir.
Ada banyak variasi pada legenda ini. Misalnya, dalam beberapa tellings, candi adalah biara dan para imam adalah biarawan .. Kuil atau biara dapat dikatakan di berbagai belahan dunia - termasuk Hanoi, Vietnam , dan mungkin terkait dengan agama Dalam beberapa versi, unsur lain diperkenalkan, seperti fakta bahwa menara ini dibuat pada awal dunia, atau bahwa para imam atau biarawan dapat membuat hanya satu langkah per hari.

Teka-teki bisa dimainkan dengan jumlah disk, meskipun versi mainan banyak memiliki sekitar tujuh sampai sembilan dari mereka. Permainan ini tampaknya tidak mungkin untuk pemula banyak, namun dipecahkan dengan sederhana algoritma . Jumlah langkah yang diperlukan untuk memecahkan teka-teki Menara Hanoi adalah 2 ⁿ -1, dimana n adalah jumlah disk.
Solusi berikut adalah solusi sederhana untuk teka-teki mainan.
Alternatif bergerak antara bagian terkecil dan sepotong non-terkecil. Ketika memindahkan bagian terkecil, selalu memindahkannya ke posisi berikutnya dalam arah yang sama (ke kanan jika jumlah awal potongan bahkan, ke kiri jika jumlah awal potongan anehJika tidak ada posisi menara ke arah yang dipilih, memindahkan potongan ke ujung, tapi kemudian terus bergerak ke arah yang benar. Misalnya, jika Anda mulai dengan tiga potong, Anda akan memindahkan bagian terkecil ke ujung, lalu lanjutkan ke arah kiri setelah itu. Ketika gilirannya adalah untuk memindahkan bagian non-terkecil, hanya ada satu langkah hokum, Melakukan hal ini akan menyelesaikan teka-teki menggunakan jumlah paling sedikit bergerak untuk melakukannya.
Barangkali perlu dicatat bahwa ini dapat ditulis sebagai satu set mencolok elegan aturan:
Bergantian antara yang terkecil dan mendatang terkecil disk, ikuti langkah-langkah untuk kasus yang sesuai:
Untuk bahkan jumlah disk:

melakukan langkah hukum antara pasak A dan B
melakukan langkah hukum antara pasak A dan C
melakukan langkah hukum antara pasak B dan C
ulangi sampai lengkap

Untuk ganjil disk:

melakukan langkah hukum antara pasak A dan C
melakukan langkah hukum antara pasak A dan B
melakukan langkah hukum antara pasak B dan C
ulangi sampai lengkap

Dalam setiap kasus, sebanyak 2 ⁿ -1 bergerak yang dibuat.
Cara lain untuk menghasilkan yang optimal unik iteratif solusi, adalah untuk nomor disk 1 sampai n, terbesar ke terkecil. Jika n ganjil, langkah pertama adalah dari Start ke Finish pasak, dan jika n adalah bahkan langkah pertama adalah dari Start untuk pasak Menggunakan.
Sekarang, tambahkan batasan bahwa tidak ada disk yang aneh dapat ditempatkan langsung pada disk aneh, dan tidak ada disk bahkan dapat ditempatkan langsung pada disk bahkan. Dengan kendala ekstra, dan aturan yang jelas tidak pernah melepas langkah terakhir, hanya ada satu gerakan di setiap kesempatan Urutan langkah yang unik adalah solusi optimal untuk masalah setara dengan iteratif solusi yang dijelaskan di atas.
Sebuah kunci untuk memecahkan teka-teki ini adalah untuk mengakui bahwa hal itu dapat diatasi dengan memecah masalah ke kumpulan masalah yang lebih kecil dan lebih jauh melanggar masalah tersebut ke dalam masalah yang lebih kecil sampai solusi tercapaiProsedur berikut menunjukkan pendekatan ini.

label pasak A, B, C-label ini dapat bergerak dengan langkah yang berbeda
mari n menjadi jumlah cakram
nomor cakram dari 1 (terkecil, paling atas) dengan n (terbesar, paling bawah)

Untuk memindahkan cakram n dari A ke pasak pasak C:

bergerak n -1 cakram dari A ke B. Ini disk daun n sendirian di pasak A
memindahkan n piringan dari A ke C
bergerak n -1 cakram dari B ke C sehingga mereka duduk di disc n

Di atas adalah algoritma rekursif : untuk melakukan langkah 1 dan 3, menerapkan algoritma yang sama lagi untuk n -1. Seluruh prosedur adalah jumlah terbatas langkah-langkah, karena di beberapa titik algoritma akan diminta untuk n = 1. Langkah ini, bergerak dari satu disk pasak pasak A ke B, adalah sepele. Pendekatan ini dapat diberikan formalisme matematika yang ketat dengan teori pemrograman dinamis dan sering digunakan sebagai contoh rekursi ketika mengajar pemrograman.
Seperti di banyak teka-teki matematika, menemukan solusi menjadi lebih mudah dengan memecahkan masalah yang sedikit lebih umum: bagaimana memindahkan menara h (h = tinggi) disk dari pasak awal A (f = dari) ke tujuan pasak C (t = untuk), B menjadi pasak ketiga tersisa dan dengan asumsi t ≠ f . Pertama, amati bahwa masalahnya adalah simetris untuk permutasi dari nama-nama pasak ( simetris kelompok S ₃ ). Jika solusi ini dikenal bergerak dari A ke pasak pasak C, maka, dengan mengganti nama pasak, solusi yang sama dapat digunakan untuk setiap pilihan lain untuk memulai dan pasak tujuan. Jika hanya ada satu disk (atau bahkan tidak sama sekali), masalahnya adalah sepele. If h=1, Jika h = 1, maka cukup memindahkan disk tersebut dari A ke pasak pasak C. Jika h> 1, maka suatu tempat di sepanjang urutan bergerak, disk terbesar harus pindah dari A ke pasak pasak lain, sebaiknya untuk mematok C. Situasi satunya yang memungkinkan langkah ini adalah ketika semua h-1 lebih kecil disk berada di pasak B. Oleh karena itu, pertama semua h-1 disk yang lebih kecil harus pergi dari A B ke. Selanjutnya memindahkan disk terbesar dan akhirnya memindahkan h-1 disk lebih kecil dari B ke pasak pasak C. Kehadiran disk terbesar tidak menghambat setiap langkah dari h-1 disk lebih kecil dan untuk sementara dapat diabaikan. Sekarang masalahnya berkurang untuk bergerak h-1 disk dari satu wadah ke satu sama lain, pertama dari A B ke B dan kemudian dari ke C, tetapi metode yang sama dapat digunakan dua kali dengan mengganti nama pasak. Strategi yang sama dapat digunakan untuk mengurangi masalah h-1 untuk h-2, h-3, dan seterusnya sampai hanya satu disk yang tersisaIni disebut rekursi. Algoritma ini dapat schematized sebagai berikutMengidentifikasi disk di urutan ukuran meningkat alam nomor dari 0 sampai dengan tetapi tidak termasuk jam. Hence disk 0 is the smallest one and disk h-1 the largest one. Oleh karena itu disk 0 adalah yang terkecil dan disk h-1 yang terbesar.
Berikut ini adalah prosedur untuk memindahkan menara disk jam dari pasak A ke C pasak, dengan B menjadi pasak ketiga tersisa:

Langkah 1: Jika h> 1 maka pertama menggunakan prosedur ini untuk memindahkan h-1 disk lebih kecil dari A ke pasak pasak B.
Langkah 2: Sekarang disk terbesar, yaitu hard disk h-1 dapat dipindahkan dari A ke pasak pasak C.
Langkah 3: Jika h> 1 maka lagi menggunakan prosedur ini untuk memindahkan h-1 disk lebih kecil dari B ke pasak pasak C.

Dengan cara induksi matematika , hal ini mudah dibuktikan bahwa prosedur di atas mengharuskan jumlah minimal bergerak mungkin, dan bahwa solusi yang dihasilkan adalah satu-satunya dengan jumlah minimal bergerak. Menggunakan hubungan kambuh , persis jumlah langkah yang membutuhkan solusi ini dapat dihitung dengan: 2 ^ h - 1

. Hasil ini diperoleh dengan mencatat bahwa langkah 1 dan 3 mengambil bergerak, dan langkah 2 mengambil satu gerakan, memberikan $T_h = 2T_ {h-1} + 1$ . .

Daftar bergerak untuk sebuah menara yang dilakukan dari satu wadah ke yang lain, seperti yang dihasilkan oleh algoritma rekursif memiliki keteraturan banyak. Bila dihitung bergerak mulai dari 1, ordinal disk yang akan dipindahkan selama m bergerak adalah jumlah m kali dapat dibagi dengan 2. Oleh karena itu setiap gerakan aneh melibatkan disk terkecil. Hal ini juga dapat diamati bahwa melintasi disk terkecil f pasak, t, r, f, t, r, dll untuk ketinggian aneh menara dan melintasi f pasak, r, t, f, r, t, dll bahkan untuk ketinggian menara Ini menyediakan algoritma berikut, yang lebih mudah, dilakukan dengan tangan, daripada algoritma rekursif.
Dalam bergerak alternatif:

memindahkan disk terkecil ke pasak itu tidak baru datang dari.
memindahkan disk lain secara hukum (akan ada satu kemungkinan saja)

Untuk langkah pertama, disk terkecil pergi ke pasak t jika h adalah aneh dan untuk mematok r jika h bahkan.
Juga mengamati bahwa:

Disk yang ordinals memiliki bahkan bergerak paritas dalam arti yang sama seperti disk terkecil.
Disk yang ordinals memiliki langkah paritas ganjil dalam arti yang berlawanan.
Jika h adalah bahkan, pasak ketiga tersisa selama bergerak berturut-turut adalah t, r, f, t, r, f, dll
Jika h adalah aneh, pasak ketiga tersisa selama bergerak berurutan adalah r, t, f, r, t, f, dll

Dengan pengetahuan ini, satu set disk di tengah solusi optimal dapat dipulihkan dengan informasi negara tidak lebih dari posisi setiap disk:

Panggil bergerak rinci di atas 'alami' bergerak disk.
Periksa disk atas terkecil yang tidak disk 0, dan perhatikan apa yang satu-satunya (hukum) bergerak akan menjadi: (jika tidak ada disk tersebut, maka kita baik pada langkah pertama atau terakhir).
Jika langkah yang 'alami' disk yang bergerak, maka disc tidak digerakkan sejak pindah 0 disc terakhir, dan langkah yang harus diambil.
Jika langkah yang tidak 'alami' disk yang bergerak, kemudian bergerak 0 disk.

Posisi Disk dapat ditentukan lebih langsung dari biner (basis 2) representasi dari jumlah bergerak (keadaan awal menjadi langkah # 0, dengan semua, angka 0 dan keadaan akhir menjadi # 2 ⁿ -1, dengan semua angka 1), menggunakan aturan berikut:

Ada satu digit biner ( bit ) untuk setiap disk
Nilai 0 menunjukkan bahwa disk terbesar adalah pada pasak awal, sementara 1 menunjukkan bahwa itu ada di pasak akhir.
Bitstring itu dibaca dari kiri ke kanan, dan tiap bit dapat digunakan untuk menentukan lokasi disk yang sesuai.
Sebuah bit dengan nilai yang sama dengan yang sebelumnya berarti bahwa disk yang bersangkutan akan ditumpuk di atas disk sebelumnya pada pasak yang sama.

(Artinya: urutan lurus dari 1 atau 0 berarti bahwa disk yang sesuai semua pada pasak yang sama).

Sebuah bit dengan nilai yang berbeda dengan yang sebelumnya berarti bahwa disk yang sesuai adalah satu posisi ke kiri atau kanan yang sebelumnya. Apakah itu kiri atau kanan ditentukan oleh aturan ini:

Asumsikan bahwa pasak awal adalah di sebelah kiri dan pasak terakhir adalah di sebelah kanan.
Juga menganggap "membungkus" - sehingga jumlah pasak yang tepat sebagai salah satu pasak "kiri" dari pasak kiri, dan sebaliknya.
Misalkan n jumlah disk yang lebih besar yang terletak di pasak yang sama seperti disk pertama mereka yang lebih besar dan tambahkan 1 jika disk terbesar adalah pada pasak kiri. Jika n adalah bahkan, disk terletak satu pasak ke kiri, jika n adalah ganjil, disk terletak satu pasak ke kanan.

Sebagai contoh, dalam sebuah 8-disk Hanoi:

Pindahkan 0

Disk terbesar adalah 0, sehingga pada pasak (awal) kiri.
Semua disk lainnya adalah 0 juga, sehingga mereka ditumpuk di atasnya. Oleh karena itu semua disk berada di pasak awal.

Pindahkan 2 ⁸ -1

Disk terbesar adalah 1, sehingga pada pasak (akhir) benar.
Semua disk lainnya 1 juga, sehingga mereka ditumpuk di atasnya. Oleh karena itu semua disk berada di pasak akhir dan teka-teki selesai.

Pindahkan 011011000 = 216 ₁₀

Disk terbesar adalah 1, sehingga pada pasak (akhir) benar.
Disk kedua adalah juga 1, sehingga ditumpuk di atasnya, di pasak yang tepat.
Disk tiga adalah 0, sehingga pada pasak yang lain. Sejak n adalah ganjil (n = 3), adalah salah satu pasak ke kanan, yaitu pada pasak kiri.
Disk four is 1, Disk empat adalah 1, sehingga pada pasak yang lain. Since n is even(n=2), it is one peg to the left, ie on the right peg. Sejak n genap (n = 2), adalah salah satu pasak ke kiri, yaitu pada pasak yang tepat.
Disk lima adalah juga 1, sehingga ditumpuk di atasnya, di pasak yang tepat.
Disk enam adalah 0, sehingga pada pasak yang lain. Sejak n adalah ganjil (n = 5), disk adalah salah satu pasak ke kanan, yaitu pada pasak kiri.
Disk tujuh dan delapan juga 0, sehingga mereka ditumpuk di atasnya, pada pasak kiri.

Sumber dan pasak tujuan untuk pindah ke m juga dapat ditemukan elegan dari representasi biner dari m menggunakan operasi bitwise . Untuk menggunakan sintaks dari bahasa pemrograman C , memindahkan m adalah dari pasak (m&m-1)%3 untuk mematok ((m|m-1)+1)%3 , di mana disk dimulai pada pasak 0 dan selesai pada pasak 1 atau 2 menurut seperti apakah jumlah disk adalah genap atau ganjilFormulasi lain adalah dari pasak (m-(m&-m))%3 untuk mematok (m+(m&-m))%3 .
Selanjutnya disk untuk dipindahkan ditentukan oleh berapa kali hitungan bergerak (m) dapat dibagi oleh 2 (yaitu jumlah bit nol di bagian kanan), menghitung langkah pertama sebagai 1 dan mengidentifikasi disk dengan angka 0 , 1, 2 dll dalam rangka ukuran meningkat. Hal ini memungkinkan implementasi non-rekursif komputer yang sangat cepat untuk menemukan posisi disk setelah bergerak m tanpa referensi untuk setiap langkah sebelumnya atau distribusi disk.
Para hitungan nol tertinggal (ctz) operasi, yang menghitung jumlah angka nol berturut-turut pada akhir bilangan biner, memberikan solusi sederhana untuk masalah: disk diberi nomor dari nol, dan pada m bergerak, disk jumlah ctz (m) dipindahkan jarak minimum yang mungkin ke kanan (berputar-putar kembali sekitar ke kiri sesuai kebutuhan). ^[9]
Dalam sistem Gray, nomor disajikan dalam kombinasi biner 0 dan 1, tetapi bukan menjadi standar sistem angka posisi , kode Gray beroperasi pada premis bahwa setiap nilai berbeda dari pendahulunya dengan hanya satu (dan tepat satu) sedikit berubah . Jumlah bit yang ada dalam kode Gray adalah penting, dan nol terkemuka tidak opsional, tidak seperti dalam sistem posisional.
Jika salah satu jumlah dalam kode Gray dengan ukuran sedikit sama dengan jumlah disk di Tower tertentu Hanoi, dimulai dari nol, dan menghitung, lalu bit berubah setiap langkah sesuai dengan disk untuk bergerak, di mana paling tidak-signifikan- bit disk terkecil dan paling signifikan-bit adalah yang terbesar.

Menghitung bergerak dari 1 dan mengidentifikasi disk dengan nomor yang dimulai dari 0 untuk ukuran meningkat, ordinal disk yang akan dipindahkan selama m bergerak adalah jumlah m kali dapat dibagi dengan 2.

Teknik ini mengidentifikasi yang disk untuk bergerak, tetapi tidak di mana untuk memindahkannya ke. Untuk disk terkecil selalu ada dua kemungkinan. Untuk disk lain selalu ada satu kemungkinan, kecuali bila semua disk berada di pasak yang sama, tetapi dalam hal yang baik itu adalah disk terkecil yang harus dipindahkan atau tujuan telah tercapai. Untungnya, terdapat aturan yang tidak mengatakan di mana untuk memindahkan disk terkecilMisalkan f menjadi pasak awal, t tujuan pasak dan r pasak ketiga tersisa. Jika jumlah disk aneh, siklus disk terkecil sepanjang pasak dalam urutan f-> t-> r-> f-> t-> r, dll Jika jumlah disk bahkan, ini harus dibalik: f-> r-> t-> f-> r-> t dll

http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/TowerOfHanoi_RulerSolution.png/320px-TowerOfHanoi_RulerSolution.png

Pembagian pada penguasa Imperial khas dapat bertindak sebagai kunci untuk urutan bergerak disk.

Sebuah solusi visual yang dapat ditemukan dengan mencermati penguasa dengan pengukuran kekaisaran. ^[11] Ini biasanya dibagi lagi menjadi tanda semakin kecil dari 1 inci, 1/2 inch, 1/4 inci, 1/8 inci, 1/16 inci dan 1/32 divisi inci. Ini dapat dianggap sesuai dengan cakram semakin kecil.
Dimulai dengan divisi terkecil yang sesuai dengan disk terkecil, setiap langkah penguasa yang menunjukkan cakram akan dipindahkan berikutnya. Seorang penguasa umum dengan divisi 1/32 inci dapat digunakan untuk memecahkan teka-teki Menara Hanoi dengan sampai enam disc.
Catatan bahwa ini hanya menyediakan kunci untuk urutan gerakan disk, bukan arah mereka. Seperti disebutkan sebelumnya, disk terkecil harus selalu bersepeda melalui pasak A, B, C, lalu kembali ke A (atau C, B, A, lalu kembali ke C).
Permainan ini dapat direpresentasikan oleh diarahkan grafik , node yang mewakili distribusi disk dan ujung-ujungnya mewakili bergerakUntuk satu disk, grafik adalah segitiga:

Grafik untuk 2 disk adalah 3 segitiga disusun dalam segitiga yang lebih besar:

Node pada simpul dari segitiga terluar mewakili distribusi dengan semua disk pada pasak yang sama.
Untuk h +1 disk, mengambil grafik disk jam dan mengganti setiap segitiga kecil dengan grafik selama 2 disk.
Untuk 3 disk grafik adalah:

memanggil pasak a, b dan c
daftar disk posisi dari kiri ke kanan dalam urutan ukuran meningkat

Sisi-sisi segitiga terluar mewakili cara-cara terpendek bergerak menara dari satu wadah ke satu sama lain. Tepi di tengah sisi-sisi segitiga terbesar merupakan langkah dari disk terbesar. Tepi di tengah sisi setiap segitiga yang lebih kecil berikutnya merupakan langkah dari setiap disk yang lebih kecil berikutnya. The Sisi-sisi dari segitiga terkecil mewakili bergerak dari disk terkecil.

http://upload.wikimedia.org/wikipedia/commons/thumb/8/80/Hanoi-Graph-7.svg/220px-Hanoi-Graph-7.svg.png

Grafik permainan tingkat 7 menunjukkan keterkaitan dengan Segitiga Sierpinski

Secara umum, untuk teka-teki dengan disk n, ada 3 node ⁿ dalam grafik; setiap node memiliki tiga tepi ke node lain, kecuali tiga node sudut, yang memiliki dua: ia selalu mungkin untuk memindahkan disk terkecil ke yang dari dua pasak lainnya, dan adalah mungkin untuk memindahkan satu disk antara dua pasak kecuali dalam situasi di mana semua disk ditumpuk pada satu pasak. Node sudut mewakili tiga kasus di mana semua disk ditumpuk pada satu pasak. Diagram untuk n + 1 disk diperoleh dengan mengambil tiga salinan dari n-disk diagram-masing-masing yang mewakili seluruh negara bagian dan bergerak dari disk yang lebih kecil untuk satu posisi tertentu yang terbesar baru disk dan bergabung dengan mereka di sudut-sudut dengan tiga baru tepi, yang mewakili tiga peluang hanya untuk memindahkan disk terbesar. Jumlah yang dihasilkan sehingga memiliki 3 ⁿ⁺¹ node dan masih memiliki tiga sudut yang tersisa hanya dua sisi.
Sebagai disk yang lebih banyak, representasi grafik dari permainan akan menyerupai Fractal angka, segitiga Sierpinski . Jelas bahwa sebagian besar posisi dalam teka-teki tidak akan pernah tercapai bila menggunakan solusi sesingkat mungkin, memang, jika para imam dari legenda menggunakan solusi yang mungkin terpanjang (tanpa kembali mengunjungi posisi apapun) akan membawa mereka 3 ^64-1 bergerak, atau lebih dari 10 ²³ tahun.
Cara non-berulang terpanjang selama tiga disk dapat divisualisasikan dengan menghapus tepi yang tidak digunakan:

Kebetulan, jalan ini tidak berulang terpanjang dapat diperoleh dengan melarang semua bergerak dari b ke.
Surat edaran jalur Hamiltonian untuk tiga disk adalah:

Grafik jelas menunjukkan bahwa:

Dari setiap distribusi sewenang-wenang dari disk, ada tepat satu cara terpendek untuk memindahkan semua disk ke salah satu dari tiga pasak.
Antara setiap pasangan distribusi sewenang-wenang disk ada satu atau dua jalur terpendek yang berbeda.
Dari setiap distribusi sewenang-wenang dari disk, ada satu atau dua jalan yang berbeda selfcrossing terpanjang non memindahkan semua disk untuk salah satu dari tiga pasak.
Antara setiap pasangan distribusi sewenang-wenang disk ada satu atau dua yang berbeda terpanjang jalur selfcrossing non.
Misalkan N _h adalah jumlah jalur non selfcrossing untuk memindahkan menara disk h dari satu wadah ke yang lain. Then: Kemudian:

N ₁ = 2 N ₁ = 2
N _h₊₁ = ( N _h ) ² + ( N _h ) ³ . N _h₊₁ = (N _h) ² + (N _h) ^3.
Sebagai contoh: N ₈ ≈ 1,5456 × 10 ⁷⁹⁵

Menara Hanoi sering digunakan dalam penelitian psikologis pada pemecahan masalah . Ada juga ada varian dari tugas ini disebut Menara London untuk diagnosis neuropsikologi dan pengobatan fungsi eksekutif.
Menara Hanoi juga digunakan sebagai skema rotasi Backup data komputer saat melakukan Backup di mana beberapa kaset / media yang terlibat.
Sebagaimana disebutkan di atas, Menara Hanoi adalah populer untuk mengajar algoritma rekursif untuk siswa pemrograman dimulai. Sebuah versi bergambar dari teka-teki ini diprogram ke dalam emacs editor, diakses dengan mengetik Mx hanoi.
Menara Hanoi juga digunakan sebagai ujian oleh neuropsychologists mencoba untuk mengevaluasi lobus frontal defisit.
Sebuah generalisasi penasaran dari tujuan asli dari teka-teki adalah mulai dari konfigurasi tertentu dari disk dimana semua disk belum tentu pada pasak yang sama, dan tiba di sejumlah minimal bergerak di lain konfigurasi tertentu. Secara umum bisa sangat sulit untuk menghitung urutan terpendek bergerak untuk memecahkan masalah ini Solusi diusulkan oleh Andreas Hinz, dan didasarkan pada pengamatan bahwa dalam urutan terpendek bergerak, disk terbesar yang harus dipindahkan (jelas orang dapat mengabaikan semua disk terbesar yang akan menempati pasak yang sama baik di awal dan konfigurasi akhir) akan bergerak baik tepat satu kali atau persis dua kali.

Matematika yang berhubungan dengan masalah ini umum menjadi lebih menarik ketika seseorang mempertimbangkan jumlah rata-rata bergerak dalam urutan terpendek bergerak antara dua konfigurasi disk yang awal dan akhir yang dipilih secara acak. Hinz dan Chan Hat-Tung independen menemukan ,bahwa jumlah rata-rata bergerak dalam n-disk Menara diberikan oleh formula yang tepat berikut:

$\ Frac {466} {885} \ cdot 2 ^ n - \ frac {1} {3} - \ frac {3} {5} \ cdot \ left (\ frac {1} {3} \ right) ^ n + \ left (\ frac {12} {29} + \ frac {18} {1003} \ sqrt {17} \ right) \ left (\ frac {5 + \ sqrt {17}} {18} \ right) ^ n + \ left (\ frac {12} {29} - \ frac {18} {1003} \ sqrt {17} \ right) \ left (\ frac {5 - \ sqrt {17}} {18} \ right) ^ n.$

Perhatikan bahwa untuk n yang cukup besar, hanya suku pertama dan kedua tidak konvergen ke nol, jadi kami mendapatkan ekspresi asimtotik : $466/885 \ cdot 2 ^ n - 1/3 + o (1)$ , as , Sebagai $n \ to \ infty$ . Dengan demikian, secara intuitif kita bisa menafsirkan fraksi $466/885 \ approx 52,6 \%$ sebagai mewakili rasio satu tenaga kerja harus melakukan ketika pergi dari konfigurasi secara acak dipilih untuk konfigurasi lain yang dipilih secara acak, relatif terhadap kesulitan karena harus menyeberangi "paling sulit" jalan panjang yang melibatkan bergerak semua disk dari satu wadah ke wadah lainnya. Penjelasan alternatif untuk penampilan 466 konstan / 885, serta algoritma baru dan agak lebih baik untuk menghitung jalur terpendek, diberikan oleh Romik.
Siklik Hanoi adalah variasi dari Hanoi di mana setiap disk harus bergerak ke arah siklik yang sama, dalam banyak kasus, searah jarum jam. Sebagai contoh, diberi pasak tiga standar set-up, disk diberikan dapat dipindahkan dari pasak A ke B pasak, kemudian dari B ke C, C ke A, dll Hal ini dapat diselesaikan dengan menggunakan dua prosedur yang saling rekursif:
Untuk memindahkan cakram n searah jarum jam dari A ke pasak pasak C:

bergerak n - 1 cakram searah jarum jam dari A ke C
memindahkan disk # n dari A ke B
bergerak n - 1 cakram berlawanan dari C ke A
memindahkan disk # n dari B ke C
bergerak n - 1 cakram searah jarum jam dari A ke C

Untuk memindahkan cakram n berlawanan dari pasak pasak A ke C:

bergerak n - 1 cakram searah jarum jam dari A ke B
memindahkan disk # n dari A ke C
bergerak n - 1 cakram searah jarum jam dari B ke C

Meskipun versi tiga pasak memiliki solusi rekursif sederhana seperti diuraikan di atas, solusi optimal untuk masalah Menara Hanoi dengan empat pasak (disebut teka-teki Reve ini), mari pasak saja lebih, masih merupakan masalah terbuka . Ini adalah contoh yang baik bagaimana masalah sederhana dipecahkan dapat dibuat secara dramatis lebih sulit dengan sedikit melonggarkan salah satu kendala masalah.
Kenyataan bahwa masalah dengan empat atau lebih pasak merupakan masalah terbuka tidak berarti bahwa tidak ada algoritma untuk menemukan (semua) solusi optimal. Cukup mewakili permainan dengan sebuah grafik diarahkan, node menjadi distribusi disk dan ujung-ujungnya menjadi bergerak dan menggunakan pencarian luas pertama untuk menemukan satu (atau semua) jalan terpendek (s) bergerak menara dari satu wadah ke satu sama lain. Namun, bahkan cerdas diimplementasikan pada komputer tercepat sekarang tersedia, algoritma ini tidak menyediakan cara untuk secara efektif menghitung solusi untuk sejumlah besar disk, program ini akan membutuhkan lebih banyak waktu dan memori daripada yang tersediaOleh karena itu, bahkan memiliki sebuah algoritma, itu masih belum diketahui berapa banyak bergerak solusi optimal memerlukan dan berapa banyak solusi optimal untuk 1000 ada 10 disk dan pasak.
Meskipun tidak diketahui secara pasti berapa banyak bergerak harus dilakukan, ada beberapa hasil asimtotik. Ada juga "dianggap optimal solusi" yang diberikan oleh algoritma Frame-Stewart, ditemukan secara independen oleh Frame dan Stewart pada tahun 1941. Para terbuka terkait dugaan Frame-Stewart mengklaim bahwa algoritma Frame-Stewart selalu memberikan solusi optimal. Secara optimum algoritma Frame-Stewart telah diverifikasi komputasi selama 4
Untuk varian lain dari empat pasak Menara Hanoi masalah, lihat kertas survei Paulus Stockmeyer itu.
Algoritma Frame-Stewart, memberikan solusi-mungkin optimal untuk empat (atau bahkan lebih) pasak, diuraikan di bawah ini:

menjadi jumlah disk.
adalah jumlah pasak.
menjadi jumlah minimum bergerak diperlukan untuk mentransfer disk n menggunakan pasak r

Algoritma ini dapat digambarkan secara rekursif:

untuk pasak tunggal selain awal atau pasak tujuan, mengambil moves. bergerak.
Tanpa mengganggu pasak yang sekarang berisi atas disks, transfer the remaining disk, mentransfer sisa disk ke pasak tujuan, hanya menggunakan sisa pegs, pasak, mengambil bergerak.
Finally, transfer the top Akhirnya, transfer atas disks to the destination peg, taking disk ke pasak tujuan, mengambil moves. bergerak.

Seluruh proses memakan waktu

bergerak. Oleh karena itu, hitungan

harus memilih yang kuantitas ini adalah minimum.
Dianggap optimal, dan tidak ada tandingan diketahui.
US paten nomor 7.566.057 diberikan kepada Victor Mascolo mengungkapkan multistack Menara Hanoi teka-teki dengan dua atau lebih tumpukan dan pasak dua kali lebih banyak tumpukan. Setelah dimulai pada pasak khusus, menggantikan tumpukan masing-masing dan digantikan oleh tumpukan warna yang berbeda pada yang lain pasak ketika teka-teki ini dipecahkan. Disk dari satu warna lain juga memiliki pasak yang mengecualikan semua warna lain, sehingga ada tiga pasak tersedia untuk setiap disk warna, dua yang dibagi dengan warna lain, dan satu yang tidak dibagi. Di pasak bersama, disk tidak dapat ditempatkan pada disk berwarna yang berbeda dengan ukuran yang sama, kemungkinan yang tidak timbul dalam teka-teki standar.
Permainan multistack paling sederhana, Menara Hanoi (2 × 4), memiliki dua tumpuk dan empat pasak, dan memerlukan 3 [T (n)] bergerak untuk memecahkan mana T (n) adalah jumlah langkah yang diperlukan untuk memecahkan setumpuk tunggal klasik disk n. Permainan hasil dalam mode jungkat-jungkit dengan seri lama dan lebih lama dari gerakan yang bergantian antara warna. Ini menyimpulkan dengan cara jungkat-jungkit terbalik dengan seri seperti lebih pendek dan lebih pendek bergerak. Dimulai dengan seri kedua dari tiga bergerak, seri ini alternatif bergerak ganda panjang untuk paruh pertama pertandingan, dan panjang yang dibelah dua karena permainan menyimpulkan. Solusinya melibatkan bersarang algoritma cocok untuk Menara Hanoi ke suatu algoritma yang menunjukkan kapan untuk beralih antara warna. Bila ada k tumpukan disk n masing-masing dalam sebuah game, dan k> 2, membutuhkan k [T (n)] + T (n - 1) + 1 langkah untuk merelokasi mereka.
Penambahan pasak universal yang terletak di pusat terbuka untuk disk dari semua tumpukan ini mengkonversi Menara Hanoi multistack teka-teki ke teka-teki multistack Reve sebagai dijelaskan di bagian sebelumnya. Dalam permainan ini setiap tumpukan dapat bergerak di antara empat pasak, kombinasi yang sama dari tiga dalam 2 × 4 game ditambah pasak yang universal pusatPermainan sederhana seperti ini (2 × 5) memiliki dua tumpuk dan lima pasak. Solusi conjectured menjadi Interlocks optimal solusi optimal dari 2 × 4 teka-teki dengan solusi optimal dianggap teka-teki Reve itu. Dibutuhkan R (n) + 2 R (n - 1) + 2 gerakan, dimana R (n) adalah jumlah bergerak dalam larutan Reve yang optimal dianggap untuk setumpuk disk n.

Contoh Source Code Towers Of Hanoi :

/**

* TowersOfHanoi.java

* Created by Stijn Strickx on Aug. 12 2006

import java.io.*;

public class TowersOfHanoi {

static int moves = 0;

static int totalDisks = 0;

public static void main(String[] arguments) throws java.io.IOException {

int disks;

char fromPole = 'A';

char withPole = 'B';

char toPole = 'C';

disks = getNumber("\nHow many disks are there on the tower? ");

totalDisks = disks;

if(totalDisks > 10){

System.out.println("Working...");

}

FileOutputStream fos = new FileOutputStream("TowersOfHanoiSolution.txt");

PrintStream ps = new PrintStream(fos);

solveHanoi(disks, fromPole, toPole, withPole, ps);

ps.close();

System.out.println();

System.out.println("\nAmount of moves: " + moves + "\n");

System.out.print("You can now access the TowersOfHanoiSolution.txt file");

System.out.println(" which is in the same directory as the .class file of this program.");

}

static void solveHanoi(int disks, char fromPole, char toPole, char withPole, PrintStream ps) {

if (disks >= 1) {

solveHanoi(disks-1, fromPole, withPole, toPole, ps);

moveDisk(fromPole, toPole, ps);

solveHanoi(disks-1, withPole, toPole, fromPole, ps);

}

static void moveDisk(char fromPole, char toPole, PrintStream ps) {

moves++;

if(totalDisks <= 10){

System.out.print("Move from " + fromPole + " to " + toPole + ". ");

ps.print("Move from " + fromPole + " to " + toPole + ". ");

if (moves%4 == 0){

System.out.println();

ps.println();

}

else {

ps.print("Move from " + fromPole + " to " + toPole + ". ");

if (moves%4 == 0){

ps.println();

}

static int getNumber(String question) throws java.io.IOException {

String theNumber;

int number = 0;

BufferedReader in = new BufferedReader (new InputStreamReader(System.in));

System.out.print(question);

theNumber = in.readLine();

System.out.println();

number = Integer.parseInt(theNumber);

return number;

}

Courtusey of Google Wikipedia,..

Cari Blog Ini

opalrock

Towers Of Hanoi

Asal

Komentar

Posting Komentar

Postingan populer dari blog ini

Tugase NOval rekkk..