PROBACA.COM – Pernah membayangkan harus mencari rute tercepat antara setiap kota, stasiun, komputer, atau bahkan bagian tubuh yang saling terhubung? Kalau jumlah titiknya sedikit, pekerjaan itu mungkin terasa ringan. Tapi ketika jaringannya membesar, komputer bisa kewalahan—seolah diminta memeriksa semua jalan di Jakarta hanya untuk memastikan rute terbaik dari setiap gang ke setiap gang lainnya.
Masalah ini dikenal oleh ilmuwan komputer sebagai All-Pairs Shortest Paths (APSP), yaitu mencari jarak terpendek antara setiap pasangan titik dalam sebuah jaringan. Dalam bahasa yang lebih sederhana, bayangkan peta besar yang berisi titik-titik dan penghubung. Titiknya bisa berupa kota, PC, stasiun kereta bawah tanah, atau organ. Penghubungnya bisa berupa jalan raya, kabel, rel, atau pembuluh darah.
Tantangannya: menghitung jarak terpendek secara tepat untuk jaringan raksasa membutuhkan waktu dan memori yang sangat besar. Pada jaringan yang padat, beberapa metode konvensional memerlukan apa yang disebut waktu kubik. Jika jumlah titik digandakan, beban komputasinya bisa melonjak kira-kira delapan kali lipat. Jaringannya bertambah dua kali, tetapi pekerjaan komputernya membengkak jauh lebih cepat.
Karena itulah para peneliti mencari jalan tengah: bukan selalu jawaban yang sempurna, melainkan perkiraan yang sangat dekat dan bisa dihitung jauh lebih cepat. Algoritma seperti ini disebut algoritma aproksimasi. Ia tidak memeriksa semua kemungkinan rute, tetapi berusaha memberi hasil dengan jaminan kesalahan tertentu.
Salah satu lompatan penting terjadi pada 1996. Saat itu, Dor, Halperin, dan Zwick—sering disebut DHZ—mengembangkan metode yang mampu menghasilkan perkiraan jarak paling banyak dua kali jarak terpendek sebenarnya untuk pasangan titik yang cukup berjauhan. Metode itu juga bekerja dalam waktu yang nyaris optimal.
Jaminan ini dikenal sebagai 2-approximation. Misalnya, rute terpendek antara dua lokasi sebenarnya berjarak 10 kilometer. Perkiraan yang memenuhi jaminan tersebut boleh berada di antara 10 dan 20 kilometer.
Triknya cukup cerdas. Alih-alih memeriksa semua titik dalam jaringan, metode DHZ memilih sejumlah kecil titik yang disebut sampled vertices, atau titik sampel. Titik-titik ini berfungsi seperti jalan pintas informasi. Dengan melihat hubungan melalui titik sampel, komputer bisa memperkirakan jarak tanpa harus menyusuri seluruh kemungkinan rute.
Namun, jalan pintas ini ternyata punya kelemahan tersembunyi.
Untuk dua titik yang berjauhan, strategi tersebut bekerja dengan baik. Bayangkan perjalanan dari Delhi ke Chennai. Karena kedua kota itu sangat jauh, algoritma biasanya bisa menemukan titik sampel yang berada cukup dekat dengan rute terpendek. Hasil perkiraannya pun cenderung tetap berada dalam batas dua kali jarak sebenarnya.
Masalah muncul ketika dua titiknya berdekatan. Misalnya, kita ingin menghitung rute antara dua kawasan di pinggiran Mumbai. Titik sampel mungkin berada terlalu jauh dari koneksi langsung. Akibatnya, algoritma memilih rute yang lebih panjang.
Contohnya, dua titik sebenarnya hanya terhubung melalui jalur dengan dua sisi. Tetapi jalur yang ditemukan lewat titik sampel memiliki lima sisi. Karena lima lebih besar daripada dua kali dua, jaminan “paling banyak dua kali” pun gagal.
Artinya, metode lama hanya bisa memberikan jaminan matematis tersebut untuk pasangan titik yang cukup jauh. Untuk koneksi yang lebih dekat, keakuratannya tidak selalu dapat dipastikan. Keterbatasan ini bertahan hampir tiga dekade.
Sekarang, Dr. Manoj Gupta, Associate Professor di Indian Institute of Technology Gandhinagar, memperkenalkan penyempurnaan yang memperluas jaminan itu ke pasangan titik yang jaraknya jauh lebih dekat.
Gupta mempresentasikan risetnya dalam 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), melalui makalah berjudul “Improved 2-Approximate Shortest Paths for close vertex pairs”. Yang membuat hasil ini penting bukan hanya karena perkiraannya lebih luas, melainkan karena algoritma tersebut tetap mempertahankan waktu kerja keseluruhan seperti pendekatan sebelumnya.
Kunci terobosannya ada pada cara memilih titik sampel. Metode tradisional mengandalkan satu kumpulan titik perwakilan. Gupta menggantinya dengan strategi pengambilan sampel multi-skala, yaitu menyusun informasi jaringan dalam beberapa tingkat atau skala.
Bayangkan kamu mencari alamat di sebuah kota. Kamu mungkin mulai dari peta seluruh kota, lalu mempersempitnya ke kecamatan, kelurahan, sampai gang. Dengan melihat jaringan dalam beberapa skala sekaligus, algoritma bisa menangkap rute-rute pendek yang sebelumnya mungkin terlewat.
Teknik ini menurunkan jarak minimum yang dibutuhkan agar jaminan 2-approximation berlaku, tanpa meningkatkan kompleksitas komputasi keseluruhan. Jadi, jika metode DHZ andal untuk perjalanan jauh seperti Delhi–Chennai, pendekatan Gupta berusaha membawa tingkat keandalan yang sama ke koneksi yang lebih pendek—seperti perjalanan antar-kawasan di pinggiran Mumbai.
Makna utama riset ini bukan sekadar menemukan cara baru untuk menebak jarak. Yang lebih penting, algoritma tersebut dapat memberikan jaminan akurasi matematis yang sama pada rentang jarak yang lebih luas, sambil tetap efisien secara komputasi.
Terobosan seperti ini penting karena jaringan raksasa ada di mana-mana: infrastruktur internet, sistem transportasi, platform media sosial, sampai aplikasi kecerdasan buatan semuanya bergantung pada analisis hubungan antartitik.
Dalam banyak situasi, jawaban yang sangat cepat dan dapat diandalkan lebih berguna daripada jawaban yang sepenuhnya tepat tetapi datang terlalu lama. Terlebih lagi, ketika sebuah jaringan memiliki jumlah koneksi yang luar biasa besar, keseimbangan antara kecepatan dan akurasi menjadi sangat berharga.
Riset Gupta memperkuat dasar matematis dalam perancangan algoritma. Dan nah, batas yang tampak kokoh sejak 1996 ternyata bukan tembok permanen—kadang, cukup dengan melihat jaringan dari beberapa skala, jalan yang terlalu dekat pun akhirnya bisa ditemukan.
***
DISCLAIMER: Sebagian proses pengolahan artikel ini dibantu oleh teknologi AI. Pembaca disarankan memverifikasi kembali data dan informasi melalui sumber resmi atau sumber primer
Disadur dari ScienceDaily
