Labirin

aktivitet-labyrint.jpg

 

Tentu kita mengenal permainan labirin, yaitu permainan yang mencari jalan keluar . Permainan ini biasa dilakukan dalam sekala besar, ataupun skala kecil yang biasa kita temukan di kertas. Permainan labirin ini juga bias kita aplikasikan dalam kehidupan nyata. Seperti bagaimana kita dapat keluar dari sebuah hutan yang memiliki jalan bercabang. Labirin dapat kita modelkan sebagai berikut:


labirin.gif

 

Dalam permainan ini, pemain masuk dari pintu masuk, lalu mencari jalan keluar dari labirin ini. atau lebih mudah dijelaskan dalam gambar ini….

labyrint.jpg

MENCARI JALAN KELUAR

Bagaimana kita dapat mencari jalan keluar dalam labirin? Akan sangat mudah jika kita mencari jalan keluar labirin jika labirin yang dimaksud adalah permainan skala kecil yang biasa kita temukan di kertas, seperti yang kita lihat pada gambar permodelan labirin di atas. Dalam permainan labirin skala kecil ini, kita dapat melihat dengan jelas jalan masuk dan jalan keluarnya. Sedangkan, jika permainan labirin yang dimaksud adalah permainan labirin skala besar, yaitu permainan labirin 3 dimensi, kita tidak bisa melihat jalan keluar dari permainan ini, dan yang dapat kita lihat adalah petak jalan yang kita sedang lewati.

Ternyata, permainan labirin dapat kita modelkan juga dalam bentuk pohon, atau biasa kita kenal dengan n-ary. Pohon yang mempunyai akar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-ary . Dengan memodelkan labirin dengan n-ary, kita akan lebih mudah menemukan jalan keluar dalam permainan labirin. Berikut ini adalah cara mencari jalan keluar dari labirin dengan memodelkan labirin dengan n-array:

11.jpg

 

1. Anggaplah jalan masuk sebagai parent dari pohon n-ary

2. Caban-cabang jalan yang terlihat dari parent atau pintu masuk kia gambar dan dapat kita analogikan sebagai simpul.

3. Dalam membuat pohon n-ary dari labirin ini, kita harus dapat membuat semua simpul yang dianalogikan sebagai cabag setiap jalan yang kita lewati pada labirin. Agar tidak tersesat, kita mulai merunutkan jalan dengan memilih jalan paling kiri atau jalan paling kanan di setiap cabang jalan permainan labirin.

4. Jalan yang terlihat dari cabang kita gambar tanpa perlu kita masuki terlebih dahulu. Jalan yang terlihat dari cabang dapat kita maski setelah percabangan sebelumnya telah kita masuki dan hasilnya adalah jalan buntu.

5. Jalan keluar , jalan yang terlihat dari percabangan dan jalan buntu adalah daun pada pohon n-ary. Jalan keluar adalah salah satu daun dalam pohon labirin n-ary ini.

penjelasan-labirin.jpg

 

 

Yang menjadi kunci utama dalam mencari pintu keluar adalah dengan cara memilih percabangan jalan secara berurutan. Kita dapat terus memilih percabangan jalan paling kiri di setiap percabangan sampai menemukan jalan buntu dan mulai memilih cabang kedua paling kiri dari percabangan jalan ini.