Rendezvous search pada garis dengan sumber daya terbatas peminimuman waktu harapan

Abstract

Pada suatu lapangan luas dengan lintasan kereta api melintasi seluruh daerah tersebut, dua orang penerjun payung diterjunkan. Mereka ingin bertemu di lintasan kereta api tersebut, tetapi persisnya titik pertemuan tersebut tidak diketahui. Pencarian dilakukan di sepanjang lintasan kereta api, sehingga untuk memecahkan masalah ini digunakan rendezvous search pada garis. Tiap pemain tidak mengetahui arah perjalanan pemain lainnya, mereka hanya mengetahui jarak atau sebaran jarak. Mereka dapat bergerak dengan kecepatan paling besar 1, dan sumber daya (kemampuan untuk melakukan tindakan) yang mereka miliki masing-masing terbatas. Penelitian ini dilakukan untuk membantu kedua pemain menentukan strategi yang harus dipakai agar mercka dapat bertemu dalam waktu yang minimum. Langkah pertama yang harus dilakukan adalah mencari jaminan apakah kedua pemain dengan keterbatasan sumber daya ini dapat bertemu. Jika jaminan itu sudah ada maka waktu harapan terkecil (nilai randevu) dapat dicari. Nilai randevu ini dapat dicari melalui dua metode yaitu melalui metode langsung dan tidak langsung. Dalam metode tidak langsung nilai randevu dicari berdasarkan rendezvous search dengan sumber daya tidak terbatas, dan dalam metode langsung nilai randevu dicari dengan mengandalkan penafsiran secara matematis dari informasi yang ada yaitu sejak awal diasumsikan bahwa sumber daya tiap pemain terbatas. Apabila sumber daya kedua pemain masing-masing a dan b dengan azb memenuhi pertidaksamaan 5a+3b215, dan strategi yang digunakan adalah g,heS, maka kedua pemain dijamin dapat bertemu dalam waktu minimum.