reveal.js

# การแก้ปัญหาด้วยการค้นหาอัจฉริยะ
## Problem Solving by Intelligent Search

**ผู้จัดทำ:** อรรถพล คงหวาน

---

# Outline

1. บทนำสู่การค้นหาอัจฉริยะ (Introduction to Intelligent Search)
2. การกำหนดปัญหา (Problem Formulation)
3. การค้นหาแบบไม่มีข้อมูลนำทาง (Uninformed Search)
4. การค้นหาแบบมีข้อมูลนำทาง (Informed Search)
5. การค้นหาแบบ Local Search
6. การวิเคราะห์และเปรียบเทียบอัลกอริทึม
7. สรุป

---

# 1. บทนำสู่การค้นหาอัจฉริยะ
## Introduction to Intelligent Search

---

# 1.1 ความสำคัญของการค้นหาใน AI

**การค้นหา (Search)** เป็นหัวใจสำคัญของปัญญาประดิษฐ์

ปัญหาส่วนใหญ่ใน AI สามารถมองเป็น:
- การค้นหาเส้นทางจาก **สถานะเริ่มต้น (Initial State)**
- ไปยัง **สถานะเป้าหมาย (Goal State)**
- ผ่าน **ปริภูมิสถานะ (State Space)** ที่กำหนด

---

# การประยุกต์ใช้การค้นหาอัจฉริยะ

| ด้าน | ตัวอย่าง |
|------|---------|
| **การวางแผนเส้นทาง** | GPS Navigation, หุ่นยนต์เคลื่อนที่ |
| **การแก้ปริศนา** | 8-Puzzle, Rubik's Cube |
| **การตัดสินใจ** | ระบบผู้เชี่ยวชาญ, การวินิจฉัยโรค |
| **การเล่นเกม** | หมากรุก, โกะ, เกมกลยุทธ์ |

---

# 1.2 ประวัติความเป็นมาของอัลกอริทึมการค้นหา

```mermaid
flowchart TB
    subgraph era1["ยุคบุกเบิก (1950s-1960s)"]
        style era1 fill:#458588,stroke:#83a598,color:#ebdbb2
        A["1956: Dartmouth Conference"]
        B["1957: GPS - General Problem Solver"]
        C["1959: BFS & DFS"]
    end
    A --> B --> C
    style A fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style B fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style C fill:#3c3836,stroke:#a89984,color:#ebdbb2
```

---

# ประวัติความเป็นมา (ต่อ)

```mermaid
flowchart TB
    subgraph era2["ยุคพัฒนา (1960s-1970s)"]
        style era2 fill:#98971a,stroke:#b8bb26,color:#ebdbb2
        D["1968: A* Algorithm"]
        E["1970: Uniform Cost Search"]
        F["1975: Iterative Deepening"]
    end
    D --> E --> F
    style D fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style E fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style F fill:#3c3836,stroke:#a89984,color:#ebdbb2
```

---

# ประวัติความเป็นมา (ต่อ)

```mermaid
flowchart TB
    subgraph era3["ยุคสมัยใหม่ (1980s-ปัจจุบัน)"]
        style era3 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
        G["1985: IDA*"]
        H["1990s: Heuristic Optimization"]
        I["2000s+: Modern Pathfinding"]
    end
    G --> H --> I
    style G fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style H fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style I fill:#3c3836,stroke:#a89984,color:#ebdbb2
```

---

# 2. การกำหนดปัญหา
## Problem Formulation

---

# 2.1 องค์ประกอบของปัญหาการค้นหา

ปัญหาการค้นหาประกอบด้วย **5 องค์ประกอบหลัก**:

1. **สถานะเริ่มต้น (Initial State)** - จุดเริ่มต้นของปัญหา
2. **การกระทำ (Actions)** - การเปลี่ยนแปลงที่เป็นไปได้
3. **แบบจำลองการเปลี่ยนสถานะ (Transition Model)** - ผลลัพธ์ของการกระทำ
4. **การทดสอบเป้าหมาย (Goal Test)** - ตรวจสอบว่าถึงเป้าหมายหรือยัง
5. **ฟังก์ชันต้นทุนเส้นทาง (Path Cost)** - ค่าใช้จ่ายในการเดินทาง

---

# ตัวอย่าง 8-Puzzle

| องค์ประกอบ | ตัวอย่าง |
|-----------|---------|
| **Initial State** | การจัดเรียงเริ่มต้นของตัวเลข |
| **Actions** | เลื่อนช่องว่างขึ้น/ลง/ซ้าย/ขวา |
| **Transition Model** | RESULT(s, a) = s' |
| **Goal Test** | ตัวเลขเรียงตามลำดับ 1-8 |
| **Path Cost** | จำนวนการเคลื่อนที่ |

---

# 2.2 ปริภูมิสถานะ (State Space)

```mermaid
graph TD
    subgraph statespace["ปริภูมิสถานะ"]
        style statespace fill:#282828,stroke:#a89984,color:#ebdbb2
        S["สถานะเริ่มต้น S₀"]
        S1["สถานะ S₁"]
        S2["สถานะ S₂"]
        G["สถานะเป้าหมาย G"]
        S -->|"cost=1"| S1
        S -->|"cost=2"| S2
        S1 -->|"cost=2"| G
        S2 -->|"cost=1"| G
    end
    style S fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style G fill:#98971a,stroke:#b8bb26,color:#ebdbb2
```

---

# ความหมายของปริภูมิสถานะ

