PENERAPAN METODE DEPTH FIRST SEARCH (DFS) PADA PERMAINAN MENARA HANOI

I.         Pendahuluan

Menara Hanoi merupakan salah satu diantara berbagai teka-teki dalam matematika. Teka-teki ini ditemukan Edouard Lucas, ahli matematika Perancis di tahun 1883 (http://id.wikipedia.org/wiki/Menara_Hanoi). Teka-teki ini berdasarkan pada sebuah cerita legenda tentang candi Indian atau menara Benares di India yang memiliki tiga tiang dan salah satu tiangnya terdapat 64 tumpukan cakram emas. Para pendeta mendapat tugas untuk memindahkan cakram emas itu ke tiang yang lain sesuai dengan suatu aturan. Tidak jelas apakah ini benar-benar legenda, atau inspirasi dari Lucas sendiri. Konon, Dewa Brahma menciptakan tiga tiang pada candi tersebut. Pada salah satu tiang terdapat tumpukan cakram emas sebanyak 64 keping, dengan urutan keping yang terbesar terletak di bawah, makin ke atas makin kecil. Selanjutnya Dewa Brahma memerintahkan para pendeta untuk memindahkan keping-keping emas itu dengan aturan : setiap perpindahan hanya boleh memindah 1 cakram dan cakram yang besar tidak boleh diletakkan di atas cakram yang lebih kecil. Dalam legenda itu dikatakan bahwa dunia akan berakhir jika para pendeta tersebut selesai memindahkan ke 64 cakram. Pertanyaannya adalah, berapa lama waktu yang diperlukan para pendeta tersebut untuk memindahkan ke-64 keping cakram ke tiang yang lain?

II.      Aturan Permainan

Permasalahan pada permainan Menara Hanoi ini adalah bagaimana cara memindahkan semua piringan dari menara asal ke menara tujuan dengan bantuan satu menara bantu yaitu menara sementara.
Adapun aturan-aturan permainannya, sebagai berikut :

• Setiap kali memindah cakram hanya diperbolehkan       mengangkat satu cakram.
• Setiap cakram yang lebih besar tidak boleh diletakkan di atas cakram yang lebih kecil.
• Piringan yang lebih besar ditempatkan di bawah piringan yang lebih kecil.

III.   Identifikasi Ruang Keadaan

Permainan Menara Hanoi yang akan di bahas kali ini menggunakan 3 menara dan 4 piringan. Dimana ukuran piringan tersebut berbeda satu sama lain. Semua piringan berada pada menara asal dengan susunan secara berurutan, yang terbesar berada pada posisi paling bawah dan yang terkecil pada posisi paling atas seperti yang tampak pada gambar di bawah ini.

I.         Keadaan Awal dan Keadaan Tujuan

Dalam proses pemecahan masalah permainan Menara Hanoi perlu ditetapkan suatu keadaan awal dan keadaan tujuan untuk mempermudah penyelesaiannya.

1.      Keadaan Awal

Bila didefinisikan menara A sebagai menara asal, menara C sebagai menara tujuan dan menara B sebagai menara sementara, dengan 4 jumlah piringan yang masing-masing didefinisikan sebagai N1, N2 dan N3 dimana ukuran N4 > N3> N2> N1. Menara A berisi  4 piringan dengan susunan N4, N3, N2, N1 dari bawah ke atas. Sedangkan menara C dan B dalam kondisi tidak ada piringan (kosong).

1.                  Keadaan tujuan

Menara A dan B kosong, sedangkan menara C berisi piringan N4, N3, N2, N1 tersusun dari bawah ke atas seperti yang terlihat.

I.         Dasar Aturan (Rule Base)

Untuk mencapai keadaan tujuan maka dibuatlah aturan-aturan yang dapat memenuhi semua keadaan yang mungkin terjadi. Adapun aturan-aturan tersebut adalah sebagai berikut :

1. Jika B kosong atau N_B> N_A, pindahkan N_A ke B
2. Jika C kosong atau N_C > N_A, pindahkan N_A ke C
3. Jika A kosong atau N_A > N_B, pindahkan N_B ke A
4. Jika C kosong atau  N_C > N_B, pindahkan N_B ke C
5. Jika A kosong atau N_A > N_C, pindahkan N_c ke A
6. Jika B kosong atau N_B > N_C, pindahkan N_C ke B

II.      Solusi

Salah satu metode yang dapat dipakai dalam proses pemecahan permasalahan pada Menara Hanoi yaitu dengan menggunakan metode DFS (Depth First Search) atau pencarian mendalam.
Metode DFS (Depth First Search) merupakan metode pencarian yang dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang terdalam solusi belum ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
Kelebihan dari metode Depth First Search yaitu :

• Jika solusi yang dicari berada pada level yang dalam dan paling kiri maka DFS akan menemukannya dengan cepat.
• Jika diimplementasikan dalam program, penggunaan memori akan lebih sedikit karena hanya simpul-simpul pada lintasan yang aktif saja yang disimpan.

Adapun kelemahan dari metode Depth First Search yaitu :

• Jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga), maka tidak ada jaminan menemukan solusi. Artinya DFS tidak komplit.
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik. Artinya DFS tidak optimal.

