Kecerdasan Artifisial

Pertemuan 02

Pemecahan Masalah dengan Pencarian
Uninformed Search

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS

šŸŽÆ Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

  1. Memformulasikan masalah sebagai problem pencarian
  2. Memahami representasi search tree dan search graph
  3. Menganalisis algoritma berdasarkan 4 kriteria evaluasi
  4. Mengimplementasikan BFS, DFS, dan UCS
  5. Memilih algoritma yang tepat untuk berbagai masalah

Mengapa Pencarian Penting?

Pada Pertemuan 1, kita belajar tentang agen cerdas

Pertanyaan: Bagaimana agen menemukan urutan aksi untuk mencapai tujuan?

Jawabannya: PENCARIAN

Proses sistematis menemukan urutan aksi dari kondisi awal ke kondisi tujuan

Klasifikasi Algoritma Pencarian

Kategori Karakteristik Contoh
Uninformed Search
(Blind Search)		 Tidak ada info tambahan tentang jarak ke goal BFS, DFS, UCS
Informed Search
(Heuristic Search)		 Menggunakan heuristik untuk estimasi Greedy, A*
(Pertemuan 3)

Komponen Problem Pencarian

  1. State Space (S) - Semua state yang mungkin
  2. Initial State (sā‚€) - Kondisi awal
  3. Actions (A) - Aksi yang tersedia
  4. Transition Model - Result(s, a) ā†’ s'
  5. Goal Test - Apakah sudah tujuan?
  6. Path Cost - Biaya total jalur

šŸ“· Lihat: images/p02-01-komponen-problem-pencarian.png

Contoh: Masalah Romania

Tujuan: Mencari rute dari Arad ke Bucharest

State Space Semua kota di Romania
Initial State Arad
Actions Pergi ke kota tetangga
Goal Test State = Bucharest?
Path Cost Jarak total (km)

šŸ“· Lihat: images/p02-02-peta-romania.png

Contoh: 8-Puzzle

State Awal

724
5ā¬œ6
831
ā†’ ? ā†’

State Tujuan

123
456
78ā¬œ

Actions: Geser kotak kosong (ā†‘ ā†“ ā† ā†’)

šŸ“· Lihat: images/p02-03-8-puzzle.png

Search Tree

Search Tree adalah representasi pohon dari proses pencarian

  • Root = Initial State
  • Node = State
  • Edge = Action
  • Path = Urutan aksi dari root

šŸ“· Lihat: images/p02-04-search-tree.png

Terminologi Penting

Expand Menghasilkan semua child node dari suatu node
Frontier Node yang sudah di-generate tapi belum di-expand
(Open List)
Explored Set State yang sudah di-expand
(Closed List)

4 Kriteria Evaluasi Algoritma

  1. Completeness
    Apakah dijamin menemukan solusi jika ada?
  2. Optimality
    Apakah dijamin menemukan solusi dengan biaya terendah?
  3. Time Complexity
    Berapa banyak node yang di-generate?
  4. Space Complexity
    Berapa banyak node maksimal di memori?

Parameter Kompleksitas

Parameter Simbol Deskripsi
Branching Factor b Jumlah maksimal anak per node
Depth of Goal d Kedalaman goal terdekat
Maximum Depth m Kedalaman maksimal pohon

šŸ“· Lihat: images/p02-05-parameter-kompleksitas.png

Breadth-First Search (BFS)

Eksplorasi semua node pada kedalaman d
sebelum ke kedalaman d+1

Karakteristik:

  • Eksplorasi per level (melebar dulu)
  • Menggunakan Queue (FIFO)
  • Cocok untuk mencari solusi dengan langkah minimum

BFS: Urutan Ekspansi

        [1]           ā† Level 0: Ekspansi pertama
       /   \
     [2]   [3]        ā† Level 1: Ekspansi kedua & ketiga
     / \   / \
   [4][5][6][7]       ā† Level 2: Ekspansi 4, 5, 6, 7

Queue: [1] ā†’ [2,3] ā†’ [3,4,5] ā†’ [4,5,6,7] ā†’ ...

FIFO: Masuk Pertama, Keluar Pertama

šŸ“· Lihat: images/p02-06-bfs-expansion.png

BFS: Pseudocode


