Menara Hanoi adalah contoh klasik dari kasus yang diselesaikan dengan teknik

Permasalahan Menara Hanoi

Teka-teki Menara Hanoi merupakan salah satu persoalan klasik dalam bidang studi Artificial Intelligence [AI]. Problema ini dapat diilustrasikan seperti berikut, terdapat 3 atau lebih cakram yang disusun sebagai kondisi awal [initial state]. Sasaran [goal] dari kasus ini adalah mendapatkan suatu tumpukan cakram yang sesuai dengan kondisi awal dari tiang asal ke tiang tujuan. Bagaimana caranya ?

Solusi Kasus Permasalahan Menara Hanoi menggunakan Algoritma Greedy

Pengertian Algoritma greedy. Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya. Prinsip Utama Algoritma Greedy Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir. Elemen-elemen yang digunakan dalam penerapan algoritma greedy antara lain : 1. Himpunan Kandidat Himpunan yang berisi elemen pembentuk solusi. 2. Himpunan Solusi Himpunan yang terpilih sebagai solusi persoalan. 3. Fungsi Seleksi Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal. 4. Fungsi Kelayakan Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada. 5. Fungsi Solusi Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap. 6. Fungsi Objektif Fungsi yang mengoptimalkan solusi. Pemecahan Menara Hanoi Menara Hanoi adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut. Permainan Menara Hanoi sering digunakan dalam penelitian psikologis dalam hal pemecahan masalah. Selain itu, juga sering digunakan dalam pengajaran algorima rekursif bagi pelajar pemrograman. Di bawah ini adalah gambar Menara Hanoi sebelum di susun dan di urutkan ke tiang  C Contoh 1:

Disinilah cara memecahkan masalah menara hanoi dengan greedy. Suatu masalah apabila akan dipecah kan menggunakan greedy harus memenuhi  5 elemen-elemen algoritma greedy diantaranya :

1. Himpunan kandidat dari menara hanoi di atas adalah 1,2,3,4,5,6,2,1.

2. Himpunan solusinya ialah apakah semua balok yang akan di pindahkan ke tiang C telah memenuhi syarat tersusunnya menara hanoi tersebut.

3. Fungsi seleksi dari menara tersebut ialah cara penyusunan dari balok terbesar ke balok terkecil.

4. Fungsi Kelayakan dari menara tersebut ialah balok besar tidak boleh diletakkan diatas balok kecil, sehingga balok tersebut layak disimpan di tiang C.

5. Fungsi obyektif dari menara tersebut ialah dimana hasil akhirnya balok-balok yang terdapat di tiang A harus berada di tiang C dengan tersusun rapih dari terbesar hingga terkecil.

Maka dari itu di bawah ini adalah langkah-langkah bagaimana cara memindahkan balok-balok yang berada di tiang A dapat dipandahkan dan tersusun dengan rapih di tiang C.

balok 1 pindah dari tiang a ke tiang b

balok 1 pindah dari tiang a ke tiang b

balok 4 pidah dari tiang a ke tiang  c

balok 3 pindah dari tiang a ke  tiang c

balok 1 pindah dari tiang b ke tiang c

balok 5  pindah dari tiang a ke tiang  b

balok 4 pindah dari tiang a ke tiang b

balok 1 pindah dari tiang c ke tiang a

balok 3 pindah dari tiang c ke tiang b

balok 1 pindah dari tiang a ke tiang b

balok 4 pindah dari tiang c ke tiang a

balok 1 pindah dari tiang b ke tiang a

balok 3 pindah dari tiang b ke tiang c

balok 1 pindah dari tiang  a ke tiang b

balok 3 pindah dari tiang c ke tiang  a

balok 1 pindah dari tiang b ke tiang a

balok 4 pindah dari tiang c ke tiang b

balok 1 pindah dari tiang a ke tiang  c

balok 3 pindah dari tiang a ke tiang  b

balok 1 pindah dari tiang c ke tiang  b

balok 6 pindah dari tiang a ke tiang  c

balok 1 pindah dari tiang b ke tiang a

balok 3 pindah dari tiang b ke tiiang  c

balok 1 pindah dari tiang a ke tiang b

balok 2 pindah dari tiang  a ke tiang  c

balok 1 pindah dari tiang  b ke tiang  c

balok 4 pindah dari tiang b ke  tiang a

balok 4 pindha dari tiang b ke tiang  a

balok 1 pindah dari tiang  c ke  tiang a

balok 2  pindah  dari tiang c ke tiang  b

balok 1 pindah dari tiang a ke tiang  b