**ปริภูมิสถานะ (State Space)** คือเซตของสถานะทั้งหมดที่เป็นไปได้

สามารถแสดงเป็นกราฟโดยที่:
- **โหนด (Nodes):** แทนสถานะ
- **เส้นเชื่อม (Edges):** แทนการกระทำที่เปลี่ยนสถานะ
- **น้ำหนัก (Weights):** แทนต้นทุนของการกระทำ

---

# 2.3 การวัดประสิทธิภาพของอัลกอริทึม

อัลกอริทึมการค้นหาถูกประเมินด้วยเกณฑ์ **4 ประการ**:

1. **ความสมบูรณ์ (Completeness)** - รับประกันว่าจะพบคำตอบหรือไม่
2. **ความเหมาะสมที่สุด (Optimality)** - คำตอบที่พบเป็นคำตอบที่ดีที่สุดหรือไม่
3. **ความซับซ้อนด้านเวลา (Time Complexity)** - ใช้เวลานานเท่าใด
4. **ความซับซ้อนด้านพื้นที่ (Space Complexity)** - ใช้หน่วยความจำมากเท่าใด

---

# พารามิเตอร์สำคัญ

| พารามิเตอร์ | ความหมาย |
|------------|---------|
| **b** | Branching Factor (จำนวนลูกเฉลี่ยของแต่ละโหนด) |
| **d** | Depth (ความลึกของคำตอบที่ตื้นที่สุด) |
| **m** | Maximum Depth (ความลึกสูงสุดของปริภูมิสถานะ) |

---

# 2.4 ตัวอย่างโค้ด: SearchProblem

```python
class SearchProblem(ABC):
    @abstractmethod
    def initial_state(self) -> State:
        """คืนค่าสถานะเริ่มต้นของปัญหา"""
        pass
    
    @abstractmethod
    def actions(self, state: State) -> List[str]:
        """คืนค่ารายการการกระทำที่เป็นไปได้"""
        pass
```

---

# ตัวอย่างโค้ด: SearchProblem (ต่อ)

```python
    @abstractmethod
    def result(self, state: State, action: str) -> State:
        """คืนค่าสถานะใหม่หลังจากทำการกระทำ"""
        pass
    
    @abstractmethod
    def goal_test(self, state: State) -> bool:
        """ตรวจสอบว่าสถานะเป็นเป้าหมายหรือไม่"""
        pass
    
    def path_cost(self, cost, state1, action, state2) -> float:
        return cost + 1
```

---

# 2.5 คลาส EightPuzzle

```python
class EightPuzzle(SearchProblem):
    GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    
    MOVES = {
        0: {'DOWN': 3, 'RIGHT': 1},
        1: {'DOWN': 4, 'LEFT': 0, 'RIGHT': 2},
        4: {'UP': 1, 'DOWN': 7, 'LEFT': 3, 'RIGHT': 5},
        # ... และอื่นๆ
    }
```

การจัดเรียงบนกระดาน:
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |

---

# ตรวจสอบความสามารถในการแก้ปัญหา

```python
def _is_solvable(self, state: Tuple[int, ...]) -> bool:
    """
    ตรวจสอบว่าปัญหา 8-Puzzle มีคำตอบหรือไม่
    โดยนับจำนวน inversions (คู่ที่ผิดลำดับ)
    ถ้า inversions เป็นเลขคู่ แสดงว่ามีคำตอบ
    """
    inversions = 0
    state_list = [x for x in state if x != 0]
    for i in range(len(state_list)):
        for j in range(i + 1, len(state_list)):
            if state_list[i] > state_list[j]:
                inversions += 1
    return inversions % 2 == 0
```

---

# 3. การค้นหาแบบไม่มีข้อมูลนำทาง
## Uninformed Search / Blind Search

---

# 3.1 ภาพรวมของ Uninformed Search

**Uninformed Search** หรือ **Blind Search** เป็นวิธีการค้นหาที่:
- ไม่มีความรู้เพิ่มเติมเกี่ยวกับปริภูมิสถานะ
- ขยายโหนดตามลำดับที่กำหนดไว้
- ไม่พิจารณาว่าโหนดใดน่าจะใกล้เป้าหมายมากกว่า

---

# ประเภทของ Uninformed Search

```mermaid
graph TD
    subgraph uninformed["Uninformed Search Algorithms"]
        style uninformed fill:#282828,stroke:#a89984,color:#ebdbb2
        ROOT["Uninformed Search"]
        BFS["BFS"]
        DFS["DFS"]
        UCS["UCS"]
        DLS["DLS"]
        IDS["IDS"]
        ROOT --> BFS
        ROOT --> DFS
        ROOT --> UCS
        DFS --> DLS
        DLS --> IDS
    end
    style ROOT fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style BFS fill:#458588,stroke:#83a598,color:#ebdbb2
    style DFS fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style UCS fill:#b16286,stroke:#d3869b,color:#ebdbb2
```

---

# 3.2 Breadth-First Search (BFS)

## หลักการทำงาน

**BFS** ค้นหาโดย:
- ขยายโหนดตามระดับความลึก
- เริ่มจากโหนดรากและขยายโหนดลูกทั้งหมดก่อนลงระดับถัดไป
- ใช้โครงสร้างข้อมูล **Queue (FIFO)**

---

# BFS: ลำดับการขยายโหนด

