Scribd
Unggah
4 tayangan2 halaman

Teori Pohon Pencarian dalam AI

Dokumen ini membahas teori dasar pohon pencarian dalam kecerdasan buatan, termasuk jenis pencarian maju dan mundur serta pendekatan pencarian buta dan heuristik. Contoh kasus menggunakan graf kota di Sulawesi Selatan menunjukkan penerapan algoritma BFS dan DFS untuk menemukan jalur terdekat. Kesimpulannya, BFS lebih optimal dalam menemukan jalur terpendek, sedangkan DFS lebih hemat memori namun tidak selalu menjamin solusi optimal.

Diunggah oleh

nurazizafourmady
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd
4 tayangan2 halaman

Teori Pohon Pencarian dalam AI

Dokumen ini membahas teori dasar pohon pencarian dalam kecerdasan buatan, termasuk jenis pencarian maju dan mundur serta pendekatan pencarian buta dan heuristik. Contoh kasus menggunakan graf kota di Sulawesi Selatan menunjukkan penerapan algoritma BFS dan DFS untuk menemukan jalur terdekat. Kesimpulannya, BFS lebih optimal dalam menemukan jalur terpendek, sedangkan DFS lebih hemat memori namun tidak selalu menjamin solusi optimal.

Diunggah oleh

nurazizafourmady
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd

Teori Dasar Pohon Pelacakan / Pencarian

Pohon pencarian (search tree) merupakan representasi hierarkis dari ruang pencarian suatu
masalah. Setiap simpul (node) menyatakan keadaan (state), akar (root) menunjukkan keadaan
awal, simpul daun (leaf) dapat menjadi solusi (goal) atau jalan buntu (dead end). Teknik pencarian
dalam kecerdasan buatan digunakan untuk menemukan solusi melalui penelusuran ruang
keadaan. Dua arah pencarian yang umum digunakan: 1. Pencarian maju (forward search): dimulai
dari keadaan awal menuju tujuan. 2. Pencarian mundur (backward search): dimulai dari keadaan
tujuan untuk melacak ke asal. Pencarian dapat dilakukan dengan dua pendekatan utama: -
Pencarian buta (uninformed / blind search), tanpa informasi tambahan, contoh: Breadth-First
Search (BFS), Depth-First Search (DFS). - Pencarian heuristik (informed search), menggunakan
fungsi evaluasi atau pengetahuan tambahan, contoh: Best-First Search, Hill Climbing, A*. Kriteria
penilaian metode pencarian meliputi: - Completeness (apakah selalu menemukan solusi jika ada). -
Optimality (apakah solusi terbaik ditemukan). - Time Complexity (efisiensi waktu). - Space
Complexity (efisiensi memori).

Referensi:
1 Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
2 Nilsson, N. J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann.
3 Akram Nur Risal, A. (2025). P3 Teknik Pencarian AN (Materi Kuliah).

Penyelesaian Soal
Tugas: Buat graph kota-kota di Sulawesi Selatan (minimal 8 kota saling terhubung), tentukan kota
awal dan tujuan, kemudian cari jalur terdekat menggunakan Graph, BFS, dan DFS.

Contoh Kasus:
Misalkan dipilih 8 kota: Makassar (S), Maros (A), Pangkep (B), Barru (C), Parepare (D), Sidrap (E),
Pinrang (F), Enrekang (G), Toraja (T). Tujuan: dari Makassar (S) ke Toraja (T).

1. Representasi Graph:
S-A-B-C-D-E-F-G-T

2. Pencarian BFS:
BFS menelusuri level demi level dari node akar (S). Jalur yang ditemukan: S → A → B → C → D →
E → F → G → T. BFS menjamin jalur terpendek berdasarkan jumlah edge.

3. Pencarian DFS:
DFS menelusuri cabang terdalam lebih dahulu. Jalur yang mungkin ditemukan: S → A → B → C →
D → E → F → G → T. Namun, jika cabang buntu ditemukan, DFS harus backtracking. DFS tidak
selalu menjamin jalur terpendek, tetapi dapat lebih cepat menemukan solusi bila berada di jalur kiri
terdalam.

Kesimpulan:
BFS lebih terjamin dalam menemukan solusi optimal (jalur terpendek), sedangkan DFS lebih hemat
memori tetapi tidak selalu optimal. Dalam kasus rute kota, BFS lebih sesuai bila ingin kepastian
jarak minimum, sementara DFS bisa lebih efisien pada graph dengan solusi di cabang awal.

Anda mungkin juga menyukai