🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

1. Menjelaskan konsep heuristik sebagai estimasi biaya
2. Mengimplementasikan Greedy Best-First Search
3. Mengimplementasikan algoritma A*
4. Menjelaskan properti admissibility dan consistency
5. Merancang fungsi heuristik yang baik
6. Menganalisis optimalitas dan kompleksitas A*

📝 Review: Uninformed Search

Pertemuan sebelumnya kita belajar:

• BFS - Eksplorasi per level
• DFS - Eksplorasi sedalam mungkin
• UCS - Eksplorasi berdasarkan g(n)

Masalah: Tidak tahu arah goal!

🔍 Masalah Uninformed Search

BFS/UCS mengeksplorasi ke semua arah termasuk yang menjauh dari goal!

💡 Solusi: Informed Search

"Gunakan pengetahuan tentang domain masalah untuk mengarahkan pencarian!"

Pengetahuan ini disebut HEURISTIK

📚 Apa itu Heuristik?

• h(n) ≥ 0 untuk semua node n
• h(goal) = 0
• Semakin kecil h(n), semakin dekat ke goal

📏 Contoh: Straight-Line Distance

Untuk pencarian rute: jarak garis lurus ke goal

📐 Contoh: Manhattan Distance

Untuk grid-based problems (8-puzzle, pathfinding):

Jumlah jarak horizontal + vertikal setiap tile ke posisi goalnya

🧩 Contoh Manhattan: 8-Puzzle

┌───┬───┬───┐
│ 2 │ 8 │ 3 │
├───┼───┼───┤
│ 1 │ 6 │ 4 │
├───┼───┼───┤
│ 7 │   │ 5 │
└───┴───┴───┘

┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │   │
└───┴───┴───┘

h_Manhattan = 1+1+0+2+2+1+0+2 = 9

🏃 Greedy Best-First Search

Selalu ekspansi node dengan h(n) terkecil

• Hanya menggunakan h(n)
• Mengabaikan biaya yang sudah ditempuh g(n)
• "Greedy" = serakah, pilih yang terlihat terbaik

📝 Algoritma Greedy BFS

def greedy_best_first_search(problem, h):
    frontier = PriorityQueue()  # ordered by h(n)
    frontier.push(initial_state)
    explored = set()
    
    while not frontier.empty():
        node = frontier.pop()  # h(n) terkecil
        
        if goal_test(node):
            return solution(node)
        
        explored.add(node)
        for successor in expand(node):
            if successor not in explored:
                frontier.push(successor)
    
    return failure
                

🔄 Trace Greedy BFS

Arad → Bucharest:

📊 Greedy BFS: Step by Step

1. Start: Arad (h=366)
2. Neighbors: Zerind(374), Sibiu(253), Timisoara(329)
3. Pilih Sibiu → Neighbors: Fagaras(176), RV(193)
4. Pilih Fagaras → Neighbor: Bucharest(0)
5. Goal! Path: Arad→Sibiu→Fagaras→Bucharest

Hanya 4 node diekspansi!

⚠️ Masalah Greedy BFS

Path Greedy: 450 km vs Optimal: 418 km

⭐ Algoritma A*

"Kombinasi terbaik dari UCS dan Greedy!"

• g(n) = biaya aktual dari start ke n
• h(n) = estimasi biaya dari n ke goal
• f(n) = estimasi total cost melalui n

📊 Perbandingan Algoritma

📋 Tabel Perbandingan

📝 Algoritma A*

def a_star_search(problem, h):
    frontier = PriorityQueue()  # ordered by f(n)
    start = Node(initial_state, g=0)
    start.f = start.g + h(start.state)
    frontier.push(start)
    
    while not frontier.empty():
        node = frontier.pop()  # f(n) terkecil
        
        if goal_test(node):
            return solution(node)
        
        for successor in expand(node):
            successor.g = node.g + cost(node, successor)
            successor.f = successor.g + h(successor.state)
            
            if successor not in explored:
                frontier.push(successor)
                

🔄 Trace A*: Arad → Bucharest

