A. Teknik
Pelacakan
Pelacakan
adalah teknik untuk pencarian :sesuatu”. Didalam pencarian ada dua kemungkinan
hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian
merupakan teknik yang penting dalam AI. Hal penting dalam menentukan
keberhasilan sistem berdasar kecerdasan adalah kesuksesan dalam pencarian dan
pencocokan.
Keberhasilan dan kualitas pencarian diukur adari empat cara yaitu:
1.
Kelengkapan
Apakah algoritma pencarian
menjamin untuk mendapatkan sebuah penyelesaian jika ada penyelesaian ?
2. Optimal
Apakah algoritma pencarian akan
mendapatkan penyeleaian optimal (Misal: penyelesaian dengan biaya lintasan
minimum)
3.
Kekompleksan waktu
Berapa
lama waktu yang digunakan untuk menyelesaian permasalahan ?
4.
Kekompleksan Ruang
Berapa
banyak memori yang dibutuhkan untuk melakukan pencarian
Ada beberapa
teknik pelacakan:
B. Pencarian Buta
Melebar Pertama (Breadth First Search)
Pada metode ini
semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi
node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1
dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari
kiri ke kanan hingga ditemukan solusi. ( lihat
gambar)
Algoritma Breadth First:
1. Buat
suatu variable Node_list dan tetapkan sebagai keadaan awal.
2. Kerjakan
langkag-langkah berikut ini sampai tujuan tercapai atau Node_lIst dalam keadaan
kosong:
a.
Hapus elemen pertama dari Node_list, sebut
dengan nama E. Jika Node_list kosong, maka Keluar.
b.
Pada setiap langkah yang aturannya cocok dengan
E, kerjakan:
-
Aplikasikan aturan tersebut untuk membentuk
sustu keadaan baru.
-
Jika keadaan awal adalah tujuan yang diharapkan,
sukses, dan keluar
-
Jika tidak demikian, tambahkan keadaan awal yang
baru tersebut pada akhir Node_list
Keuntungan:
1.
Tidak akan menemui jalan buntu.
2.
Jika ada satu solusi, maka breadth first search
akan menemukan. Jika ada lebih dari satu solusi, maka solusi minimum akan
ditemukan.
Kelemahan:
1.
Membutuhkan memori yang besar, karena menyimpan
semua node dalam satu pohon.
2.
Membutuhkan waktu yang lama, karena akan menguji
n level untuk mendapatkan solusi pada level yang ke- (n+1).
Analisis Ruang dan Waktu
1. Diasumsikan:
Ada satu solusi (I tujuan ditemukan) pada pohon. Pohon pelacakan memiliki
cabang yang selalu sama, yaitu sebanyak b. Tujuan dicapai pada level ke-d. Tujuan
dicapai pada pertengahan pohon ( kondisi rata-rata)
2. Analisis
Ruang
-
Antrian pertama memiliki 1 keadaan.
-
Setelah mencapai langkah pertama, antrian akan
berisi b keadaan.
-
Pemrosesan setiap b keadaan pada level ke-0 akan
menambahkan b keadaan lagi pada antrian.
-
Sehingga setelah dilakukan pemrosesan semua
keadaan pada level ke-d, maka antrian akan menyimpan keadaan sebanyak b d−1 .
Karena diasumsikan bahwa tujuan terletak di tengah, maka antrian akan menyimpan
b d−1 /2 keadaan (Lihat Gambar)
c.
3. Analisis Waktu
Ukuran waktu diambil
dari banyaknya keadaan yang dikunjungi. Jika tujuan diasumsikan bahwa setiap
node membutuhkan waktu yang sama dalam pemrosesan maka:
·
Waktu = waktu untuk memproses node-node di level 1 +
·
Waktu untuk memproses node-node di level 2 +…+
·
Waktu untuk memproses node-node di level ke-(d-1) +
·
Waktu untuk memproses node-node di level ke-(d)/2
= 1 + b + b 2 + b 3
+…….+ b d−1 + b d /2
= 0 (b d )
C. Pencarian
Mendalam Pertama ( Depth First Search)
Pada Depth First
Search, Proses pencarian akan dilakukan pada semua anak sebelum dilakukan
pencarian ke node-node yang selevel. Pencarian dimulai dari dari node akarke
level yang lebih tinggi. Proses ini diulangi terus hingga ditemukan solusi.
•
termasuk teknik pelacakan sistematis
•
ruang keadaan direpresentasikan dg. diagram pohon mapun grafik
•
asumsi one path is as good as any other
•
ambil salah satu cabang ( left-to-right order)
•
simpul-simpul paling dalam diperiksa lebih dahulu
•
lebih efektif digunakan jika simpul sasaran (Goal) terletak pada
lokasi yang lebih dalam.
Ø
Keuntungan
Membutuhkan memori yang relative kecil,
karena hanya node-node pada lintasan yang aktif saja yang disimpan. Secara
kebetulan, metode ini akan menemukan solusi tanpa harus menguji lebih banyak
lagi yang lain.
Ø
Kelemahan:
Memungkinkan tidak
ditemukannya tujuan yang diharapkan. Hanya akan mendapatkan 1 solusi pada
setiap pencarian
Ø
Analisis Ruang dan Waktu
1.
Analisis Ruang
Setelah
berjalan 1 langkah, stack akan berisi b node.
Setelah
berjalan 2 langkah, stack akan berisi (b-1)+b node
Setelah
berjalan 3 langkah, stack akan berisi (b-1)+(b-1)+b node
Setelah
berjalan d langkah, stack akan berisi (b-1)x d+1, mencapai maksimum
2.
Analisis Waktu
Pada kasus terbaik,
depth-first-search akan mencapai tujuan pada kedalaman d pertama, sehingga
dibutuhkan pencarian sebanyak d+1 node. Pada kasus terburuk ,
depth-first-search akan mencapai tujuan pada kedalaman d pada node
terakhir, sehingga dibutuhkan pencarian sebanyak : 1+b+b 2 +b 3 +….+b d =
(b d +1
-1)/(b-1)
0 komentar:
Posting Komentar