Algoritma Baru Mempercepat Pencarian Jalur Terpendek

Versi aslinya dari cerita ini muncul di Majalah Kuanta.

Jika Anda ingin memecahkan masalah yang rumit, mengatur diri sendiri sering kali membantu. Misalnya, Anda dapat memecah masalah menjadi beberapa bagian dan menyelesaikan bagian yang paling mudah terlebih dahulu. Namun penyortiran seperti ini memerlukan biaya. Anda mungkin menghabiskan terlalu banyak waktu untuk menata barang-barang tersebut.

Dilema ini sangat relevan dengan salah satu masalah paling ikonik dalam ilmu komputer: menemukan jalur terpendek dari titik awal tertentu dalam jaringan ke titik lainnya. Ini seperti versi lengkap dari masalah yang perlu Anda selesaikan setiap kali Anda pindah: mempelajari rute terbaik dari rumah baru Anda ke tempat kerja, gym, dan supermarket.

“Jalur terpendek adalah masalah indah yang dapat dialami oleh siapa pun di dunia,” katanya Mikel Thorupseorang ilmuwan komputer di Universitas Kopenhagen.

Secara intuitif, cara termudah adalah menemukan jalur terpendek ke tujuan terdekat. Jadi jika Anda ingin merancang algoritma tercepat untuk masalah jalur terpendek, masuk akal untuk memulai dengan mencari titik terdekat, lalu titik terdekat berikutnya, dan seterusnya. Namun untuk melakukan itu, Anda perlu berulang kali mencari tahu titik mana yang paling dekat. Anda akan mengurutkan poin berdasarkan jarak seiring berjalannya waktu. Ada batas kecepatan mendasar untuk algoritma apa pun yang mengikuti pendekatan ini: Anda tidak bisa bergerak lebih cepat dari waktu yang diperlukan untuk menyortir.

Empat puluh tahun yang lalu, para peneliti yang merancang algoritma jalur terpendek menghadapi “penghalang penyortiran” ini. Kini, tim peneliti telah merancangnya algoritma baru yang memecahkannya. Itu tidak mengurutkan, dan berjalan lebih cepat daripada algoritma apa pun.

“Para penulisnya berani berpikir bahwa mereka dapat mendobrak penghalang ini,” kata Robert Tarjanseorang ilmuwan komputer di Universitas Princeton. “Ini adalah hasil yang luar biasa.”

Perbatasan Pengetahuan

Untuk menganalisis masalah jalur terpendek secara matematis, peneliti menggunakan bahasa grafik—jaringan titik, atau node, yang dihubungkan oleh garis. Setiap hubungan antar node diberi label dengan angka yang disebut bobot, yang dapat mewakili panjang segmen tersebut atau waktu yang diperlukan untuk melintasinya. Biasanya terdapat banyak rute antara dua node, dan rute terpendek adalah rute yang bobotnya berjumlah paling sedikit. Dengan adanya grafik dan node “sumber” tertentu, tujuan algoritma adalah menemukan jalur terpendek ke setiap node lainnya.

Itu algoritma jalur terpendek yang paling terkenal, dirancang oleh ilmuwan komputer perintis Edsger Dijkstra pada tahun 1956, dimulai dari sumbernya dan bekerja secara bertahap. Ini merupakan pendekatan yang efektif, karena mengetahui jalur terpendek ke node terdekat dapat membantu Anda menemukan jalur terpendek ke node yang lebih jauh. Namun karena hasil akhirnya adalah daftar jalur terpendek yang diurutkan, penghalang pengurutan menetapkan batasan mendasar pada seberapa cepat algoritme dapat berjalan.

Pada tahun 1984, Tarjan dan peneliti lainnya menyempurnakan algoritma asli Dijkstra sehingga mencapai batas kecepatan ini. Perbaikan lebih lanjut harus datang dari algoritma yang menghindari penyortiran.

