Algoritma Greedy
Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan
penyelesaian masalah dengan mencari nilai maksimum sementara pada
setiasp langkahnya. Nilai maksimum sementara ini dikenal dengan istilash
local maximum. Pada kebanyakan kasus, algoritma greedy tidak
akan menghasilkan solusi paling optimal, begitupun algoritma greedy
biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang
cukup cepat.
Sebagai contoh dari penyelesaian masalah algoritma greedy, mari kita
lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan
sehari-hari: mencari jarak terpendek dari peta. Midalkan kita ingin
bergerak dari titik A ke titik B, dan kita telaj menemukan beberapa
jalur dari peta:
Dari peta yang ditampilkan diatas, dapat dilihat bahwa terdapat beberapa
jalur dari titik A ke titik B. Sistem pada petagambar secara otomatis
telah memilih jalur terpendek juga, dengan menggunakan algoritma greedy.
Algoritma a-star/Memory-Bounded A*
Algoritma a-star ditemukan pertamakali oleh Peter Harrt, Nils Nilsson,
dan Bertram Raphael pada tahun 1968 adalah algoritma pencarian rute
terpendek (shortest path) yang merupakan perbaikan dari algoritma BFS
dengan memodifikasi tugas heuristiknya untuk memberikan hasil yang
optimal. Dimana menggabungkan fungsi heuristik dan jarak sesungguhnya.
Refrensi :
https://id.wikipedia.org/wiki/Algoritma_a-star
Tidak ada komentar:
Posting Komentar