Algoritma Sederhana, Elegan Yang Membuat Google Map Ada

“Algoritma Dijkstra menunjukkan kepada kita bahwa masalah yang rumit memiliki landasan dasar penyelesaian yang sederhana dan elegan. Dan penerapan algoritma hebat ini tanpa kita sadari telah sering kita gunakan dalam Google Map”

– catatan editor –

Artikel asli dalam Bahasa Inggris oleh: Michael Byrne

Ditranslasikan ke dalam Bahasa Indonesia oleh: Edy Kesuma

Dicek dan ditinjau ulang oleh: Reopan editor

Algoritma adalah ilmu kecerdasan. Sebuah manifestasi alami dari penalaran logis — bentuk matematika induksi secara khusus — suatu algoritma dikatakan baik jika memperlihatkan gambaran singkat yang menitikberatkan ke dalam inti permasalahan. Sifat dan hubungan yang jumlahnya begitu banyak berubah menjadi hubungan berulang yang sederhana, sebuah garis tunggal langkah rekursif yang mencipatakan keterikatan di tengah kerumitan atau kekacauan. Dan untuk melihat jauh kedalam kerumitan itu, diperlukan kecerdasan.

Adalah pelopor pemrograman Edsger W. Dijkstra yang memecahkan hal ini, dan senama dengan algoritmanya yang terus menjadi salah satu hal tercerdas dalam bidang ilmu komputer. Seorang penganjur kesederhanaan dan keeleganan dalam matematika, dia kurang lebih mempercayai bahwa setiap masalah yang rumit memiliki landasan dasar yang bisa dimasuki, sebuah jalan masuk, dan matematika adalah salah satu alat untuk menemukan dan mengeksplorasinya.

Di tahun 1956, Dijkstra bekerja dalam proyek ARMAC, sebuah mesin komputer pararel yang berbasis di Pusat Matematika Belanda (Netherland’s Mathematical Center). Perangkat tersebut merupakan suksesor atau penerus dari mesin ARRA dan ARRA II, yang mana secara esensi merupakan komputer pertama yang dimiliki oleh negara tersebut. Pekerjaannya adalah memprogram mesin itu, dan ketika ARMAC sudah siap untuk penampilan pertama kali di depan umum — setelah kerja keras terpadu selama dua tahun — Djikstra memerlukan contoh permasalahan untuk dipecahkan dengan mesin tersebut.

“Untuk mendemonstrasikan kepada orang-orang yang bukan dari bidang komputer anda harus memiliki contoh kasus non-matematika yang mudah dipahami,” pernyataan Dijkstra saat wawancara tidak lama sebelum dia meninggal di tahun 2002. “Mereka bahkan harus paham akan jawabannya. Jadi saya merancang sebuah program yang dapat menemukan rute tercepat antara dua kota di Belanda, menggunakan peta jalan di Belanda yang sudah dikecilkan, dimana saya memilih 64 kota .”

“Mana rute tercepat yang bisa ditempuh dari Rotterdam ke Groningen?,” kata Dijkstra. “Ini adalah algoritma untuk menemukan rute tercepat yang saya desain dalam 20 menit.”

Google Maps bekerja dengan cara itu bagi kita saat ini dan kita bahkan tidak perlu berpikir tentang proses rumit yang ada di dalamnya. Masalah rute tercepat, sebuah fitur kunci dalam teori graph dengan begitu banyak penerapannya yang jelas dalam kehidupan nyata, begitu dalam dan sangat cepat. Hasilnya dikenal sebagai ledakan kombinasi, dimana jumlah kombinasi berbeda yang didapatkan harus dieksplorasi dari masalah yang diberikan, yang meningkat secara eksponensial.

Hasil dari ledakan ini adalah masalahnya, seperti masalah rute tercepat, bertambah dengan cepat dan secara prakteknya menjadi sulit dihitung, memerlukan jumlah penanganan yang tidak terbatas untuk diselesaikan. Hanya membutuhkan beberapa node dalam peta atau graph yang diberikan untuk jumlah kemungkinan kombinasi mencapai milyaran, dengan kebutuhan waktu yang sangat besar dan tidak masuk akal.