Pada akhir tahun 1990-an dan awal tahun 2000-an, Thorup dan peneliti lainnya merancang algoritma yang memecahkan hambatan penyortiran, namun mereka perlu membuat yakin asumsi tentang beban. Tidak ada yang tahu bagaimana memperluas teknik mereka ke beban yang sewenang-wenang. Sepertinya mereka sudah sampai di ujung jalan.

“Penelitian terhenti untuk waktu yang sangat lama,” kata Ran Duanseorang ilmuwan komputer di Universitas Tsinghua di Beijing. “Banyak orang percaya bahwa tidak ada cara yang lebih baik.”

Duan bukan salah satu dari mereka. Dia sudah lama memimpikan membangun algoritma jalur terpendek yang bisa menembus penghalang penyortiran di semua grafik. Musim gugur yang lalu, dia akhirnya berhasil.

Di Luar Macam

Ketertarikan Duan terhadap hambatan penyortiran sudah ada sejak 20 tahun yang lalu ketika ia masih kuliah pascasarjana di Universitas Michigan, di mana penasihatnya adalah salah satu peneliti yang mencari cara untuk mendobrak hambatan tersebut dalam kasus-kasus tertentu. Namun baru pada tahun 2021 Duan menemukan pendekatan yang lebih menjanjikan.

Kuncinya adalah fokus pada arah algoritma selanjutnya di setiap langkah. Algoritma Dijkstra mengambil wilayah yang telah dieksplorasi pada langkah sebelumnya. Ia memutuskan ke mana harus pergi selanjutnya dengan memindai “perbatasan” kawasan ini—yaitu, semua titik yang terhubung ke batasnya. Ini tidak memakan banyak waktu pada awalnya, namun menjadi lebih lambat seiring kemajuan algoritma.

Duan malah membayangkan mengelompokkan titik-titik tetangga di perbatasan menjadi beberapa kelompok. Dia kemudian hanya akan mempertimbangkan satu node dari setiap cluster. Dengan lebih sedikit node yang harus disaring, pencarian bisa lebih cepat di setiap langkah. Algoritme juga mungkin berakhir di suatu tempat selain node terdekat, sehingga penghalang penyortiran tidak akan berlaku. Namun memastikan bahwa pendekatan berbasis pengelompokan ini benar-benar membuat algoritme menjadi lebih cepat dan bukannya lebih lambat akan menjadi sebuah tantangan.

Duan menyempurnakan ide dasar ini pada tahun berikutnya, dan pada musim gugur 2022 dia optimistis dapat mengatasi kendala teknis. Dia merekrut tiga mahasiswa pascasarjana untuk membantu mengerjakan rinciannya, dan beberapa bulan kemudian mereka tiba di sana solusi parsial—sebuah algoritma yang memecahkan penghalang penyortiran untuk bobot apa pun, tetapi hanya pada apa yang disebut grafik tidak berarah.

Pada graf tidak berarah, setiap link dapat dilintasi pada kedua arah. Ilmuwan komputer biasanya lebih tertarik pada kelas grafik yang lebih luas yang menampilkan jalur satu arah, namun grafik “terarah” ini seringkali lebih sulit untuk dinavigasi.

“Mungkin saja A bisa menjangkau B dengan mudah, tapi B tidak bisa menjangkau A dengan mudah,” ujarnya Xiao Maoseorang mahasiswa pascasarjana ilmu komputer di Universitas Stanford. “Itu akan memberimu banyak masalah.”

Jalan yang Menjanjikan

Pada musim panas tahun 2023, Mao mendengar Duan memberikan ceramah tentang algoritma grafik tidak berarah di sebuah konferensi di California. Dia memulai percakapan dengan Duan, yang karyanya sudah lama dia kagumi.

“Saya bertemu dengannya untuk pertama kali dalam kehidupan nyata,” kenang Mao. “Itu sangat menarik.”

Setelah konferensi, Mao mulai memikirkan masalah tersebut di waktu luangnya. Sementara itu, Duan dan rekan-rekannya sedang menjajaki pendekatan baru yang dapat digunakan pada grafik berarah. Mereka mengambil inspirasi dari algoritma lain yang bagus untuk masalah jalur terpendek, yang disebut algoritma Bellman-Ford, yang tidak menghasilkan daftar yang diurutkan. Sekilas, ini tampak seperti strategi yang tidak bijaksana, karena algoritma Bellman-Ford jauh lebih lambat dibandingkan algoritma Dijkstra.

