Bridge and Torch (Dynamic Programing)

Ketika saya kuliah di matematika UI semester 6, saya mengambil peminatan ke arah komputasi dan operasional riset. Waktu itu, saya mengambil mata kuliah Dynamic Programing, dengan dosennya Mba Helen namanya. Enak kuliahnya, 3S pokoknya, seru santai susah hahha. Susah kenapa?, karena waktu tugas akhirnya yang dipakai untuk nilai UAS itu kita disuruh cari bahan tentang dynamic programing yang berkaitan dengan game, dan dibuat juga aplikasinya (berupa program) dan semester 6 juga merupakan semester yang padat buat saya, karena saya mengambil banyak sks, dan juga lagi aktif-aktifnya di BEM Fakultas (cailah).

Dalam tugas akhir mata kuliah tersebut, saya mencoba mencari solusi penyelesaian dari game "Bridge Crossing" atau disebut juga "Bridge and Torch" dan membuat aplikasinya (dalam hal ini saya menggunakan matlab, nanti akan dibahas lebih lanjut), sepertinya sudah pada tahu game ini seperti apa. Ok, berikut ini saya tampilkan game tersebut, silahkan dicoba. Jika belum mengerti cara bermain, saya juga akan jelaskan mengenai tata cara permainannya.

Pembahasan
Bridge and Torch adalah salah satu jenis puzzle (permainan teka-teki) matematika, dimana sebanyak m orang, P = {1, 2, …, m}, harus menyeberangi sebuah bridge (jembatan) yang menghubungkan tempat A ke tempat B. Mereka menyeberangi bridge tersebut pada malam hari yang gelap, oleh karena itu mereka hanya bisa menyeberangi bridge tersebut jika mereka membawa lampu. Masalahnya, mereka hanya memiliki satu buah lampu dan maksimal banyaknya orang dalam setiap kali menyeberangi bridge tersebut adalah sebanyak 2 orang. Setiap orang memiliki waktu menyeberang (t) masing-masing (bisa berbeda ataupun sama). Waktu yang dibutuhkan untuk sekali menyeberang untuk suatu kelompok adalah waktu paling lama yang dimiliki oleh orang yang menyeberang dalam kelompok tersebut. Bagaimanakah caranya agar n orang tersebut dapat menyeberangi bridge dengan waktu yang paling minimum (optimal)? Saya akan berikan solusi yang telah dapat, mari kita lanjutkan.

Berikut ini saya berikan, solusi berupa formula yang saya peroleh dengan menggunakan dynamic programing.

Formula/Model


Untuk penjelasannya panjang dan sulit jika saya taro sini (sekarang mepet udah jam 8 pagi, saya mesti pergi jam 10 hari ini hahha belum mandi juga), jadi buat yang penasaran bisa dicoba program yang saya buat, kalo penasaran juga ko bisa dapet model seperti di atas, pengen tau cara penyelesaian manualnya atau menggunakan program yang saya buat. Bisa download disini :

Penjelasan lebih lanjut (Mediafire)
Program Bridge and Torch (Mediafire)