power of hanoy dengan metoda greedy

Memecahkan Menara Hanoi dengah Metode Greedy

1. Mengenal Menara Hanoi dan Metode Greedy

• Cerita Menara Hanoi

Pada suatu hari, di vietnam, seorang pendeta dari sebuah kuil harus memindahkan 64 piringan emas suci
dari satu berlian ke berlian lain yang disusun dari piringan paling besar (terbawah) dari piringan paling kecil.
Piringan ini sangat rapuh sehingga hanya bisa dibawa satu per satu. Selain itu, piringan lebih besar tidak boleh
ditaruh diatas piringan yang lebih kecil. Terdapat berlian lain di antara berlian tujuan dan berlian awal.
     Saat Pendeta telah selesai memindahkan 64 piringan tersebut, maka legenda mengatakan bahwa dunia akan
berakhir. Untuk itu, kita harus mengetahui berapa lama puzzle ini akan selesai dan berapa banyak langkah yang
dibutuhkan untuk mencapai solusi tersebut?  Puzzle ini dikenalkan olen N Claus (de Siam), seorang  professor dari Universitas Li-Sou-Louis, dan anagram Edouard Lucas (D’Ameins), seorang professor dari Lyce
Saint-Louis.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 milyar tahun.

• Metode Greedy

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 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.  Adapun elemen–elemen yang digunakan dalam penerapan algoritma greedy antara lain :
- Himpunan Kandidat.
            Himpunan yang berisi elemen pembentuk solusi,  yaitu benda 1,2,3,4,4,5 dan 6
- Himpunan Solusi.
            Himpunan yang terpilih sebagai solusi persoalan, yaitu dengan mencari nilai yang terbesar kemudian
            pindahkan ke daerah C sedangkan yang lainnya di pindahkan ke A atau B.
- Fungsi Seleksi.
            Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal, yaitu dengan
            memilih benda terbesar dan di pindahkan ke C supaya bisa tersusun secara terurut.
- 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,yaitu dengan memindahkan nilai yang kecil ke daerah yang
            kosong (A atau B).
- Fungsi Solusi
            Fungsi yang mengembalikan nilai  boolean. True jika himpunan solusi yang sudah tebentuk
            merupakan solusi yang lengkap;  False jika himpunan solusi belum lengkap.
Penyelesaian dengan cara satu :

 

gambar gif

Algoritma :

Cari benda terbesar di daerah A dan B dan tentukan letaknya. Kemudian pindahkan  benda kecil ke daerah yang kosong (daerah A atau B) dengan ketentuan :

1.       Jika benda kecil letaknya berada di atas benda besar maka pindahkan benda kecil tersebut ke daerah A atau B (jika benda ada di A maka pindahkan ke B, jika benda ada di B maka pindahkan ke A).

2.       Jika benda kecil letaknya berada di bawah benda besar maka pindahkan benda besar terlebih dahulu ke daerah C, kemudian pindahkan benda kecil tersebut ke daerah A atau B (jika benda ada di A maka pindahkan ke B, jika benda ada di B maka pindahkan ke A) sesuai dengan perpindahan di atas.

Jika benda dari daerah A atau B yang ukurannya sama dan merupakan terbesar maka pindahkan ke C.

Penyelesaian :

Aturan hanya di pindahkan satu-satu

Jika Mempunyai Dua Aturan (seperti biasanya)

******************************************************************************
Tapi biasanya menara hanoi mempunyai dua pelaturan yaitu :
- Di pindahkan satu-satu
-Benda yang kecil harus selalu di atas benda yang lebih besar

Kalau dengan pelaturan seperti itu begini cara menyelesaikan masalah itu :

Read More