```mermaid
graph TD
    subgraph bfs["BFS: Level by Level"]
        style bfs fill:#282828,stroke:#a89984,color:#ebdbb2
        A["A Level 0 ขยายที่ 1"]
        B["B Level 1 ขยายที่ 2"]
        C["C Level 1 ขยายที่ 3"]
        D["D Level 2 ขยายที่ 4"]
        E["E Level 2 ขยายที่ 5"]
        A --> B
        A --> C
        B --> D
        B --> E
    end
    style A fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style C fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
```

---

# คุณสมบัติของ BFS

| คุณสมบัติ | ค่า | คำอธิบาย |
|----------|-----|---------|
| **Completeness** | ✅ Yes | รับประกันพบคำตอบ (ถ้า b จำกัด) |
| **Optimality** | ✅ Yes* | หาคำตอบที่สั้นที่สุด (*ถ้าต้นทุนเท่ากันหมด) |
| **Time Complexity** | O(b^d) | ขยายโหนดทั้งหมดจนถึงระดับ d |
| **Space Complexity** | O(b^d) | เก็บโหนดทั้งหมดในหน่วยความจำ |

---

# BFS Implementation

```python
def breadth_first_search(problem) -> Optional[Node]:
    initial_node = Node(state=problem.initial_state())
    
    if problem.goal_test(initial_node.state):
        return initial_node
    
    frontier = deque([initial_node])  # Queue (FIFO)
    explored = set()
```

---

# BFS Implementation (ต่อ)

```python
    while frontier:
        node = frontier.popleft()  # FIFO
        explored.add(node.state.data)
        
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            
            if child_state.data not in explored:
                if problem.goal_test(child_state):
                    return child_node
                frontier.append(child_node)
    return None
```

---

# 3.3 Depth-First Search (DFS)

## หลักการทำงาน

**DFS** ค้นหาโดย:
- ขยายโหนดลึกสุดก่อน
- ลงไปจนถึงใบ (leaf) แล้วจึงย้อนกลับ (backtrack)
- ใช้โครงสร้างข้อมูล **Stack (LIFO)** หรือ Recursion

---

# DFS: ลำดับการขยายโหนด

```mermaid
graph TD
    subgraph dfs["DFS: Depth First"]
        style dfs fill:#282828,stroke:#a89984,color:#ebdbb2
        A["A ขยายที่ 1"]
        B["B ขยายที่ 2"]
        C["C ขยายที่ 5"]
        D["D ขยายที่ 3"]
        E["E ขยายที่ 4"]
        A --> B
        A --> C
        B --> D
        B --> E
    end
    style A fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style D fill:#458588,stroke:#83a598,color:#ebdbb2
```

---

# คุณสมบัติของ DFS

| คุณสมบัติ | ค่า | คำอธิบาย |
|----------|-----|---------|
| **Completeness** | ❌ No* | อาจติดวนซ้ำหรือลงลึกไม่สิ้นสุด |
| **Optimality** | ❌ No | ไม่รับประกันหาคำตอบที่สั้นที่สุด |
| **Time Complexity** | O(b^m) | อาจต้องสำรวจทั้งต้นไม้ |
| **Space Complexity** | O(bm) | เก็บเฉพาะเส้นทางปัจจุบัน |

> **หมายเหตุ:** m = ความลึกสูงสุดของต้นไม้

---

# DFS Implementation

```python
def depth_first_search(problem, max_depth=1000):
    initial_node = Node(state=problem.initial_state())
    
    frontier = [initial_node]  # Stack (LIFO)
    explored = set()
    
    while frontier:
        node = frontier.pop()  # LIFO
        
        if node.depth > max_depth:
            continue
```

---

# DFS Implementation (ต่อ)

```python
        if node.state.data in explored:
            continue
        
        explored.add(node.state.data)
        
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            if child_state.data not in explored:
                if problem.goal_test(child_state):
                    return child_node
                frontier.append(child_node)
    return None
```

---

# 3.4 Uniform Cost Search (UCS)

## หลักการทำงาน

**UCS** ขยายโหนดที่มี **ต้นทุนเส้นทางต่ำที่สุด** ก่อน
- ใช้ **Priority Queue**
- จัดลำดับตาม g(n)

---

# ต้นทุนเส้นทาง g(n)

- **g(n)** = ต้นทุนสะสมจากสถานะเริ่มต้นถึงโหนด n
- **c(sᵢ, aᵢ, sᵢ₊₁)** = ต้นทุนของการกระทำ aᵢ

---

# UCS: ขยายตามต้นทุนต่ำสุด

```mermaid
graph TD
    subgraph ucs["UCS: Lowest Cost First"]
        style ucs fill:#282828,stroke:#a89984,color:#ebdbb2
        A["A g=0"]
        B["B g=1 ขยายที่ 2"]
        C["C g=5 ขยายที่ 5"]
        D["D g=3 ขยายที่ 3"]
        A -->|"cost=1"| B
        A -->|"cost=5"| C
        B -->|"cost=2"| D
    end
    style A fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style D fill:#458588,stroke:#83a598,color:#ebdbb2
```

---

# คุณสมบัติของ UCS

| คุณสมบัติ | ค่า | คำอธิบาย |
|----------|-----|---------|
| **Completeness** | ✅ Yes | รับประกันพบคำตอบ (ถ้าต้นทุน > 0) |
| **Optimality** | ✅ Yes | หาคำตอบที่มีต้นทุนต่ำที่สุดเสมอ |
| **Time** | O(b^(1+⌊C*/ε⌋)) | C* = ต้นทุนคำตอบที่ดีที่สุด |
| **Space** | O(b^(1+⌊C*/ε⌋)) | เก็บโหนดใน Priority Queue |

