Algoritma merupakakan urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dam logis. Bagaimana langkah langkah logis yang digunakan pada komputer untuk menentukan suatu jalur terpendek yang harus dilalui oleh pengguna?
Waze, Google Maps, dan sebagian besar aplikasi navigasi, menggunakan algoritma yang disebut algoritma Dijkstra untuk menemukan rute yang paling efisien.
Waze melihat peta jalan sebagai grafik, terbuat dari nodus - lokasi pada peta, dan tepian - jalan yang menghubungkan lokasi yang berbeda. Saat Anda mencoba menavigasi dari satu simpul ke node lainnya (satu lokasi ke lokasi lain), rute terdiri dari tepi (jalan) yang berbeda yang dapat Anda tempuh. Sebagai contoh, perhatikan peta berikut, dengan lapisan representasi grafik di atasnya:
Misalkan Anda ingin pergi dari titik 25 (pojok kiri atas), ke simpul 23 (kiri tengah). Ada banyak rute yang berbeda yang menghubungkan simpul tersebut, dan setiap rute tersebut didefinisikan oleh serangkaian tepi yang kita ambil dari simpul ke simpul:
- 25-24-23
- 25-27-23
- 25-24-19-18-10-11-17-20-23
Pertanyaannya sekarang agak sederhana - bagaimana kita menemukan semua rute yang mungkin, dan rute mana dari semua kemungkinan yang bisa kita ambil?
Menemukan rute:
Untuk menemukan rute yang mungkin, algoritma Dijkstra menggunakan proses :
- Mulai pada simpul awal (posisi) - pada kasus kita di simpul 25.
- Lihatlah semua simpul yang terhubung ke simpul ini dengan tepi - dalam kasus 24 dan 27 kita.
a. Jika salah satunya adalah node target (lokasi) - berhenti. Kami memiliki keunggulan yang membawa kami ke sana.
b. Jika tidak ada ujung sasarannya, ulangi proses masing-masing node yang ditemukan, gunakan sebagai node awal. Kita sudah punya jalan untuk sampai ke mereka, jadi kalau ada jalan untuk sampai ke target, kita bisa bergabung dengan 2.
Dalam contoh kita, kita akan mulai dengan node 25. Dari sini kita akan menuju ke node 24 dan 27. Karena keduanya tidak menjadi target, kita akan terus berjalan. Dari simpul 24, kita bisa sampai ke simpul 25, 19 dan 23. Dan sebagai 23 adalah target kita, kita bisa menyelesaikannya, dan jalannya adalah: 25-24-23.
Sementara proses ini membawa kita jalan, ini belum tentu yang paling efisien. Bagaimana jika jalan dari 25-24 tersumbat? Kita dapat menjelaskannya dengan biaya.
Biaya rute:
Kita bisa memberi setiap tepi (garis penghubung 2 nodes) biayanya. Biaya itu akan mewakili waktu yang ditempuh untuk menempuh perjalanan tepi (waktu yang ditempuh untuk mengendarai jalan).
Biaya itu akan dipengaruhi oleh banyak parameter:
- Panjang jalan
- Jumlah jalur
- Lampu lalu lintas
- Data lalu lintas (real time / perkiraan)
- Masih banyak lagi…
Pada gambar di atas, Anda bisa melihat sedikit angka di atas setiap tepi - itu biayanya. Kita ingin mencari rute dengan waktu tempuh tercepat.
Kita bisa mengadaptasi algoritma kita sedikit untuk melakukan hal itu:
Letakkan node awal ke dalam antrian prioritas (akan kembali item dengan biaya terendah), dengan biaya 0.
Ulangi:
- Tarik simpul A dengan biaya terendah dari antrian
a. Jika ini adalah node target - berhenti, kita punya jalan!
b. Jika ini bukan simpul target, tarik semua simpul yang terhubung dengannya dengan tepi.
c. Untuk masing-masing node tetangga B ini, masukkan kembali ke antrian, dengan biaya gabungan sampai ke A (dari antrian) ditambah biaya untuk mendapatkan dari A-B.
Algoritma ini tampaknya sederhana, ditemukan oleh ilmuwan komputer Belanda Edsger W. Dijkstra adalah tulang punggung dari setiap aplikasi navigasi modern.
Permainan sebenarnya sekarang hanya mendapatkan data sebanyak mungkin untuk memiliki biaya yang akurat untuk setiap tepi (data lalu lintas, pemetaan yang akurat, dll. …).
Sumber :
Dijkstra’s Algorithm for Shortest Route Path
The Simple, Elegant Algorithm That Makes Google Maps Possible
Edsger W. Dijkstra - Wikipedia
Waze, Google Maps, dan beragai aplikasi navigasi yang lainnya menggunakan Algoritma Dijkstra yang diciptakan oleh Edsger W. Dijkstra dan dipublikasikan pada tahun 1959. Algoritma ini disebut juga algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek untuk membuat sebuah graf berarah dengan bobot-bobot sisi yang bernilai tidak negatif.
Waze berbeda dengan piranti lunak navigasi pada umumnya, dikarenakan peran user yang sangat besardalam berkontribusi untuk informasi-informasi mengenai kecelakan, kemacetan jalan, polisi, maupun bahaya berdasarkan kondisi nyata yang dilaporkan para penggunanya. User juga dapat melakukan pemutakhiran peta, pemberian nomor rumah/bangunan, maupun penandaan lokasi secara pribadi dan langsung yang selanjutnya digunakan waze dalam algoritma pencarian rute teroptimalnya.
Pengaplikasian algoritma Dijsktra dalam system pencarian rute teroptimal pada fitur navigasi piranti lunak Waze sangat penting. Modifikasi terhadap algoritma dijsktra menyebabkan runtime yang jauh lebih cepat daripada algoritma dijkstra yang biasa. Sistem pencarian rute teroptimal masih terus berkembang
Sumber:
Sebagai pengendara, bernavigasi melewati kemacetan lalu lintas dapat berdampak kepada kepala pusing, dan sekarang ada opsi-opsi yang membantu Anda, apakah itu google maps atau sistem yang ada di mobil Anda. Lalu ada Start-up kecil Sillicon Valley yang dikenal dengan Waze dimana CEO dari Waze adalah Noam Bardin.
Lalu algoritma seperti apa yang digunakan Waze untuk menentukan jalur tercepat?
CEO Noam Bardin menjelaskan bahwa ini semua tetang pengambilan informasi dari handphone Anda, seperti mengetahui lokasi Anda, Seberapa cepat perjalanan Anda, mengetahui lokasi orang lain dari suatu komunitas pada waktu tersebut, seberapa cepat perjalanan mereka, membawa semua informasi dan menggabungkannya untuk mengetahui dengan pasti dimana kemacetannya, mengetahui jalan yang lancar dan menggunakan di sekitar rute dimana orang-orang biasa menggunakannya.
Diane Eisner (Kepala global partnerships di Waze) menjelaskan orang-orang yang menggunakan waze saat berkendara dan dari pihak Waze mengambil jejak GPS dan cap waktu dan mengubahnya menjadi lalu lintas yang bersifat real time dimana pengguna dapat menggunakannya. Karena ini merupakan navigasi dan kemacetan lalu lintas, Anda berjalan sesuai dengan rute Anda dan jika dari pihak Waze menemukan sesuatu yang lebih baik, maka mereka akan memberikan rute kepada Anda untuk terhindar dari insiden.
Dapat disimpulkan, algoritma dari waze dimulai dari pengambilan informasi dari pengguna waze (lokasi,kecepatan perjalanan) → Mengambil informasi dari pengguna Waze lain di sekitar lokasi pada waktu yang bersamaan (lokasi, kecepatan perjalanan) → Menggabungkan kedua informasi untuk mengetahui dengan pasti kemacetan yang terjadi → mencari jalur tercepat atau jalur alternatif dengan memanfaatkan informasi seperti lokasi dan kecepatan kendaraan dari pengguna waze, maka semakin memungkinkan mendapatkan jalan tercepat.
Sumber: