Kelebihan dan Kelemahan DFS

 Kelebihan dan Kelemahan DFS

Kelebihan DFS adalah:

  • Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
  • Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah:

  • Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
  • Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

2.2.2. Cara Kerja DFS

Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma DFS:

  1. Masukkan simpul ujung (akar) ke dalam tumpukan
  2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
  3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
  4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan
  5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
  6. Ulangi pencarian dari langkah kedua

2.3. Pencarian Heuristik

Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.

George Poyla (dalam Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah metode dan aturan discovery serta invention” dalam pencarian state space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima .

Pemecahan masalah AI menggunakan heuristik dalam dua situasi dasar (Setiawan. S, 1993), yaitu :

  1. Permasalahan yang mungkin tidak mempunyai solusi yang pasti disebabkan oleh ambiguitas (keraguan/ketidakpastian) mendasar dalam pernyataan permasalahan atau data yang tersedia, contohnya diagnosa kedokteran.
  2. Permasalahan yang boleh jadi memiliki solusi pasti, tetapi biaya komputasinya untuk mendapatkan solusi tersebut mungkin sangat tinggi. Dalam banyak problema (misalnya saja catur), pertumbuhan state space adalah secara kombinatorial eksplosif dengan bayak state yang mungkin meningkat secara eksponensial atau faktorial dengan kedalaman pencarian. Dalam hal ini, exhaustive, yakni teknik pencarian brute force seperti pencarian mendalam pertama dan pencarian meluas pertama mungkin gagal menemukan solusi sehingga heuristik akan menangani kerumitan permasalahan ini dengan panduan pencarian pada sepanjang lintasan yang memeberi harapan melewati state. Dengan mengeliminasi state yang tidak memberi harapan dan turunannya dari ruang tersebut maka algoritma heuristik dapat mengalahkan ledakan kombinatorial dan menemukan penyelesaian yang dapat diterima.

sumber :

https://www.lesotakus.com/peanuts-apk/