---

# UCS Implementation

```python
def uniform_cost_search(problem):
    initial_node = Node(state=problem.initial_state(), 
                        path_cost=0)
    
    frontier = PriorityQueue()
    frontier.push(initial_node, initial_node.path_cost)
    
    explored = set()
```

---

# UCS Implementation (ต่อ)

```python
    while len(frontier) > 0:
        node = frontier.pop()  # Lowest cost first
        
        if problem.goal_test(node.state):
            return node
        
        explored.add(node.state.data)
        
        for action in problem.actions(node.state):
            child_cost = problem.path_cost(...)
            if child_state.data not in explored:
                frontier.push(child_node, child_cost)
```

---

# 3.5 Depth-Limited Search (DLS)

## หลักการทำงาน

**DLS** = DFS + ขีดจำกัดความลึก **l (limit)**

- ป้องกันการค้นหาลงลึกไม่สิ้นสุด
- คืนค่า 3 แบบ: SUCCESS, FAILURE, CUTOFF

---

# DLS Implementation

```python
def depth_limited_search(problem, limit: int):
    def recursive_dls(node, limit):
        if problem.goal_test(node.state):
            return (SearchResult.SUCCESS, node)
        
        if limit == 0:
            return (SearchResult.CUTOFF, None)
        
        cutoff_occurred = False
        for action in problem.actions(node.state):
            result, found = recursive_dls(child, limit - 1)
            if result == SearchResult.SUCCESS:
                return (SearchResult.SUCCESS, found)
```

---

# 3.6 Iterative Deepening Search (IDS)

## หลักการทำงาน

**IDS** รวมข้อดีของ BFS และ DFS:
- **Completeness & Optimality** จาก BFS
- **Space Efficiency** จาก DFS

ทำ DLS ซ้ำหลายรอบ เพิ่มขีดจำกัดความลึกทีละหนึ่ง

---

# IDS: กระบวนการค้นหา

```mermaid
graph LR
    subgraph iter0["Iteration 0: limit=0"]
        style iter0 fill:#cc241d,stroke:#fb4934,color:#ebdbb2
        A0["A"]
    end
    subgraph iter1["Iteration 1: limit=1"]
        style iter1 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
        A1["A"]
        B1["B"]
        A1 --> B1
    end
    iter0 -.->|"cutoff"| iter1
```

---

# คุณสมบัติของ IDS

| คุณสมบัติ | ค่า | คำอธิบาย |
|----------|-----|---------|
| **Completeness** | ✅ Yes | เหมือน BFS |
| **Optimality** | ✅ Yes* | หาคำตอบที่ตื้นที่สุด |
| **Time Complexity** | O(b^d) | เหมือน BFS |
| **Space Complexity** | O(bd) | เหมือน DFS |

---

# การวิเคราะห์ความซับซ้อนของ IDS

จำนวนโหนดที่ถูกขยายใน IDS:

---

# Overhead จากการค้นหาซ้ำ

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtext>Overhead</mtext>
  <mo>=</mo>
  <mfrac>
    <mrow>
      <mi>N</mi>
      <mo stretchy="false">(</mo>
      <mi>I</mi>
      <mi>D</mi>
      <mi>S</mi>
      <mo stretchy="false">)</mo>
    </mrow>
    <mrow>
      <mi>N</mi>
      <mo stretchy="false">(</mo>
      <mi>B</mi>
      <mi>F</mi>
      <mi>S</mi>
      <mo stretchy="false">)</mo>
    </mrow>
  </mfrac>
  <mo>=</mo>
  <mfrac>
    <mi>b</mi>
    <mrow>
      <mi>b</mi>
      <mo>−</mo>
      <mn>1</mn>
    </mrow>
  </mfrac>
</math>

**ตัวอย่าง:** ถ้า b = 10, overhead = 10/9 ≈ 1.11 (เพิ่มขึ้นเพียง 11%)

---

# IDS Implementation

```python
def iterative_deepening_search(problem, max_limit=100):
    for depth_limit in range(max_limit + 1):
        result, node = depth_limited_search(problem, depth_limit)
        
        if result == SearchResult.SUCCESS:
            return node
        elif result == SearchResult.FAILURE:
            return None
        # CUTOFF: เพิ่มความลึกและลองใหม่
    return None
```

---

# 3.7 ตารางเปรียบเทียบ Uninformed Search

| อัลกอริทึม | Complete | Optimal | Time | Space | โครงสร้าง |
|-----------|----------|---------|------|-------|----------|
| **BFS** | ✅ | ✅* | O(b^d) | O(b^d) | Queue |
| **DFS** | ❌ | ❌ | O(b^m) | O(bm) | Stack |
| **UCS** | ✅ | ✅ | O(b^(C*/ε)) | O(b^(C*/ε)) | PQ |
| **DLS** | ❌ | ❌ | O(b^l) | O(bl) | Stack |
| **IDS** | ✅ | ✅* | O(b^d) | O(bd) | Stack |

---

# 4. การค้นหาแบบมีข้อมูลนำทาง
## Informed Search / Heuristic Search

---

# 4.1 แนวคิดของฮิวริสติก

**ฮิวริสติก (Heuristic)** คือ **ฟังก์ชันประมาณการ**
- บอกว่าแต่ละสถานะน่าจะใกล้เป้าหมายเพียงใด
- ช่วยให้อัลกอริทึมค้นหาได้อย่างมีทิศทาง

---

