Versi asli dari artikel ini diterbitkan di Quanta Magazine.
Apabila ingin memecahkan suatu masalah yang rumit, sering kali kita perlu mengatur pendekatan dengan lebih terstruktur. Misalnya, dengan memecah masalah menjadi bagian-bagian kecil dan menyelesaikan bagian termudah terlebih dahulu. Namun, proses pengurutan semacam ini juga memiliki biaya tersendiri. Bisa jadi kita menghabiskan terlalu banyak waktu hanya untuk mengatur urutan bagian-bagian tersebut.
Dilema ini sangat relevan dengan salah satu masalah paling ikonis dalam ilmu komputer: mencari jalur terpendek dari suatu titik awal spesifik ke setiap titik lain dalam sebuah jaringan. Ini seperti versi yang lebih canggih dari masalah yang kita hadapi setiap kali pindah rumah: mencari rute terbaik dari rumah baru ke kantor, pusat kebugaran, dan supermarket.
“‘Shortest paths’ adalah masalah yang indah dan dapat dipahami oleh siapa saja di seluruh dunia,” ungkap Mikkel Thorup, seorang ilmuwan komputer dari Universitas Copenhagen.
Secara intuitif, menemukan jalur terpendek ke tujuan yang dekat seharusnya lebih mudah. Jadi, jika ingin merancang algoritma tercepat untuk masalah ini, tampaknya masuk akal untuk memulai dengan mencari titik terdekat, lalu titik berikutnya yang terdekat, dan seterusnya. Tetapi untuk melakukannya, kita perlu terus-menerus menentukan titik mana yang paling dekat. Kita akan mengurutkan titik-titik berdasarkan jarak seiring prosesnya. Ada batas kecepatan fundamental untuk setiap algoritma yang mengikuti pendekatan ini: kita tidak bisa lebih cepat dari waktu yang dibutuhkan untuk melakukan pengurutan.
Empat puluh tahun lalu, para peneliti yang merancang algoritma pencarian jalur terpendek mentok pada “hambatan pengurutan” ini. Kini, sebuah tim peneliti telah menciptakan algoritma baru yang berhasil menembusnya. Algoritma ini tidak melakukan pengurutan, dan berjalan lebih cepat daripada algoritma apapun yang melakukannya.
“Para penulis cukup berani karena berpikir mereka dapat menembus batasan ini,” komentar Robert Tarjan, seorang ilmuwan komputer dari Universitas Princeton. “Ini adalah hasil yang luar biasa.”
Batas Pengetahuan
Untuk menganalisis masalah jalur terpendek secara matematis, peneliti menggunakan bahasa graf—jaringan titik (node) yang terhubung oleh garis. Setiap tautan antar-node diberi label dengan angka yang disebut bobot, yang dapat mewakili panjang segmen tersebut atau waktu yang diperlukan untuk melaluinya. Biasanya ada banyak rute antara dua node mana pun, dan yang terpendek adalah rute yang jumlah bobotnya paling kecil. Diberikan sebuah graf dan sebuah “sumber” node tertentu, tujuan algoritma adalah menemukan jalur terpendek ke setiap node lain.
Algoritma pencarian jalur terpendek paling terkenal, yang dirancang oleh perintis ilmu komputer Edsger Dijkstra pada tahun 1956, dimulai dari sumber dan bekerja ke luar langkah demi langkah. Ini adalah pendekatan yang efektif, karena mengetahui jalur terpendek ke node terdekat dapat membantu menemukan jalur terpendek ke node yang lebih jauh. Tetapi karena hasil akhirnya adalah daftar terurut dari jalur terpendek, hambatan pengurutan menetapkan batas fundamental pada seberapa cepat algoritma dapat berjalan.