def bfs(problem):
    node = Node(problem.initial_state)
    if problem.goal_test(node.state):
        return node.path()
    
    frontier = Queue()  # FIFO
    frontier.enqueue(node)
    explored = set()
    
    while not frontier.is_empty():
        node = frontier.dequeue()
        explored.add(node.state)
        
        for action in problem.actions(node.state):
            child = node.child(problem, action)
            if child.state not in explored:
                if problem.goal_test(child.state):
                    return child.path()
                frontier.enqueue(child)
    return None

BFS: Analisis Kompleksitas

Complete? āœ… Ya (jika b terbatas)
Optimal? āœ… Ya (jika step cost = 1)
Time O(bd)
Space O(bd) šŸ˜°

āš ļø Memori bisa sangat besar!

Depth-First Search (DFS)

Selalu eksplorasi node terdalam di frontier terlebih dahulu

Karakteristik:

  • Eksplorasi mendalam dulu (deep before wide)
  • Menggunakan Stack (LIFO) atau rekursi
  • Memori jauh lebih hemat dari BFS

DFS: Urutan Ekspansi

        [1]           ā† Mulai dari root
       /   \
     [2]   [7]        ā† Kiri dulu, kanan nanti
     / \   
   [3] [6]            ā† Terus ke bawah
   /
 [4]                  ā† Sampai buntu
   \
   [5] ā† backtrack    ā† Lalu backtrack

Stack: [1] ā†’ [2,7] ā†’ [3,6,7] ā†’ [4,6,7] ā†’ ...

LIFO: Masuk Terakhir, Keluar Pertama

šŸ“· Lihat: images/p02-07-dfs-expansion.png

DFS: Analisis Kompleksitas

Complete? āŒ Tidak (bisa infinite loop)
Optimal? āŒ Tidak (bisa temukan solusi lebih dalam)
Time O(bm) šŸ˜° (bisa sangat buruk)
Space O(bm) šŸ˜Š (linear!)

āœ… Keunggulan utama: Space complexity!

Perbandingan Space: BFS vs DFS

Jika b = 10 dan d = 10:

Algoritma Space Estimasi
BFS O(bd) 1010 = 10 miliar node!
DFS O(bm) 10 Ɨ 10 = 100 node

100 juta kali lebih hemat!

Depth-Limited Search (DLS)

DFS dengan batas kedalaman maksimal L

  • Node pada kedalaman L tidak di-expand
  • Menghindari infinite path
  • Masalah: bagaimana memilih L yang tepat?

def depth_limited_search(problem, limit):
    return recursive_dls(Node(problem.initial), problem, limit)

Iterative Deepening Search (IDS)

Jalankan DLS berulang dengan limit meningkat:
L=0, L=1, L=2, ...


def iterative_deepening_search(problem):
    depth = 0
    while True:
        result = depth_limited_search(problem, depth)
        if result != 'cutoff':
            return result
        depth += 1

šŸ“· Lihat: images/p02-08-iterative-deepening.png

IDS: Kombinasi Terbaik!

Complete? āœ… Ya (seperti BFS)
Optimal? āœ… Ya (untuk uniform cost)
Time O(bd) (seperti BFS)
Space O(bd) šŸ˜Š (seperti DFS!)

IDS = Keunggulan BFS + Keunggulan DFS!

IDS: Apakah Ada Overhead?

Bukankah IDS mengulang eksplorasi?

Contoh: b=3, d=3

Algoritma Node Generated
BFS 1+3+9+27 = 40
IDS 1+4+13+40 = 58

Overhead: 58/40 = 1.45Ɨ saja!

Sebagian besar node ada di level terdalam

Uniform-Cost Search (UCS)

Eksplorasi node dengan path cost terendah terlebih dahulu

Mengapa UCS dibutuhkan?

  • BFS optimal hanya untuk uniform step cost
  • Jika step cost bervariasi, butuh UCS
  • Menggunakan Priority Queue

UCS: Mengapa BFS Gagal?

Start -----(cost 10)----ā†’ A -----(cost 1)----ā†’ Goal
  |                                              ā†‘
  +-------(cost 5)------ā†’ B ------(cost 5)------+

BFS path: Start ā†’ A ā†’ Goal (cost = 11)

Optimal path: Start ā†’ B ā†’ Goal (cost = 10)

BFS memilih berdasarkan kedalaman, bukan biaya!

šŸ“· Lihat: images/p02-09-ucs-expansion.png

UCS: Pseudocode