# ฟังก์ชันฮิวริสติก h(n)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>h</mi>
  <mo stretchy="false">(</mo>
  <mi>n</mi>
  <mo stretchy="false">)</mo>
  <mo>=</mo>
  <mtext>ค่าประมาณของต้นทุนจาก n ไปยังเป้าหมาย</mtext>
</math>

คุณสมบัติ:
- **h(n) ≥ 0** เสมอ
- **h(goal) = 0** (ที่เป้าหมาย ค่าประมาณเป็น 0)

---

# 4.2 ฟังก์ชันประเมิน

```mermaid
graph LR
    subgraph eval["Evaluation Functions"]
        style eval fill:#282828,stroke:#a89984,color:#ebdbb2
        GN["g(n) ต้นทุนจริง"]
        HN["h(n) ค่าประมาณ"]
        FN["f(n) = g(n) + h(n)"]
        GN --> FN
        HN --> FN
    end
    style GN fill:#458588,stroke:#83a598,color:#ebdbb2
    style HN fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style FN fill:#98971a,stroke:#b8bb26,color:#ebdbb2
```

---

# ตารางฟังก์ชันประเมิน

| ฟังก์ชัน | ความหมาย | ใช้ใน |
|---------|---------|------|
| **g(n)** | ต้นทุนจริงจากสถานะเริ่มต้นถึง n | UCS, A* |
| **h(n)** | ค่าประมาณจาก n ถึงเป้าหมาย | Greedy, A* |
| **f(n) = g(n) + h(n)** | ค่าประเมินรวมผ่าน n | A* |

---

# 4.3 Greedy Best-First Search

## หลักการทำงาน

**Greedy** เลือกขยายโหนดที่มี **h(n) ต่ำที่สุด** เสมอ

**ฟังก์ชันประเมิน:**

ไม่พิจารณาต้นทุนที่ผ่านมา (g(n))

---

# คุณสมบัติของ Greedy Best-First

| คุณสมบัติ | ค่า | คำอธิบาย |
|----------|-----|---------|
| **Completeness** | ❌ No* | อาจติดวนซ้ำ |
| **Optimality** | ❌ No | ไม่รับประกันคำตอบที่ดีที่สุด |
| **Time Complexity** | O(b^m) | กรณีแย่สุด |
| **Space Complexity** | O(b^m) | เก็บโหนดทั้งหมด |

---

# Greedy Implementation

```python
def greedy_best_first_search(problem, heuristic):
    initial_node = Node(state=problem.initial_state())
    
    frontier = PriorityQueue()
    h_initial = heuristic(initial_node.state)
    frontier.push(initial_node, h_initial)  # f(n) = h(n)
    
    explored = set()
```

---

# Greedy Implementation (ต่อ)

```python
    while len(frontier) > 0:
        node = frontier.pop()
        
        if problem.goal_test(node.state):
            return node
        
        explored.add(node.state.data)
        
        for action in problem.actions(node.state):
            h_value = heuristic(child_state)
            frontier.push(child_node, h_value)
```

---

# 4.4 A* Search Algorithm

## หลักการทำงาน

**A*** รวมข้อดีของ UCS และ Greedy:

- **g(n)** = ต้นทุนจริงจากสถานะเริ่มต้นถึง n
- **h(n)** = ค่าประมาณจาก n ถึงเป้าหมาย
- **f(n)** = ค่าประมาณของเส้นทางที่ดีที่สุดผ่าน n

---

# A* Search: การทำงาน

```mermaid
graph TD
    subgraph astar["A* Search"]
        style astar fill:#282828,stroke:#a89984,color:#ebdbb2
        S["S g=0, h=7, f=7"]
        A["A g=1, h=6, f=7"]
        B["B g=4, h=2, f=6 ✓"]
        G["G g=6, h=0, f=6"]
        S -->|"1"| A
        S -->|"4"| B
        B -->|"2"| G
    end
    style S fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style G fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
```

---

# 4.4.2 เงื่อนไขสำหรับ Optimality

**A* จะเป็น Optimal ถ้า h(n) เป็น Admissible:**

โดยที่ **h*(n)** = ต้นทุนจริงจาก n ถึงเป้าหมาย

**Admissible Heuristic:** ไม่ประเมินเกินจริง (never overestimates)

---

# คุณสมบัติของ A*

| คุณสมบัติ | ค่า | เงื่อนไข |
|----------|-----|---------|
| **Completeness** | ✅ Yes | ถ้า b จำกัด และ cost > ε > 0 |
| **Optimality** | ✅ Yes | ถ้า h(n) เป็น admissible |
| **Time** | O(b^(h*-h)) | ขึ้นอยู่กับความแม่นยำของ h |
| **Space** | O(b^d) | เก็บโหนดทั้งหมด |

---

# A* Implementation

```python
def astar_search(problem, heuristic):
    initial_state = problem.initial_state()
    initial_node = Node(state=initial_state, path_cost=0)
    
    h_initial = heuristic(initial_state)
    f_initial = initial_node.path_cost + h_initial
    
    frontier = PriorityQueue()
    frontier.push(initial_node, f_initial)
    
    g_values = {initial_state.data: 0}
```

---

# A* Implementation (ต่อ)

```python
    while len(frontier) > 0:
        node = frontier.pop()
        
        if problem.goal_test(node.state):
            return node  # Optimal solution found!
        
        for action in problem.actions(node.state):
            child_g = problem.path_cost(...)
            if child_g < g_values.get(child_state.data, inf):
                g_values[child_state.data] = child_g
                f_value = child_g + heuristic(child_state)
                frontier.push(child_node, f_value)
```

---

# 4.5 ฟังก์ชันฮิวริสติก

## คุณสมบัติของฮิวริสติกที่ดี

**1. Admissible (ยอมรับได้):**

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>h</mi>
  <mo stretchy="false">(</mo>
  <mi>n</mi>
  <mo stretchy="false">)</mo>
  <mo>≤</mo>
  <msup>
    <mi>h</mi>
    <mo>*</mo>
  </msup>
  <mo stretchy="false">(</mo>
  <mi>n</mi>
  <mo stretchy="false">)</mo>
  <mspace width="1em"/>
  <mtext>สำหรับทุก n</mtext>
</math>

- ไม่ประเมินเกินจริง
- รับประกัน A* หาคำตอบ optimal

---

# Consistent Heuristic

**2. Consistent (สม่ำเสมอ):**

- เป็นไปตาม Triangle Inequality
- **Consistent ⟹ Admissible** (แต่กลับกันไม่จริง)

---

# 4.5.2 ฮิวริสติกสำหรับ 8-Puzzle

## h₁: Misplaced Tiles

```python
def misplaced_tiles(state) -> int:
    """นับจำนวนช่องที่อยู่ผิดตำแหน่ง (ไม่นับช่องว่าง)"""
    goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    count = 0
    for i in range(9):
        if state.data[i] != 0 and state.data[i] != goal[i]:
            count += 1
    return count
```

**Admissible:** ใช่ (ต้องเคลื่อนที่อย่างน้อย 1 ครั้งต่อช่องที่ผิด)

---

# h₂: Manhattan Distance

```python
def manhattan_distance(state) -> int:
    """ผลรวมของระยะทางแนวนอนและแนวตั้ง"""
    goal_positions = {
        1: (0, 0), 2: (0, 1), 3: (0, 2),
        4: (1, 0), 5: (1, 1), 6: (1, 2),
        7: (2, 0), 8: (2, 1), 0: (2, 2)
    }
    total = 0
    for i in range(9):
        tile = state.data[i]
        if tile != 0:
            current = (i // 3, i % 3)
            goal = goal_positions[tile]
            total += abs(current[0]-goal[0]) + abs(current[1]-goal[1])
    return total
```

---

# h₃: Linear Conflict

**Linear Conflict** = Manhattan Distance + penalty

เกิดขึ้นเมื่อ:
- ช่อง 2 ช่องอยู่ในแถว/คอลัมน์เป้าหมายเดียวกัน
- แต่สลับลำดับกัน (ต้องเอาช่องหนึ่งออกไปก่อน)

**ตัวอย่าง:** แถว [3, 1, 2] เป้าหมาย [1, 2, 3]
- 3 และ 1 conflict → บวก 2

---

# ฮิวริสติกสำหรับ Grid Map

```python
def euclidean_distance(current, goal) -> float:
    """ระยะทางยูคลิด - เส้นตรง"""
    x1, y1 = current
    x2, y2 = goal
    return math.sqrt((x2-x1)**2 + (y2-y1)**2)

def manhattan_distance_grid(current, goal) -> int:
    """ระยะทางแมนฮัตตัน - 4 ทิศทาง"""
    return abs(x2-x1) + abs(y2-y1)

def chebyshev_distance(current, goal) -> int:
    """ระยะทางเชบีเชฟ - 8 ทิศทาง"""
    return max(abs(x2-x1), abs(y2-y1))
```

---

# 4.5.3 เปรียบเทียบคุณภาพฮิวริสติก

| ฮิวริสติก | คำอธิบาย | ความแม่นยำ | เวลา |
|----------|---------|-----------|------|
| **h₁: Misplaced** | นับช่องที่ผิดที่ | ต่ำ | เร็ว |
| **h₂: Manhattan** | ผลรวมระยะทาง | ปานกลาง | เร็ว |
| **h₃: Linear Conflict** | Manhattan + Conflict | สูง | ช้ากว่า |
| **h = 0** | ไม่ใช้ฮิวริสติก | ต่ำมาก | เร็วมาก |

---

# หลักการ Dominance

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtext>ถ้า</mtext>
  <mspace width="0.5em"/>
  <msub><mi>h</mi><mn>2</mn></msub>
  <mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo>
  <mo>≥</mo>
  <msub><mi>h</mi><mn>1</mn></msub>
  <mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo>
  <mspace width="0.5em"/>
  <mtext>สำหรับทุก n</mtext>
</math>

แล้ว h₂ **dominate** h₁

**ผลลัพธ์:** ฮิวริสติกที่ dominate จะทำให้ A* ขยายโหนดน้อยกว่าหรือเท่ากัน

---

# 5. การค้นหาแบบ Local Search

---

# 5.1 แนวคิดของ Local Search

**Local Search** เป็นอัลกอริทึมที่:
- ทำงานกับสถานะปัจจุบันเพียงสถานะเดียว
- ไม่เก็บเส้นทางหรือต้นไม้การค้นหา
- เหมาะสำหรับปัญหา **Optimization**

---

# ข้อดีและข้อเสียของ Local Search

**ข้อดี:**
- ใช้หน่วยความจำน้อยมาก O(1)
- สามารถแก้ปัญหาขนาดใหญ่มากได้

**ข้อเสีย:**
- ไม่รับประกันว่าจะพบ Global Optimum
- อาจติดอยู่ที่ Local Optimum

---

# Search Landscape

