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)
