Contoh Relasi Rekurensi: Menara Hanoi

martha yunanda kombinatorika

Sebelumnya telah dijelaskan mengenai arti dari relasi rekurensi. Juga sudah dipaparkan contoh permodelan matematika relasi rekurensi Kelinci dan Bilangan Fibonacci. Berikutnya ini adalah contoh aplikasi model matematika relasi rekurensi dengan nama Problem Menara Hanoi.

Kasus:
Jenis Puzzle ini dikenalkan oleh seorang ahli matematika di akhir abad ke-19 yang berasal dari Perancis yaitu Edouard Lucas. Problem ini dikenal dengan nama Menara Hanoi. Permasalahannya seperti berikut,

Puzzle menara hanoi ini terdiri dari tiga tiang yang diletakkan di atas papan bersama dengan piringan yang ukurannya berbeda. Pada kondisi awal piringan ini diletakan pada tiang pertama dalam urutan berdasarkan ukuran, dengan piringan terbesar berada paling bawah. Aturannya adalah, piringan boleh dipindahkan dari tiang satu ke tiang lainnya sepanjang piringan yang lebih besar tidak diletakkan di atas piringan yang lebih kecil. Tujuan dari puzzle ini adalah memindahkan semua piringan dari tiang pertama ke tiang kedua dalam urutan berdasarkan ukuran dengan syarat piringan paling besar ada di urutan paling bawah.

Misal $H_n$ dinotasikan sebagai banyaknya langkah minimal yang diperlukan untuk menyelesaikan permasalahan menara hanoi dengan n piringan. Tentukanlah relasi rekurensi untuk barisan ($H_n$)


Solusi 
Penyelesaian dimulai dengan n piringan pada tiang pertama. Lalu bisa dipindahkan n-1 piringan dari yang paling atas. Berdasarkan aturan main, dilanjutkan pada tiang ketiga dengan jumlah $H_{n-1}$ langkah.

Piringan terbesar pada tiang pertama dipindahkan pada tiang ke-dua dengan 1 langkah. Selanjutnya pindahkan piringan ketiga dengan menggunakan $H_{n-1}$ langkah ke tiang ke dua dengan menaruh piringan di atas piringan yang lebih besar yang diletakkan sebelumnya.

Bentuk umumnya bisa dituliskan,
$H_n= 2 H_{n-1}+1$ , syarat Awal $H_1=1$ sebab 1 piringan bisa dipindahkan dari tiang pertama ke tiang kedua dengan 1 langkah.

Penjabaran berikutnya, akan dibuat bentuk iterasi (pengulangan) dan disederhanakan sebagai berikut,
$\begin{align*} H_n &= 2H_{n-1} + 1\\ &=2(2H_{n-2} + 1) + 1\\ &= 2^2(2H_{n-3} + 1) + 2 + 1 = 2^3H_{n-3} + 2^2 + 2 + 1\\ &\vdots\\ &=2^{n-1}H_1 + 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^{n-1}+ 2^{n-2} + 2^{n-3} + \ldots + 2 + 1\\ &=2^n - 1 \end{align*}$

Sebagai tambahan, misalkan akan dipindahkan menara Hanoi dengan 5 piringan. Secara hitungan akan dibutuhkan
$2^n-1 = 2^5-1 =32$ gerakan. Perhatikan pembuktiannya pada ilustrasi video menara Hanoi di bawah ini,

Berikutnya:Contoh Relasi Rekurensi Codeword

Share on Facebook

Share on Twitter

Share on LinkedIn