Langkah-langkah pencarian solusi menggunakan metode DFS adalah   sebagai berikut:

1. Solusi dicari dengan membentuk lintasan dari akar sampai daun. Simpul-simpul yang sudah dilahirkan dinamakan simpul anak kiri dan simpul anak kanan.
2. Simpul yang dibentuk, terlebih dahulu simpul sebelah kiri dan mendalam sampai ditemukan solusi.
3. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka lintasan yang sebelah kiri dihentikan disebut simpul mati dan dilanjutkan ke simpul anak kanan terdekat. Simpul yang sudah dihentikan (simpul mati) tidak akan pernah diperluas lagi.
4. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan pembentukan ke simpul hidup terdekat. Selanjutnya simpul ini menjadi simpul hidup yang baru.
5. Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi.

Solusi permasalahan untuk pemindahan seluruh piringan dari menara asal ke menara tujuan pada permainan Menara Hanoi dengan metode DFS dapat dilihat pada tabel 1 dan gambar 5 berikut ini.

Tabel1. Solusi Permainan Menara Hanoi

 

I.         Kesimpulan

Dengan metode DFS (Depth First Search), proses pemecahan masalah pada permainan Menara Hanoi dapat disimpulkan sebagai berikut:

• Metode DFS mampu menyelesaikan masalah pada permainan Menara Hanoi.
• Sesuai dengan kelebihan pada metode DFS, telah terbukti bahwa pemecahan permasalahan permainan Menara Hanoi dapat diselesaikan dengan beberapa solusi. Dimana solusi dari permasalahan tersebut yang terbaik adalah solusi yang paling cepat ditemukan dimana letak solusi yang dicari berada pada level yang dalam dan paling kiri.
• Untuk N buah piringan diperlukan pemindahan sebanyak 2ⁿ – 1 kali. Ternyata dengan menggunakan metode DFS  terbukti pula untuk 3 buah piringan dapat diselesaikan dengan 2 ⁴ – 1 langkah = 7 langkah.

I.         Daftar Referensi

Atmavidya, Arif Nanda, Penerapan Algoritma Backtracking dalam Pencarian Solusi Menara Hanoi,  Institut Teknologi Bandung, 2008
Mukti, Garibaldy W, Berbagai Solusi Pemecahan Masalah Tower of Hanoi dan Representasi Grafnya, Institut Teknologi Bandung, 2008
Santosa, Insap, Struktur Data menggunakan Turbo Pascal, Andi Offset Yogyakarta, 2003
Suyanto, Artificial Intelligence, Informatika Bandung, 2007
Wikipedia, http://en.wikipedia.org/wiki/Tower_of_Hanoi, diakses 10 Desember 2008
http://rusdyana.wordpress.com/2009/
hidjah, khasnur dkk, penerapan metode depth first search (dfs)
                        Pada permainan menara Hanoi,UGM, Yogyakarta.2008