```mermaid
graph TD
    subgraph landscape["Search Landscape"]
        style landscape fill:#282828,stroke:#a89984,color:#ebdbb2
        LO1["Local Maximum"]
        GO["Global Maximum ⭐"]
        LO2["Local Maximum"]
        START["จุดเริ่มต้น"]
        START -.->|"อาจติด"| LO1
        START -.->|"หลายจุด"| GO
    end
    style LO1 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style GO fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style START fill:#cc241d,stroke:#fb4934,color:#ebdbb2
```

---

# 5.2 Hill Climbing Algorithm

## หลักการทำงาน

**Hill Climbing** เลือกเคลื่อนที่ไปยังสถานะที่ดีกว่าเสมอ

เหมือนการปีนเขาในหมอกที่มองเห็นแค่รอบตัว

---

# Hill Climbing Implementation

```python
def hill_climbing(problem, evaluation, maximize=True):
    current = problem.initial_state()
    current_value = evaluation(current)
    
    while True:
        neighbors = []
        for action in problem.actions(current):
            neighbor = problem.result(current, action)
            neighbors.append((neighbor, evaluation(neighbor)))
```

---

# Hill Climbing Implementation (ต่อ)

```python
        if maximize:
            best, best_value = max(neighbors, key=lambda x: x[1])
        else:
            best, best_value = min(neighbors, key=lambda x: x[1])
        
        # ไม่มีเพื่อนบ้านที่ดีกว่า - หยุด
        if (maximize and best_value <= current_value) or \
           (not maximize and best_value >= current_value):
            break
        
        current, current_value = best, best_value
    
    return current, current_value
```

---

# ข้อจำกัดของ Hill Climbing

1. **Local Maximum/Minimum** - ติดจุดสูงสุด/ต่ำสุดเฉพาะที่
2. **Plateau** - ติดที่ราบสูง (ค่าเท่ากัน)
3. **Ridge** - ติดสันเขาแคบ

---

# First-Choice Hill Climbing

เลือกเพื่อนบ้าน**แรก**ที่ดีกว่าแทนการหาที่ดีที่สุด

```python
def hill_climbing_first_choice(problem, evaluation):
    actions = problem.actions(current)
    random.shuffle(actions)  # สุ่มลำดับ
    
    for action in actions:
        neighbor = problem.result(current, action)
        if evaluation(neighbor) > current_value:
            current = neighbor
            break
```

---

# Random Restart Hill Climbing

ทำ Hill Climbing **หลายรอบ** จากจุดเริ่มต้นแบบสุ่ม

```python
def random_restart_hill_climbing(problem, num_restarts=10):
    best_state, best_value = None, float('-inf')
    
    for i in range(num_restarts):
        state, value = hill_climbing(problem, evaluation)
        if value > best_value:
            best_state, best_value = state, value
    
    return best_state, best_value
```

---

# 5.3 Simulated Annealing

## หลักการทำงาน

ยอมให้เคลื่อนที่ไปทางที่**แย่กว่าได้บ้าง**
โดยความน่าจะเป็นขึ้นกับ "อุณหภูมิ" ที่ลดลงเรื่อยๆ

**ความน่าจะเป็นในการยอมรับ:**

P(accept) = exp(ΔE / T)

---

# Simulated Annealing Implementation

```python
def simulated_annealing(problem, evaluation, schedule):
    current = problem.initial_state()
    
    for t in range(max_iterations):
        T = schedule(t)  # อุณหภูมิ
        if T <= 0:
            break
        
        neighbor = random_neighbor(current)
        delta = evaluation(neighbor) - evaluation(current)
```

---

# Simulated Annealing (ต่อ)

```python
        if delta > 0:
            # ดีกว่า - เคลื่อนที่เสมอ
            current = neighbor
        else:
            # แย่กว่า - เคลื่อนที่ด้วยความน่าจะเป็น
            probability = math.exp(delta / T)
            if random.random() < probability:
                current = neighbor
    
    return current
```

---

# Temperature Schedule

```python
def exponential_schedule(t, T0=1000, alpha=0.995):
    """T(t) = T₀ × α^t"""
    return T0 * (alpha ** t)

def linear_schedule(t, T0=1000, rate=0.1):
    """T(t) = max(0, T₀ - rate × t)"""
    return max(0, T0 - rate * t)
```

---

# เปรียบเทียบ Local Search Algorithms

| อัลกอริทึม | ข้อดี | ข้อเสีย |
|-----------|------|--------|
| **Hill Climbing** | เร็ว, เรียบง่าย | ติด Local Optimum |
| **First-Choice** | เร็วกว่าเมื่อ neighbor มาก | ติด Local Optimum |
| **Random Restart** | หลีกเลี่ยง Local ได้ดี | ช้ากว่า |
| **Simulated Annealing** | หลีกเลี่ยง Local | ต้องปรับ schedule |

---

# 6. การวิเคราะห์และเปรียบเทียบอัลกอริทึม

---

# 6.1 ตารางเปรียบเทียบรวม

| อัลกอริทึม | Complete | Optimal | Time | Space |
|-----------|----------|---------|------|-------|
| **BFS** | ✅ | ✅* | O(b^d) | O(b^d) |
| **DFS** | ❌ | ❌ | O(b^m) | O(bm) |
| **UCS** | ✅ | ✅ | O(b^(C*/ε)) | O(b^(C*/ε)) |
| **IDS** | ✅ | ✅* | O(b^d) | O(bd) |
| **Greedy** | ❌ | ❌ | O(b^m) | O(b^m) |
| **A*** | ✅ | ✅ | O(b^d) | O(b^d) |