balok 3 pindah  dari  tiang c ke tiang a

balok 1 pindah dari tiang b ke tiang  c

balok 2 pindah dari  tiang b ke tiang  a

balok 1 pindah dari tiang  c ke tiang a

balok 5 pindah dari tiang b ke  tiang c

balok 1 pindah dari tiang a ke tiang  c

balok 2 pindah dari tiang a ke tiang b

balok 1 pindah dari tiang  c ke tiang  b

balok 3 pindah dari tiang a ke tiang c

balok 1 pindha dari tiang b ke tiang  c

balok 2 pindah dari taing b ke tiang  a

balok 1 pindah dari tiang c ke tiang a

balok 3 pindah dari tiang c ke tiang b

balok 1 pindah dari tiang a ke  tiang c

balok 2 pindah  dari  tiang a ke tiang  b

balok 1 pindah dari  tiang c ke tiang  b

balok 4 pindah  dari  tiang a ke tiang  c

balok 4  pindah dari  tiang a ke  tiang c

balok 1 pindah  dari tiang b ke tiang  c

balok 2 pindah dari tiang b ke tiang a

balok 1 pindah dari  tiang c ke tiang  a

balok 3 pindah dari  tiang b ke tiang c

balok 1  pindah dari  tiang a ke tiang  b

balok 2  pindah dari  tiang a ke tiang c

balok 1 pindah dari  tiang b ke tiang  c

Dan hasilnya adalah sebagai berikut :

Contoh 2 :

Untuk menyelesaikan puzzle di atas dalam pemrograman, kita dapat menggunakan teknik rekursif. Rekursif adalah fungsi atau prosedure yang dapat memanggil dirinya sendiri. Jadi algoritmanya adalah … Kalau N = 1 maka N dipindahkan dari A ke C secara langsung Tapi kalau N > 1 maka pindahkan N-1 dari A ke B pindahkan N dari A ke C pindahkan N-1 dari B ke C catatan : N = banyaknya piringan Referensi : Ujicobatamplate.blog. 2011. Algoritma "Tower Of Hanoi" [Menara Hanoi]. Diambil dari //ujicobatamplate.blogspot.co.id/2011/12/algoritma-of-hanoi-menara-hanoi.html [13 November 2017] Triani, Puspita. 2011. Pemecahan masalah Menara Hanoi dengan menggunakan Greedy. Diambil dari //puspitatriani.blogspot.co.id/2011/10/pemecahan-masalah-menara-hanoi-dengan.html [13 November 2017]

Page 2

Menara Hanoi adalah sebuah permainan matematis atau teka-teki. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut.

Menara HanoiTipePuzzlePenemuÉdouard LucasNegaraPrancisKeberadaan1883–sekarang

Animasi pemecahan Menara Hanoi.

Tujuan dari teka-teki ini adalah untuk memindahkan seluruh tumpukan ke tiang yang lain, mengikuti aturan berikut:

• Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
• Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
• Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

Input's size

Teka-teki ini ditemukan Édouard Lucas, ahli matematika Prancis pada tahun 1883. Ada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 cakram emas. Pendeta Brahma, melaksanakan tugas dari peramal pada masa lalu, sesuai dengan aturan teka-teki ini. Menurut legenda ini, bila teka-teki ini diselesaikan, dunia akan kiamat. Tidak jelas benar apakah Lucas menemukan legenda ini atau terinspirasi olehnya.

Bila legenda ini benar, dan pendeta itu bisa memindahkan satu cakram tiap detik, menggunakan pemindahan paling sedikit, maka akan memakan waktu 264−1 detik atau kurang lebih 584,582 miliar tahun.

Permainan Menara Hanoi sering digunakan dalam penelitian psikologis dalam hal pemecahan masalah. Selain itu, juga sering digunakan dalam pengajaran algorima rekursif bagi pelajar pemrograman. Permainan ini juga digunakan sebagai ujian ingatan oleh ahli psikolog saraf dalam berupaya mengevaluasi amnesia.

Wikimedia Commons memiliki media mengenai Tower of Hanoi.

• Menara Hanoi Interaktif Diarsipkan 2008-02-25 di Wayback Machine.
• Sejarah Menara Hanoi Diarsipkan 2007-09-28 di Wayback Machine.
• Penyelesaian dalam lingkungan BASIC klasik interaktif berbasis web

[[Kategori:Permainan otak]nice ingfo

Diperoleh dari "//id.wikipedia.org/w/index.php?title=Menara_Hanoi&oldid=20909789"