def uniform_cost_search(problem):
    node = Node(problem.initial_state, path_cost=0)
    frontier = PriorityQueue()  # priority = g(n)
    frontier.push(node, priority=node.path_cost)
    explored = set()
    
    while not frontier.is_empty():
        node = frontier.pop()  # cost terendah
        
        if problem.goal_test(node.state):  # test saat expand!
            return node.path()
        
        explored.add(node.state)
        for action in problem.actions(node.state):
            child = node.child(problem, action)
            # ... update frontier jika cost lebih rendah
    return None

UCS: Hal Penting!

āš ļø Goal Test dilakukan saat EXPAND

Bukan saat node di-generate!

Alasan: Node dengan cost lebih rendah bisa muncul kemudian

UCS: Analisis Kompleksitas

Complete? āœ… Ya (jika step cost ā‰„ Īµ > 0)
Optimal? āœ… Ya! šŸŽ‰
Time O(b1+āŒŠC*/ĪµāŒ‹)
Space O(b1+āŒŠC*/ĪµāŒ‹)

C* = biaya solusi optimal, Īµ = step cost minimum

Perbandingan Lengkap

Kriteria BFS DFS IDS UCS
Complete āœ… āŒ āœ… āœ…
Optimal āœ…* āŒ āœ…* āœ…
Time O(bd) O(bm) O(bd) O(bC*/Īµ)
Space O(bd) O(bm) O(bd) O(bC*/Īµ)
Struktur Queue Stack Stack PQueue

* jika step cost uniform

Panduan Pemilihan Algoritma

Situasi Pilih Alasan
Step cost bervariasi UCS Menjamin optimal
Memori terbatas IDS Space O(bd), complete
Perlu solusi tercepat BFS/IDS Solusi terdangkal
State space besar/infinite IDS Complete, hemat memori

šŸ“· Lihat: images/p02-10-flowchart-pemilihan.png

Aplikasi: Konteks Pertahanan

šŸŽÆ Perencanaan Rute Operasi Militer

  • State: Posisi unit di medan
  • Actions: Bergerak ke pos berikutnya
  • Cost: Risiko deteksi, waktu, konsumsi logistik
  • Goal: Mencapai sasaran dengan risiko minimum

ā†’ Gunakan UCS untuk misi dengan risiko minimum!

šŸ§  Quiz Time!

Pertanyaan 1

Algoritma mana yang menggunakan Queue (FIFO)?

  1. DFS
  2. BFS
  3. UCS
  4. IDS

Jawaban: B. BFS

šŸ§  Quiz Time!

Pertanyaan 2

Jika step cost bervariasi, algoritma mana yang menjamin solusi optimal?

  1. BFS
  2. DFS
  3. IDS
  4. UCS

Jawaban: D. UCS

šŸ§  Quiz Time!

Pertanyaan 3

Algoritma mana yang memiliki space complexity paling efisien?

  1. BFS - O(bd)
  2. DFS - O(bm)
  3. IDS - O(bd)
  4. UCS - O(bC*/Īµ)

Jawaban: C. IDS - O(bd)

IDS memiliki keunggulan DFS (space) + keunggulan BFS (complete, optimal)

Ringkasan

  • Problem Pencarian: State Space, Initial, Actions, Transition, Goal, Cost
  • BFS: Queue, complete, optimal (uniform), O(bd) space
  • DFS: Stack, not complete, O(bm) space
  • IDS: DLS berulang, complete, O(bd) space
  • UCS: Priority Queue, optimal untuk semua cost

Pertemuan Berikutnya

Pertemuan 03

Pencarian Heuristik - Informed Search

  • Konsep Heuristik
  • Greedy Best-First Search
  • Algoritma A*
  • Admissibility dan Consistency

Tugas

  1. Implementasikan BFS dan DFS untuk maze solver
  2. Bandingkan jumlah node yang dieksplorasi
  3. Implementasikan UCS untuk graf berbobot
  4. Kerjakan latihan di latihan.md

Deadline: Sebelum Pertemuan 03

šŸ“š Referensi

  1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 3.1-3.4
  2. Poole, D.L. & Mackworth, A.K. (2023). Artificial Intelligence: Foundations of Computational Agents (3rd Ed.). Cambridge University Press. Chapter 3.
  3. CS188 Berkeley AI Materials: https://inst.eecs.berkeley.edu/~cs188/

Terima Kasih

šŸ¤– Kecerdasan Artifisial

Pertemuan 02: Pemecahan Masalah dengan Pencarian - Uninformed Search


Ada pertanyaan?