algoritma astar dan bfs kelas algoritma

17

Upload: masudah

Post on 16-Feb-2015

407 views

Category:

Documents


35 download

DESCRIPTION

ALgoritma

TRANSCRIPT

Page 1: Algoritma Astar Dan BFS Kelas algoritma
Page 2: Algoritma Astar Dan BFS Kelas algoritma

(Best-First Search) (Best-First Search)

Best First Search (BFS) adalah algoritma

pathfinding yang menggunakan fungsi heuristic

untuk ‘menuntun’ pencarian solusi, dengan

menghitung berapa jauh goal dari node

sekarang. Metode ini merupakan kombinasi dari

metode depth first search dan breadth first

search. Pada metode best-first search, pencarian

di perbolehkan memilih simpul baru yang

memiliki biaya terkecil diantara semua leaf

nodes (simpul-simpul pada level terdalam) yang

pernah dibangkitkan.

Page 3: Algoritma Astar Dan BFS Kelas algoritma

Fungsi Heuristik yang digunakan merupakan prakiraan(estimasi) cost dari initial state ke goal state, yang dinyatakan dengan:Memperhitungkan biaya perkiraan (estimated cost), biaya sebenarnya (actual cost tidak diperhitungkan) dengan hanya memperkirakan biaya perkiraan yang belum tentu kebenarannya oleh karena itu algoritma ini tidak optimal

dimana ,

f’= Fungsievaluasig = cost dari initial state ke current state

f’(n) = g(n)

Page 4: Algoritma Astar Dan BFS Kelas algoritma

Contoh:Misalkan, Simpul S merupakan simpul awal dimulainya penulusuran dan simpul Z adalah simpul yang akan menjadi tujuan.

Page 5: Algoritma Astar Dan BFS Kelas algoritma

Jawaban:Gambar diagram pohon dari kasus diatas

Page 6: Algoritma Astar Dan BFS Kelas algoritma

Algoritma

1.Buat sebuah Antrian, inisialisasi node pertama dengan Root dari tree2. Bila node pertama, jika ≠ GOAL (tujuan) , node dihapus dan diganti dengan anak-ankanya. 3.Bila node pertama=GOAL, maka selesai

Page 7: Algoritma Astar Dan BFS Kelas algoritma
Page 8: Algoritma Astar Dan BFS Kelas algoritma

Masalah utama pada algoritma pathfinding BFS ini adalah cara kerjanya yang terus mencoba bergerak ke arah tujuan/goal, meskipun jalan yang dilaluinya bukan jalan yang benar. Karena BFS hanya memperhitungkan cost untuk mencapai goal dan mengabaikan cost jalan yang sudah ditempuhnya untuk sampai ke current state, maka algoritma tersebut terus maju meskipun jalan yang telah dilaluinya sudah terlalu panjang.

Page 9: Algoritma Astar Dan BFS Kelas algoritma

Algoritma A* (A Star) adalah algoritma pathfinding pengembangan dari algoritma Best First Search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Seperti halnya pada BFS, untuk menemukan solusi,A* juga ‘dituntun’ oleh fungsi heuristic. Pada pencarian rute kasus sederhana, dimana tidak terdapat halangan pada peta, A* bekerja secepat dan seefisien BFS. Pada kasus peta dengan halangan, seperti pada gambar di bawah ini, A* dapat menemukan solusi rute tanpa ‘terjebak’ oleh halangan yang ada.

ALGORITMA A* (A Star)

Page 10: Algoritma Astar Dan BFS Kelas algoritma

Pencarian menggunakan algoritma A*mempunyai prinsip yang sama dengan algoritma BFS, hanya saja dengan 2 faktor tambahan. Setiap sisi mempunyai “cost” yang berbeda-beda, seberapa besar cost untuk pergi dari satu simpul ke simpul yang lain. Cost dari setiap simpul ke simpul tujuan bisa diperkirakan. Ini membantu pencarian, sehingga lebih kecil kemungkinan kita mencari ke arah yang salah. Cost untuk setiap sompul tidak harus berupa jarak. Cost bisa saja berupa waktu bila kita ingin mencari jalan dengan waktu tercepat untuk dilalui. Sebagai contoh, bila kita berkendaraan melewati jalan biasa bisa saja merupakan jarak terdekat, tetapi melewati jalan tol biasanya memakan waktu lebih sedikit.

Page 11: Algoritma Astar Dan BFS Kelas algoritma

Perbedaan cara kerja A* dengan BFS adalah selain memperhitungkan cost dari current state ke tujuan dengan fungsi heuristic (seperti BFS), algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi bila jalan yang telah ditempuh sudah terlalu panjang dan ada jalan lain yang lebih kecil cost-nya namun memberikan posisi yang sama dilihat dari goal, jalan baru yang lebih pendek itulah yang akan dipilih .

Page 12: Algoritma Astar Dan BFS Kelas algoritma

A* menyimpan sebuah himpunan solusi parsial, yaitu jalur yang diambil yang berawal dari titik awal, disimpan dalam sebuah antrian berprioritas(priority queue). Prioritas yang diberikan pada suatu jalur ditentukan oleh fungsi:

Page 13: Algoritma Astar Dan BFS Kelas algoritma

Dalam notasi standar yang dipakai untuk algoritma A* di atas, digunakan g(n) untuk mewakili cost rute dari node awal ke node n. Lalu h(n) mewakili perkiraan cost dari node n ke node goal, yang dihitung dengan fungsi heuristic. A* ‘menyeimbangkan’ kedua nilai ini dalam mencari jalan dari node awal ke node goal. Dalam menentukan node yang akan dikembangkan, algoritma ini akan memilih node dengan nilai f(n) = g(n) + h(n) yang paling kecil

f(n) = g(n) + h(n) (1)

Page 14: Algoritma Astar Dan BFS Kelas algoritma

n S A B C D E F G H J K L M

h(n) 80

80 60 70 85 74 70 0 40 100

30 20 70

Contoh Penggunaan A Star:

Page 15: Algoritma Astar Dan BFS Kelas algoritma
Page 16: Algoritma Astar Dan BFS Kelas algoritma
Page 17: Algoritma Astar Dan BFS Kelas algoritma