Cara termudah untuk menjelaskan algoritma Dijkstra mungkin dengan sebuah contoh. Bisa dilihat pada gambar graph dibawah, dimana angka yang diberikan adalah bobot dari masing-masing koneksi. (Sebuah bobot bisa saja merupakan sebuah jarak yang sederhana atau setiap beban relatif terkait dengan rute perlintasan koneksi tertentu yang ingin kita minimalkan). Kita akan mencari rute tercepat dari S ke T. Untuk memulainya, kita tetapkan S, posisi awal kita, dengan nilai 0. Diperlukan 0 mill (atau apapun) ke tempat ini karena merupakan titik awal. Selanjutnya, kita melihat titik tetangga dari S, yang bisa kita bayangkan sebagai semacam perbatasan yang perlu dieksplorasi.

Pada iterasi pertama, kita lihat titik terdekat, yang mana diperlukan nilai sejauh 1 unit. Kita tentukan sebuah label untuk titik tersebut dengan nama, A, dan lihat kembali titik perbatasan selanjutnya beserta jaraknya masing-masing. B bernilai 1 unit ( 2 unit dari awal), C bernilai 2 unit (3 unit dari awal), dan juga kita memiliki D, yang mana bernilai 2 unit dari awal. Karena kita mencari rute tercepat dari titik awal, kita dipaksa untuk bergerak ke D dari S (2 unit), dan kita menetapkan nilai 2 unit menuju D. Di perulangan selanjutnya dari algoritma, dari D kita melihat ke titik berikutnya yaitu C, yang mana bernilai 10 unit (12 dari S), namun kita juga melihat kembali pos terdepan yaitu A, dimana kita masih bisa menuju ke C sejauh 2 unit (3 unit dari awal) dan B sejauh 1 unit (2 unit dari awal). Kita tentukan pos terdepan berikutnya di B dan melabelkannya sejauh 2 unit (2 pergerakan dari awal mulai).

Penelurusan kita ke titik B ternyata memberikan hasil yang mengecewakan. Pergerakan yang bisa dilakukan ke T bernilai 10 unit (12 unit dari awal). Dan ini lebih besar dari 2 unit A ke C (3 unit dari awal) dan bernilai sama dengan perjalanan dari S ke C melalui D, salah satu kemungkinan yang bisa dengan aman kita buang (tiba di C hanya dengan 3 unit, dibandingkan 12 unit melalui D). Lalu kita telah ada di C dan jika ini terlihat rumit, sebenarnya tidak begitu. Kita hanya berhati-hati, langkah tentatif dari satu titik ke titik lain, dimana dibuat mengikuti algoritma untuk selalu mempertimbangkan rute tercepat dari awal mulai.

Akhirnya, kembali mengecek B ke T, dimana total nilainya menjadi 12. Di lain hal, pergerakan terakhir ke C memerlukan 1 unit, dengan total jarak tempuh sejauh 4 unit. Permasalahan yang begitu luar biasa kompleks – eksplosif kompleks – bisa diselesaikan dengan elegan, sederhana dan bahkan berintuisi di dalam kertas.

Contoh animasi bentuk Algoritma Dijkstra:

Source: https://en.wikipedia.org/wiki/File:Dijkstras_progress_animation.gif

Dijkstra mengatakan bahwa pemikiran ini muncul ketika dia sedang menghirup aroma kopi di suatu kedai kopi. “Pada faktanya, cerita ini dipublikasikan tahun 1959, tiga tahun sesudahnya,” kata dia. “Publikasi saat itu cukup bagus. Salah satu alasan hal itu begitu bagus adalah saya merancangnya tanpa pensil dan kertas. Tanpa pensil dan kertas kebanyakan anda dipaksa untuk menghindari semua kekompleksitasan. Akhirya algoritma tersebut menjadi, kekaguman saya yang paling besar, salah satu landasan dari kepopuleran saya.”

Hal inilah yang membuat Google Map dapat berpendar kemana-mana, atau paling tidak beberapa varias dari hal itu. Sungguh, ini yang membuat penemuan suatu rute tertentu menjadi memungkinkan. Cukup cerdas melihat ke dalam gangguan atau kerumitan.