Blind Search

ALGORITMA GRAPH

· Algoritma traversal di dalam graf adalah mengunjungi simpul – simpul dengan cara yang sistematik.

· Pencarian Melebar ( Breadth First Search atau BFS )

· Pencarian Mendalam ( Depth First Search atau DFS )

1. Breadth First Search atau BFS

Breadth First Search adalah algoritma pencarian simpul dalam graf (pohon) secara traversal yang dimulai dari simpul akar dan mengecek semua simpul – simpul tetangganya. Setelah itu, dari tiap simpul tetangganya, algoritma akan terus mengecek semua simpul tetangganya yang belum dicek. Sedemikian seterusnya hingga menemukan simpul tujuan Breadth First Search. Interpreter kaidah mulai dari fakta yang ada yaitu hipotesa kemudian kaidah bagian THEN mulai di uji untuk mendukung hipotesa awal. Jika ditemukan maka kaidah IF yang cocok digunakan untuk menghasilkan hipotesa antara yang baru. kemudian proses berantai terus di ulang, mengumpulkan bukti yang mendukung, sehingga hipotesa kebenarannya.

Graf Breadth First Search

Breadth First Search merupakan proses penalaran dengan pendekatan proses goal – driven. Memulai titik pendekatannya dari goal yang akan dicari nilainya kemudian bergerak mencari informasi yang mendukung goal tersebut.

Keuntungan BFS:

· Tidak menemui jalan buntu.

· Jika ada suatu solusi, maka Braedth First Search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan BFS:

· Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.

· Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke – ( n + 1 )

· Idenya mirip dengan algo prim dan dijkstra.

· Traversal dimulai dari simpul v.

· Algoritma :

- Kunjungi simpul v,

- Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu,

- Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi di kunjungi, demikian seterusnya.

· Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul – simpul pada aras d + 1.

Representasi BFS

· Pada umumnya graf di representasikan baik secara array ataupun list.

· Dalam kuliah ini menggunakan Link LIST dan queue

Strucut node {

int data;

struct node *link;

};

BFS Properti dan Running Time

· O ( V + E )

· G = ( V, E ), bfs mencari seluruh vertex yang dapat diraih dari source s.

· Untuk setiap vertex pada level l, path bfs tree antara s dan v mempunyai 1 edge dan selain path dalam G antara s dan v setidaaknya mempunyai 1 edge.

· Jika ( u, v ) adalah edge maka jumlah level u dan v dibedakan setidaknya satu tingkat.

· BFS menghitung seluruh jarak terpendek ke seluruh vertex yang dapat di raihnya.

Kegunaan BFS

· Memeriksa apakah graph terhubung.

· Menghitung spanning forest graph.

· Menghitung, tiap vertex dalam graph, jalur dengan jumlah edge menimum antara vertex awal dan current vertex atau ketiadaan path.

· Menghitung cycle dalam graph atau ketiadaan cycle.

· O ( V + E )

Contoh BFS

· Awal simpul adalah v1 dari graf G dibawah

· Kunjungan BFS menghasilkan :

· v1, v2, v5, v3, v4, v7, v6, v8, v9

2. Depth First Search atau DFS

Metode Depth First Search dilakukan dengan node awal secara mendalam hingga yang paling akhir ( dead – end ) sampai ditemukan goal state. Dengan kata lain, simpul cabang anak yang terlebih dahulu dikunjungi. Andaikan tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang berikutnya hingga semua node di kunjungi.

Depth First Search ( DFS ) adalah algoritma pencarian simpul dalam graf secara traversal yang dimulai dari simpul akar dan mengecek simpul anaknya yang pertama, setelah itu, algoritma mengecek simpul anak dari simpul anak yang pertama tersebut, hingga mencapai simpul daun atau simpul tujuan.

· Traversal dimulai dari simpul v.

· Algoritma:

- Kunjungi simpul v,

- Kunjungi simpul w yang bertetangga dengan simpul v

- Ulangi DFS mulai dari simpul w

- Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut – balik ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.

- Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi.

Keuntungan DFS:

· Membutuhkan memori yang relaatif kecil, karena hanya node – node pada lintasan yang aktif yang disimpan.

· Secara kebetulan, metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan DFS:

· Memungkinkan tidak ditemukannya tujuan yang diharapkan

· Hanya akan mendapatkan satu solusi pada setiap pencarian

Untuk memeriksa algoritma diatas, bahwa keadaan – keadaan turunan (descendent) ditambahkan atau dihapuskan dari ujung kiri open. Hasil dari penerapan algoritma.