“Setiap kali Anda melakukan penelitian, Anda mencoba mengambil jalur yang menjanjikan,” kata Thorup. “Saya hampir menyebutnya anti-janji untuk mengambil Bellman-Ford, karena itu terlihat seperti hal paling bodoh yang mungkin Anda lakukan.”

Tim Duan menghindari lambatnya algoritma Bellman-Ford dengan menjalankannya hanya beberapa langkah dalam satu waktu. Penggunaan Bellman-Ford yang selektif ini memungkinkan algoritme mereka untuk mencari node paling berharga untuk dijelajahi pada langkah selanjutnya. Node-node ini seperti persimpangan jalan raya utama dalam jaringan jalan raya.

“Kamu harus melewatinya [them] untuk mendapatkan jalur terpendek ke banyak hal lainnya,” kata Thorup.

Pada bulan Maret 2024, Mao memikirkan pendekatan lain yang menjanjikan. Beberapa langkah penting dalam pendekatan awal tim menggunakan keacakan. Algoritma acak dapat menyelesaikan banyak masalah secara efisien, namun peneliti masih lebih memilih pendekatan nonacak. Mao merancang cara baru untuk memecahkan masalah jalur terpendek tanpa keacakan. Dia bergabung dengan tim, dan mereka bekerja sama selama beberapa bulan berikutnya melalui obrolan grup dan panggilan video untuk menggabungkan ide-ide mereka. Akhirnya, pada musim gugur, Duan menyadari bahwa mereka dapat mengadaptasi suatu teknik sebuah algoritma dia merancang pada tahun 2018 yang memecahkan hambatan penyortiran untuk masalah grafik yang berbeda. Teknik tersebut adalah bagian terakhir yang mereka perlukan agar algoritma dapat bekerja lebih cepat daripada algoritma Dijkstra baik pada grafik berarah maupun tidak berarah.

Algoritme yang telah selesai mengiris grafik menjadi beberapa lapisan, bergerak keluar dari sumbernya seperti milik Dijkstra. Namun alih-alih menangani seluruh perbatasan pada setiap langkah, ia menggunakan algoritma Bellman-Ford untuk menentukan node-node yang berpengaruh, bergerak maju dari node-node ini untuk menemukan jalur terpendek ke node-node lain, dan kemudian kembali ke node-node frontier lainnya. Itu tidak selalu menemukan node dalam setiap lapisan dalam urutan peningkatan jarak, sehingga penghalang penyortiran tidak berlaku. Dan jika Anda memotong grafik dengan cara yang benar, grafik tersebut berjalan sedikit lebih cepat daripada versi terbaik algoritma Dijkstra. Ini jauh lebih rumit, mengandalkan banyak bagian yang harus dipasangkan dengan tepat. Namun anehnya, tidak ada satu pun karya yang menggunakan matematika mewah.

“Benda ini mungkin saja ditemukan 50 tahun yang lalu, namun ternyata tidak,” kata Thorup. “Itu membuatnya jauh lebih mengesankan.”

Duan dan timnya berencana untuk mengeksplorasi apakah algoritme tersebut dapat disederhanakan agar menjadi lebih cepat. Dengan hilangnya penghalang penyortiran, waktu proses algoritma baru tidak mendekati batas mendasar yang diketahui oleh para ilmuwan komputer.

“Sebagai seorang yang optimis, saya tidak akan terkejut jika Anda bisa menurunkannya lebih jauh lagi,” kata Tarjan. “Saya yakin ini bukan langkah terakhir dalam proses ini.”

Cerita asli dicetak ulang dengan izin dari Majalah Kuanta, publikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman masyarakat terhadap sains dengan meliput perkembangan dan tren penelitian di bidang matematika serta ilmu fisika dan kehidupan.