Path: Arad→Sibiu→RV→Pitesti→Bucharest = 418 km ✓

📈 A* vs UCS: Efisiensi

Kedua menemukan path optimal 418 km

✅ Admissibility

Contoh: Straight-line distance selalu ≤ jarak jalan

🏆 Teorema Optimalitas A*

A* akan menemukan solusi dengan biaya minimum!

🔗 Consistency (Monotonicity)

Ketidaksamaan segitiga!

📌 Implikasi Consistency

• Setiap consistent heuristic adalah admissible
• f(n) tidak pernah berkurang sepanjang path
• Node yang sudah diekspansi tidak perlu diekspansi lagi
• Graph search dengan consistent h → optimal!

👑 Dominance

Heuristik yang mendominasi → A* lebih efisien!

Contoh: Manhattan > Misplaced Tiles

🧠 Quiz Time!

Soal 1: Jika h(n) = 0 untuk semua n, algoritma apa yang dihasilkan A*?

1. BFS
2. DFS
3. UCS ✓
4. Greedy BFS

Penjelasan: f(n) = g(n) + 0 = g(n)

🧠 Quiz Time!

Soal 2: Mana yang BUKAN properti heuristik admissible?

1. h(n) ≤ h*(n)
2. h(goal) = 0
3. h(n) selalu sama dengan h*(n) ✓
4. h(n) ≥ 0

Admissible = tidak overestimate, bukan harus exact

🛠️ Merancang Heuristik

Teknik: Relaxed Problem

🧩 Relaxation untuk 8-Puzzle

Semakin sedikit relaxation → heuristik lebih informatif

🔀 Kombinasi Heuristik

Jika h₁ dan h₂ keduanya admissible:

Hasilnya:

• ✓ Tetap admissible
• ✓ Mendominasi h₁ dan h₂
• ✓ A* lebih efisien!

📊 Mengapa A* Optimal?

A* ekspansi dalam urutan f-value → goal optimal ditemukan duluan!

⏱️ Kompleksitas A*

⚠️ Memori adalah bottleneck utama A*!

💾 IDA* (Iterative Deepening A*)

Solusi untuk masalah memori:

• Gunakan f-limit sebagai cutoff (bukan depth)
• Setiap iterasi naikkan f-limit
• Space: O(bd) - Linear!
• Tetap optimal dengan h admissible

🎮 Aplikasi A*

🎖️ Aplikasi Pertahanan

• UAV Path Planning - Hindari radar musuh
• SAR Operations - Cari korban optimal
• Tactical Movement - Minimize exposure
• Logistics - Optimal supply routes

🛩️ Heuristik UAV

double heuristic(State n, Target t, vector<Radar>& radars) {
    // Jarak ke target
    double dist = euclideanDistance(n.pos, t.pos);
    
    // Penalti radar
    double penalty = 0;
    for (auto& r : radars) {
        if (distance(n, r) < r.range)
            penalty += r.threat_level;
    }
    
    return dist + RADAR_WEIGHT * penalty;
}
                

🧠 Quiz Time!

Soal 3: Manhattan distance untuk state ini?

Current: [2,1,3,4,5,6,7,8,0]
Goal:    [1,2,3,4,5,6,7,8,0]

1. 1
2. 2 ✓
3. 3
4. 4

Tile 1: jarak 1, Tile 2: jarak 1 → Total = 2

📋 Ringkasan

🔑 Key Takeaways

1. Heuristik = estimasi biaya ke goal
2. A* = UCS + Greedy (terbaik dari keduanya)
3. Admissible h → A* optimal
4. Heuristik lebih baik → A* lebih cepat
5. Relaxed problem → cara membuat heuristik

📅 Pertemuan Berikutnya

• Hill Climbing
• Simulated Annealing
• Algoritma Genetika

📚 Referensi

1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 3.5-3.6
2. Ertel, W. (2017). Introduction to Artificial Intelligence (2nd Ed.). Springer. Chapter 4.
3. CS188 Berkeley AI Materials: https://inst.eecs.berkeley.edu/~cs188/