Metode Pencarian dan Pelacakan


Posted on 2017-02-15 - by Ali Nardi



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-searchakan 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) sumber : http://elista.akprind.ac.id/upload/files/2532_BAB_4.pdf