Metode Pencarian Vertex

E. Metode Pencarian Vertex

Pencarian vertex adalah proses umum dalam graph. Terdapat 2 metoda pencarian, yakni Depth First Search (DFS) dan Breadth First Search (BFS).

a. Depth First Search (DFS)

Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan.Dengan kata lain,simpul cabang atau anak yang terlebih dahulu dikunjungi.

Proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka   pencarian dilanjutkan  ke  cabang  sebelumnya,  turun  ke  bawah  jika  memang masih  ada  cabangnya.  Begitu seterusnya hingga diperoleh tujuan akhir (goal).  Depth First Search, memiliki kelebihan diantaranya adalah cepat mencapai kedalaman ruang pencarian. Jika diketahui bahwa lintasan solusi permasalahan akan  panjang  maka  Depth  First  Search  tidak  akan  memboroskan waktu  untuk  melakukan  sejumlah  besar  keadaan  dangkal  dalam permasalahan graf. Depth First Search jauh lebih efisien untuk ruang pencarian  dengan  banyak  cabang  karena  tidak  perlu  mengeksekusi semua simpul pada suatu level tertentu pada daftar open. Selain itu, Depth  First  Search  memerlukan  memori  yang  relatif  kecil  karena banyak node pada lintasan yang aktif saja yang Selain kelebihan, Depth First Search juga memiliki kelemahan di antaranya adalah memungkinkan tidak ditemukannya tujuan yang diharapkan  dan  hanya  akan  mendapatkan  satu  solusi  pada  setiap pencarian.

b. Breadth First Search (BFS)

Prosedur Breadth First Search (BFS) merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap  level  hingga  keadaan tujuan (goal  state) ditemukan. Atau dengan kata lain, penulusuran   yang   dilakukan   adalah   dengan mengunjungi tiap-tiap node pada level yang sama hingga ditemukan goal  state-nya. 

Implementasi algoritma BFS :

Pengimplementasian BFS dapat ditelusuri dengan  menggunakan daftar (list),   open, dan closed, untuk menelusuri gerakan pencarian di dalam  ruang  keadaan.  Prosedur untuk Breadth First Search dapat dituliskan sebagai berikut:

Pada diatas, state 21 merupakan tujuannya (goal) sehingga bila ditelusuri   menggunakan prosedur  Breadth First Search, diperoleh:

1)     Open = [1]; closed = [ ].

2)     Open = [2, 3, 4]; closed = [1].

3)     Open = [3, 4, 5, 6]; closd = [2, 1].

4)     Open = [4, 5, 6, 7, 8]; closed = [3, 2, 1].

5)     Open = [5, 6, 7, 8, 9, 10]; closed = [4, 3, 2, 1].

6)     Open = [6, 7, 8, 9, 10, 11, 12]; closed = [5, 4, 3, 2, 1].

7)     Open  =  [7,  8,  9,  10,  11,  12,  13]  (karena  12  telah  di-open);

         closed = [6, 5, 4, 3, 2, 1].

8)     Open = [8, 9, 10, 11, 12, 13, 14]; closed = [7, 6, 5, 4, 3, 2, 1].

9)     Dan seterusnya sampai state 21 diperoleh atau open = [ ].

Ada  beberapa  keuntungan  menggunakan  algoritma  Breadth First Search ini, diantaranya adalah tidak akan menemui jalan buntu dan jika ada   satu solusi maka Breadth First Search akan menemukannya, dan jika ada lebih  dari  satu  solusi  maka solusi minimum akan ditemukan.

Namun  ada  tiga  persoalan  utama  berkenaan  dengan  Breadth First Search ini yaitu : 

1) Membutuhkan  memori  yang  lebih  besar,  karena menyimpan semua node dalam satu pohon. 

2) Membutuhkan   sejumlah   besar   pekerjaan,   khususnya   jika lintasan  solusi  terpendek  cukup  panjang,  karena  jumlah  node yang  perlu  diperiksa  bertambah  secara  eksponensial  terhadap panjang lintasan.

3) Tidak relevannya operator akan menambah jumlah node yang harus diperiksa.

Oleh  karena  proses  Breadth  First  Search  mengamati  node  di setiap  level  graf  sebelum  bergerak  menuju  ruang  yang  lebih  dalam maka  mula-mula  semua  keadaan  akan  dicapai  lewat  lintasan  yang terpendek  dari  keadaan  awal.  Oleh  sebab  itu,  proses  ini  menjamin ditemukannya  lintasan  terpendek  dari  keadaan  awal  ke  keadaan tujuan   (akhir).   Lebih   jauh   karena   mula-mula   semua   keadaan ditemukan melalui lintasan terpendek sehingga setiap keadaan  yang ditemui  pada  kali  kedua  didapati  pada  sepanjang  sebuah  lintasan yang sama atau lebih panjang. Kemudian, jika tidak ada kesempatan ditemukannya  keadaan  yang  identik  pada  sepanjang  lintasan  yang lebih baik maka algoritma akan menghapusnya.