Persoalan pertemuan
Dilema pertemuan bisa digambarkan sebagai berikut:
- Dua orang berjanji temu di sebuah taman yang belum pernah mereka kunjungi. Mereka datang sendiri dan baru tahu bahwa tamannya sangat besar. Mereka pun kesulitan bertemu satu sama lain. Dalam situasi seperti ini, masing-masing dari mereka harus memilih antara menunggu di suatu tempat supaya ditemukan orang lain atau mencari orang lain yang mungkin sudah menunggu di suatu tempat.
Apabila mereka berdua memilih menunggu, mereka tidak akan pernah bertemu. Apabila mereka memilih mencari, mereka bisa saja bertemu atau tidak bertemu. Apabila satu orang memilih menunggu dan satu lagi berjalan, mereka pada akhirnya akan bertemu; dalam praktiknya, proses mencari seperti ini memakan waktu yang sangat lama. Persoalannya adalah: apa strategi yang perlu mereka ambil untuk memaksimalkan peluang bertemu?
Contoh persoalan seperti ini dikenal dengan istilah persoalan pertemuan. Persoalan ini pertama kali diperkenalkan secara tidak formal oleh Steve Alpern pada tahun 1976.[1] Ia membahas lebih lanjut persoalan ini secara formal pada tahun 1995.[2] Sejak itu, banyak peneliti yang mendalami permasalahan ini.[3] Persoalan pertemuan simetris yang disimulasikan di n lokasi tertentu (kadang disebut Mozart Cafe Rendezvous Problem)[4] ternyata sangat sulit diselesaikan. Pada tahun 1990, Richard Weber dan Eddie Anderson memperkirakan strategi yang optimal.[5] Perkiraan yang dibuktikan Weber adalah n = 3.[6] Ini merupakan persoalan pertemuan simetris non-trivial pertama yang selesai sepenuhnya. Ingat bahwa persoalan pertemuan asimetris memiliki satu solusi optimal yang sederhana: satu pihak menunggu di lokasi awal dan pihak lain mencarinya menggunakan permutasi lokasi acak.
Selain dalam teori, dilema janji temu juga diterapkan di dunia nyata, misalnya di bidang sinkronisasi, rancangan sistem operasi, penelitian operasi, dan bahkan perencanaan operasi pencarian dan penyelamatan.
Persoalan pertemuan deterministik
Persoalan pertemuan deterministik adalah varian dilema pertemuan. Para pihak atau robot harus menemukan satu sama lain dengan mengikuti urutan instruksi yang deterministik. Meski setiap robot mengikuti urutan instruksi yang sama, sebuah label unik di setiap robot digunakan untuk mencegah kemiripan.[7]
Lihat pula
Referensi
- ^ Alpern, Steve (1976), Hide and Seek Games, Seminar, Institut fur Hohere Studien, Wien, 26 July.
- ^ Alpern, Steve (1995), "The rendezvous search problem", SIAM Journal on Control and Optimization, 33 (3): 673–683, doi:10.1137/S0363012993249195, MR 1327232
- ^ Alpern, Steve; Gal, Shmuel (2003), The Theory of Search Games and Rendezvous, International Series in Operations Research & Management Science, 55, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-7468-1, MR 2005053.
- ^ Alpern, Steve (2011), "Rendezvous search games", dalam Cochran, James J., Wiley Encyclopedia of Operations Research and Management Science, Wiley, doi:10.1002/9780470400531.eorms0720.
- ^ Anderson, E. J.; Weber, R. R. (1990), "The rendezvous problem on discrete locations", Journal of Applied Probability, 27 (4): 839–851, doi:10.2307/3214827, MR 1077533.
- ^ Weber, Richard (2012), "Optimal symmetric Rendezvous search on three locations" (PDF), Mathematics of Operations Research, 37 (1): 111–122, doi:10.1287/moor.1110.0528, MR 2891149.
- ^ Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12.