PEMANFAATAN METODE MONTE CARLO DALAM PENCARIAN PATH TERPENDEK PADA GRAF

Abstract

Pada saat ini ada beberapa cara yang dilakukan untuk mencari path terpendek pada graf. Untuk graf dengan jumlah vertek yang besar, secara konvensional pencarian ini akan menghabiskan waktu yang lama dan keakuratan yang kecil. Dengan bantuan komputer kita dapat mengembangkan banyak algoritma memudahkan kita mencari optimasi dari sebuah graf. Dengan komputasi menggunakan metode monte carlo kita dapat mendistribusikan nilai random untuk dapat memunculkan semua kemungkinan yang terjadi dari path ini. Nilai path akan diseleksi dari generasi ke generasi berdasarkan nilai terkecil dari jumlah edge, waktu yang diperlukan bergantung dari jumlah vertek dan epoch dari sebuah program.
Kata kunci: komplit graf, path terpendek, tree, monte carlo