---

# 6.2 แผนผังการเลือกอัลกอริทึม

```mermaid
flowchart TD
    START["เริ่มต้น เลือกอัลกอริทึม"]
    Q1{"ต้องการเส้นทาง?"}
    Q2{"มีฮิวริสติก?"}
    SA["Simulated Annealing"]
    ASTAR["A* Search"]
    START --> Q1
    Q1 -->|"ไม่"| SA
    Q1 -->|"ใช่"| Q2
    Q2 -->|"ใช่"| ASTAR
    style START fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style ASTAR fill:#98971a,stroke:#b8bb26,color:#ebdbb2
```

---

# แผนผังการเลือก (ต่อ)

```mermaid
flowchart TD
    Q2{"มีฮิวริสติก?"}
    Q3{"ต้นทุนเท่ากัน?"}
    Q4{"หน่วยความจำจำกัด?"}
    UCS["UCS"]
    BFS["BFS"]
    IDS["IDS"]
    Q2 -->|"ไม่"| Q3
    Q3 -->|"ไม่"| UCS
    Q3 -->|"ใช่"| Q4
    Q4 -->|"ไม่"| BFS
    Q4 -->|"ใช่"| IDS
    style UCS fill:#458588,stroke:#83a598,color:#ebdbb2
    style BFS fill:#458588,stroke:#83a598,color:#ebdbb2
    style IDS fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
```

---

# 6.3 ตัวอย่างการประยุกต์ใช้: Grid Pathfinding

```python
class GridPathfinding:
    def __init__(self, grid, start, goal):
        self.grid = grid  # 0=ว่าง, 1=กำแพง
        self.start = start
        self.goal = goal
        self.directions = [
            (-1, 0, 'UP'), (1, 0, 'DOWN'),
            (0, -1, 'LEFT'), (0, 1, 'RIGHT')
        ]
    
    def heuristic(self, state):
        """Manhattan Distance"""
        row, col = state.data
        return abs(row - self.goal[0]) + abs(col - self.goal[1])
```

---

# การแสดงผลเส้นทาง

```python
def visualize_path(grid, path, start, goal):
    symbols = {0: '·', 1: '█', 2: '○', 3: 'S', 4: 'G'}
    
    display = [row[:] for row in grid]
    for state in path:
        display[state.data[0]][state.data[1]] = 2
    
    display[start[0]][start[1]] = 3
    display[goal[0]][goal[1]] = 4
    
    for row in display:
        print(' '.join(symbols[cell] for cell in row))
```

---

# 7. สรุป

---

# 7.1 ประเด็นสำคัญที่ควรจดจำ

**1. การกำหนดปัญหา (Problem Formulation)**
- เป็นขั้นตอนแรกและสำคัญที่สุด
- ต้องระบุ State Space, Actions, Transition Model, Goal Test, Path Cost

---

# Uninformed Search

**2. Uninformed Search** ไม่ต้องการความรู้เพิ่มเติม:
- **BFS** - หาคำตอบที่ตื้นที่สุด แต่ใช้หน่วยความจำมาก
- **DFS** - ใช้หน่วยความจำน้อย แต่ไม่ Complete
- **IDS** - รวมข้อดีของทั้งคู่ เหมาะสำหรับ unknown depth

---

# Informed Search

**3. Informed Search** ใช้ Heuristic นำทาง:
- **A*** เป็นอัลกอริทึมที่ดีที่สุดเมื่อมี Admissible Heuristic
- คุณภาพของ Heuristic ส่งผลโดยตรงต่อประสิทธิภาพ

---

# Local Search

**4. Local Search** เหมาะสำหรับ Optimization:
- ใช้หน่วยความจำน้อยมาก
- **Simulated Annealing** ช่วยหลีกเลี่ยง Local Optimum

---

# 7.2 การเลือกอัลกอริทึม

**การเลือกอัลกอริทึม** ขึ้นอยู่กับ:
- ต้องการ Optimal หรือไม่?
- มี Heuristic หรือไม่?
- หน่วยความจำจำกัดหรือไม่?
- ปริภูมิสถานะมีขนาดใหญ่แค่ไหน?

---

# 7.3 ทักษะที่ควรฝึกฝน

1. การออกแบบ State Space และ Actions ที่เหมาะสม
2. การสร้าง Heuristic Functions ที่ Admissible และมีคุณภาพสูง
3. การวิเคราะห์ Complexity และเลือกอัลกอริทึมที่เหมาะสม
4. การ Implement อัลกอริทึมการค้นหาด้วย Python

---

# 8. เอกสารอ้างอิง

## หนังสือหลัก
- Russell, S., & Norvig, P. (2021). *Artificial Intelligence: A Modern Approach* (4th Edition)
- Poole, D., & Mackworth, A. (2023). *AI: Foundations of Computational Agents*

## บทความวิจัยสำคัญ
- Hart, P. E., et al. (1968). A Formal Basis for A* Algorithm
- Korf, R. E. (1985). Depth-First Iterative-Deepening

---

# แหล่งเรียนรู้เพิ่มเติม

## แหล่งเรียนรู้ออนไลน์
- Stanford CS221: AI Principles and Techniques
- MIT 6.034: Artificial Intelligence

## เครื่องมือและไลบรารี
- NetworkX - Python Library for Graph Analysis
- python-pathfinding - A* และอัลกอริทึมการหาเส้นทาง

---

# คำถาม - ข้อสงสัย