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

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

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

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

การค้นหาอัจฉริยะมีการประยุกต์ใช้ในหลายด้าน:

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

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

flowchart TB
    subgraph era1["ยุคบุกเบิก (1950s-1960s)"]
        style era1 fill:#458588,stroke:#83a598,color:#ebdbb2
        A["1956: Dartmouth Conference
กำเนิด AI"]
        B["1957: GPS - General Problem Solver
โดย Newell & Simon"]
        C["1959: BFS & DFS
อัลกอริทึมค้นหาพื้นฐาน"]
    end
    
    subgraph era2["ยุคพัฒนา (1960s-1970s)"]
        style era2 fill:#98971a,stroke:#b8bb26,color:#ebdbb2
        D["1968: A* Algorithm
โดย Hart, Nilsson, Raphael"]
        E["1970: Uniform Cost Search
การค้นหาตามต้นทุน"]
        F["1975: Iterative Deepening
โดย Korf"]
    end
    
    subgraph era3["ยุคสมัยใหม่ (1980s-ปัจจุบัน)"]
        style era3 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
        G["1985: IDA*
Iterative Deepening A*"]
        H["1990s: Heuristic Optimization
Hill Climbing, Simulated Annealing"]
        I["2000s+: Modern Pathfinding
D*, Jump Point Search"]
    end
    
    A --> B --> C
    C --> D --> E --> F
    F --> G --> H --> I
    
    style A fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style B fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style C fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style D fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style E fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style F fill:#3c3836,stroke:#a89984,color:#ebdbb2
    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 องค์ประกอบหลัก:

องค์ประกอบ	คำอธิบาย	ตัวอย่าง (8-Puzzle)
สถานะเริ่มต้น (Initial State)	จุดเริ่มต้นของปัญหา	การจัดเรียงเริ่มต้นของตัวเลข
การกระทำ (Actions)	การเปลี่ยนแปลงที่เป็นไปได้	เลื่อนช่องว่างขึ้น/ลง/ซ้าย/ขวา
แบบจำลองการเปลี่ยนสถานะ (Transition Model)	ผลลัพธ์ของการกระทำ	RESULT(s, a) = s'
การทดสอบเป้าหมาย (Goal Test)	ตรวจสอบว่าถึงเป้าหมายหรือยัง	ตัวเลขเรียงตามลำดับ 1-8
ฟังก์ชันต้นทุนเส้นทาง (Path Cost)	ค่าใช้จ่ายในการเดินทาง	จำนวนการเคลื่อนที่

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

graph TD
    subgraph statespace["ปริภูมิสถานะ (State Space)"]
        style statespace fill:#282828,stroke:#a89984,color:#ebdbb2
        
        S["สถานะเริ่มต้น
Initial State
S₀"]
        S1["สถานะ S₁"]
        S2["สถานะ S₂"]
        S3["สถานะ S₃"]
        S4["สถานะ S₄"]
        S5["สถานะ S₅"]
        G["สถานะเป้าหมาย
Goal State
G"]
        
        S -->|"action a₁
cost=1"| S1
        S -->|"action a₂
cost=2"| S2
        S1 -->|"action a₃
cost=1"| S3
        S1 -->|"action a₄
cost=3"| S4
        S2 -->|"action a₅
cost=1"| S4
        S3 -->|"action a₆
cost=2"| G
        S4 -->|"action a₇
cost=1"| S5
        S5 -->|"action a₈
cost=1"| G
    end
    
    style S fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style G fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style S1 fill:#458588,stroke:#83a598,color:#ebdbb2
    style S2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style S3 fill:#458588,stroke:#83a598,color:#ebdbb2
    style S4 fill:#458588,stroke:#83a598,color:#ebdbb2
    style S5 fill:#458588,stroke:#83a598,color:#ebdbb2

ปริภูมิสถานะ (State Space) คือเซตของสถานะทั้งหมดที่เป็นไปได้ในปัญหา สามารถแสดงเป็นกราฟโดยที่:

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

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

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

ความสมบูรณ์ (Completeness): รับประกันว่าจะพบคำตอบหรือไม่ ถ้ามีคำตอบอยู่จริง
ความเหมาะสมที่สุด (Optimality): คำตอบที่พบเป็นคำตอบที่ดีที่สุดหรือไม่
ความซับซ้อนด้านเวลา (Time Complexity): ใช้เวลานานเท่าใดในการหาคำตอบ
ความซับซ้อนด้านพื้นที่ (Space Complexity): ใช้หน่วยความจำมากเท่าใด

โดยมีพารามิเตอร์สำคัญ:

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

2.4 ตัวอย่างการกำหนดปัญหาด้วย Python

"""
โมดูลสำหรับการกำหนดปัญหาการค้นหา (Problem Formulation Module)
รองรับการสร้างปัญหาแบบทั่วไปและปัญหา 8-Puzzle

ผู้เขียน: AI Course
วันที่: 2025
"""

from abc import ABC, abstractmethod
from typing import List, Tuple, Set, Optional, Any
from dataclasses import dataclass
import copy


@dataclass(frozen=True)
class State:
    """
    คลาสแทนสถานะทั่วไปในปัญหาการค้นหา
    ใช้ frozen=True เพื่อให้สามารถใช้เป็น key ใน dictionary ได้
    """
    data: tuple  # ข้อมูลสถานะ (ต้องเป็น immutable)


class SearchProblem(ABC):
    """
    คลาสนามธรรมสำหรับปัญหาการค้นหาทั่วไป (Abstract Search Problem)
    
    คลาสลูกต้อง implement เมธอดต่อไปนี้:
    - initial_state(): คืนค่าสถานะเริ่มต้น
    - actions(state): คืนค่าการกระทำที่เป็นไปได้ในสถานะนั้น
    - result(state, action): คืนค่าสถานะใหม่หลังทำ action
    - goal_test(state): ตรวจสอบว่าถึงเป้าหมายหรือยัง
    - path_cost(cost, state1, action, state2): คำนวณต้นทุนเส้นทาง
    """
    
    @abstractmethod
    def initial_state(self) -> State:
        """คืนค่าสถานะเริ่มต้นของปัญหา"""
        pass
    
    @abstractmethod
    def actions(self, state: State) -> List[str]:
        """คืนค่ารายการการกระทำที่เป็นไปได้ในสถานะที่กำหนด"""
        pass
    
    @abstractmethod
    def result(self, state: State, action: str) -> State:
        """คืนค่าสถานะใหม่หลังจากทำการกระทำ"""
        pass
    
    @abstractmethod
    def goal_test(self, state: State) -> bool:
        """ตรวจสอบว่าสถานะเป็นเป้าหมายหรือไม่"""
        pass
    
    def path_cost(self, cost: float, state1: State, 
                  action: str, state2: State) -> float:
        """
        คำนวณต้นทุนเส้นทางสะสม
        ค่า default คือ ต้นทุนเดิม + 1 (uniform cost)
        """
        return cost + 1


class EightPuzzle(SearchProblem):
    """
    คลาสสำหรับปัญหา 8-Puzzle
    
    สถานะแสดงด้วย tuple ขนาด 9 โดยที่ 0 แทนช่องว่าง
    ตัวอย่าง: (1, 2, 3, 4, 5, 6, 7, 8, 0) คือสถานะเป้าหมาย
    
    การจัดเรียงบนกระดาน:
    | 0 | 1 | 2 |
    | 3 | 4 | 5 |
    | 6 | 7 | 8 |
    """
    
    # สถานะเป้าหมายมาตรฐาน
    GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    
    # การเคลื่อนที่ที่เป็นไปได้ของช่องว่างในแต่ละตำแหน่ง
    # key = ตำแหน่งช่องว่าง, value = dict ของ action -> ตำแหน่งใหม่
    MOVES = {
        0: {'DOWN': 3, 'RIGHT': 1},
        1: {'DOWN': 4, 'LEFT': 0, 'RIGHT': 2},
        2: {'DOWN': 5, 'LEFT': 1},
        3: {'UP': 0, 'DOWN': 6, 'RIGHT': 4},
        4: {'UP': 1, 'DOWN': 7, 'LEFT': 3, 'RIGHT': 5},
        5: {'UP': 2, 'DOWN': 8, 'LEFT': 4},
        6: {'UP': 3, 'RIGHT': 7},
        7: {'UP': 4, 'LEFT': 6, 'RIGHT': 8},
        8: {'UP': 5, 'LEFT': 7}
    }
    
    def __init__(self, initial: Tuple[int, ...]):
        """
        สร้างปัญหา 8-Puzzle ด้วยสถานะเริ่มต้นที่กำหนด
        
        Args:
            initial: tuple ขนาด 9 แทนสถานะเริ่มต้น
        
        Raises:
            ValueError: ถ้าสถานะไม่ถูกต้อง
        """
        # ตรวจสอบความถูกต้องของสถานะเริ่มต้น
        if len(initial) != 9 or set(initial) != set(range(9)):
            raise ValueError("สถานะต้องมีตัวเลข 0-8 ครบทุกตัว")
        
        # ตรวจสอบว่าปัญหามีคำตอบหรือไม่ (solvability check)
        if not self._is_solvable(initial):
            raise ValueError("ปัญหานี้ไม่มีคำตอบ (unsolvable)")
        
        self._initial = State(data=initial)
    
    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
    
    def initial_state(self) -> State:
        """คืนค่าสถานะเริ่มต้น"""
        return self._initial
    
    def actions(self, state: State) -> List[str]:
        """
        คืนค่าการเคลื่อนที่ที่เป็นไปได้
        
        Returns:
            รายการการกระทำ เช่น ['UP', 'DOWN', 'LEFT', 'RIGHT']
        """
        # หาตำแหน่งของช่องว่าง (0)
        blank_pos = state.data.index(0)
        return list(self.MOVES[blank_pos].keys())
    
    def result(self, state: State, action: str) -> State:
        """
        คำนวณสถานะใหม่หลังทำการเคลื่อนที่
        
        Args:
            state: สถานะปัจจุบัน
            action: การกระทำ ('UP', 'DOWN', 'LEFT', 'RIGHT')
        
        Returns:
            สถานะใหม่หลังทำการกระทำ
        """
        # หาตำแหน่งช่องว่าง
        blank_pos = state.data.index(0)
        
        # หาตำแหน่งใหม่ของช่องว่าง
        new_blank_pos = self.MOVES[blank_pos][action]
        
        # สร้างสถานะใหม่โดยสลับตำแหน่ง
        new_data = list(state.data)
        new_data[blank_pos], new_data[new_blank_pos] = \
            new_data[new_blank_pos], new_data[blank_pos]
        
        return State(data=tuple(new_data))
    
    def goal_test(self, state: State) -> bool:
        """ตรวจสอบว่าถึงเป้าหมายหรือยัง"""
        return state.data == self.GOAL
    
    def display(self, state: State) -> str:
        """แสดงสถานะในรูปแบบกระดาน"""
        board = ""
        for i in range(0, 9, 3):
            row = state.data[i:i+3]
            board += "| " + " | ".join(
                str(x) if x != 0 else " " for x in row
            ) + " |\n"
        return board


# ==================== ตัวอย่างการใช้งาน ====================

if __name__ == "__main__":
    # สร้างปัญหา 8-Puzzle
    initial_state = (1, 2, 3, 4, 0, 5, 7, 8, 6)
    
    print("=" * 50)
    print("ตัวอย่างการใช้งานคลาส EightPuzzle")
    print("=" * 50)
    
    try:
        puzzle = EightPuzzle(initial_state)
        
        # แสดงสถานะเริ่มต้น
        print("\nสถานะเริ่มต้น (Initial State):")
        print(puzzle.display(puzzle.initial_state()))
        
        # แสดงการกระทำที่เป็นไปได้
        actions = puzzle.actions(puzzle.initial_state())
        print(f"การกระทำที่เป็นไปได้: {actions}")
        
        # ทดลองทำการกระทำ
        if 'DOWN' in actions:
            new_state = puzzle.result(puzzle.initial_state(), 'DOWN')
            print(f"\nหลังเลื่อนลง (DOWN):")
            print(puzzle.display(new_state))
        
        # ตรวจสอบเป้าหมาย
        print(f"ถึงเป้าหมายแล้วหรือยัง: {puzzle.goal_test(puzzle.initial_state())}")
        
        # แสดงสถานะเป้าหมาย
        print("\nสถานะเป้าหมาย (Goal State):")
        goal_state = State(data=EightPuzzle.GOAL)
        print(puzzle.display(goal_state))
        
    except ValueError as e:
        print(f"Error: {e}")

ผลลัพธ์การทำงาน:

==================================================
ตัวอย่างการใช้งานคลาส EightPuzzle
==================================================

สถานะเริ่มต้น (Initial State):
| 1 | 2 | 3 |
| 4 |   | 5 |
| 7 | 8 | 6 |

การกระทำที่เป็นไปได้: ['UP', 'DOWN', 'LEFT', 'RIGHT']

หลังเลื่อนลง (DOWN):
| 1 | 2 | 3 |
| 4 | 8 | 5 |
| 7 |   | 6 |

ถึงเป้าหมายแล้วหรือยัง: False

สถานะเป้าหมาย (Goal State):
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 |   |

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

3.1 ภาพรวมของการค้นหาแบบไม่มีข้อมูลนำทาง

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

graph TD
    subgraph uninformed["Uninformed Search Algorithms"]
        style uninformed fill:#282828,stroke:#a89984,color:#ebdbb2
        
        ROOT["Uninformed Search
การค้นหาแบบไม่มีข้อมูลนำทาง"]
        
        BFS["BFS
Breadth-First Search
ค้นหาตามกว้าง"]
        DFS["DFS
Depth-First Search
ค้นหาตามลึก"]
        UCS["UCS
Uniform Cost Search
ค้นหาตามต้นทุน"]
        DLS["DLS
Depth-Limited Search
ค้นหาจำกัดความลึก"]
        IDS["IDS
Iterative Deepening
ค้นหาลึกขึ้นเรื่อยๆ"]
        
        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
    style DLS fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
    style IDS fill:#cc241d,stroke:#fb4934,color:#ebdbb2

3.2 การค้นหาตามกว้าง (Breadth-First Search - BFS)

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

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

graph TD
    subgraph bfs_example["BFS: ลำดับการขยายโหนด"]
        style bfs_example 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"]
        F["F
Level 2
ขยายที่ 6"]
        G["G ⭐
Level 2
Goal!"]
        
        A --> B
        A --> C
        B --> D
        B --> E
        C --> F
        C --> G
    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
    style D fill:#458588,stroke:#83a598,color:#ebdbb2
    style E fill:#458588,stroke:#83a598,color:#ebdbb2
    style F fill:#458588,stroke:#83a598,color:#ebdbb2
    style G fill:#98971a,stroke:#b8bb26,color:#ebdbb2

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

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

3.2.3 การ Implement BFS

"""
โมดูล Breadth-First Search (BFS)
การค้นหาตามกว้างสำหรับปัญหาการค้นหาทั่วไป
"""

from collections import deque
from typing import List, Optional, Tuple
from dataclasses import dataclass


@dataclass
class Node:
    """
    โหนดในต้นไม้การค้นหา (Search Tree Node)
    
    Attributes:
        state: สถานะที่โหนดนี้แทน
        parent: โหนดแม่ (None สำหรับโหนดราก)
        action: การกระทำที่นำมาสู่โหนดนี้
        path_cost: ต้นทุนสะสมจากโหนดเริ่มต้น
        depth: ความลึกของโหนด (ระยะห่างจากราก)
    """
    state: any
    parent: Optional['Node'] = None
    action: Optional[str] = None
    path_cost: float = 0
    depth: int = 0
    
    def __hash__(self):
        return hash(self.state.data)
    
    def __eq__(self, other):
        return self.state.data == other.state.data


def get_solution_path(node: Node) -> List[Tuple[str, any]]:
    """
    สร้างเส้นทางคำตอบจากโหนดเป้าหมายย้อนกลับไปยังโหนดเริ่มต้น
    
    Args:
        node: โหนดเป้าหมาย
    
    Returns:
        รายการของ (action, state) จากเริ่มต้นถึงเป้าหมาย
    """
    path = []
    current = node
    
    while current.parent is not None:
        path.append((current.action, current.state))
        current = current.parent
    
    path.reverse()  # กลับลำดับให้เริ่มจากต้น
    return path


def breadth_first_search(problem) -> Optional[Node]:
    """
    อัลกอริทึม Breadth-First Search
    
    ค้นหาเส้นทางจากสถานะเริ่มต้นไปยังเป้าหมาย
    โดยขยายโหนดตามลำดับความลึก (level by level)
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    Time Complexity: O(b^d)
    Space Complexity: O(b^d)
    
    โดยที่:
        b = branching factor (จำนวนลูกเฉลี่ย)
        d = ความลึกของคำตอบ
    """
    # สร้างโหนดเริ่มต้น
    initial_node = Node(
        state=problem.initial_state(),
        parent=None,
        action=None,
        path_cost=0,
        depth=0
    )
    
    # ตรวจสอบว่าสถานะเริ่มต้นเป็นเป้าหมายหรือไม่
    if problem.goal_test(initial_node.state):
        return initial_node
    
    # สร้าง frontier เป็น Queue (FIFO)
    frontier = deque([initial_node])
    
    # สร้าง explored set เพื่อเก็บสถานะที่สำรวจแล้ว
    explored = set()
    
    # สร้าง frontier_states เพื่อตรวจสอบสถานะใน frontier
    frontier_states = {initial_node.state.data}
    
    # ตัวนับจำนวนโหนดที่ขยาย
    nodes_expanded = 0
    
    while frontier:
        # ดึงโหนดออกจาก frontier (FIFO)
        node = frontier.popleft()
        frontier_states.remove(node.state.data)
        
        # เพิ่มสถานะเข้า explored set
        explored.add(node.state.data)
        nodes_expanded += 1
        
        # ขยายโหนด: พิจารณาทุกการกระทำที่เป็นไปได้
        for action in problem.actions(node.state):
            # สร้างโหนดลูก
            child_state = problem.result(node.state, action)
            child_node = Node(
                state=child_state,
                parent=node,
                action=action,
                path_cost=problem.path_cost(
                    node.path_cost, node.state, action, child_state
                ),
                depth=node.depth + 1
            )
            
            # ตรวจสอบว่าสถานะลูกไม่อยู่ใน explored และ frontier
            if (child_state.data not in explored and 
                child_state.data not in frontier_states):
                
                # ตรวจสอบเป้าหมาย
                if problem.goal_test(child_state):
                    print(f"BFS: พบคำตอบ! ขยายโหนดทั้งหมด {nodes_expanded} โหนด")
                    print(f"ความลึกของคำตอบ: {child_node.depth}")
                    return child_node
                
                # เพิ่มโหนดลูกเข้า frontier
                frontier.append(child_node)
                frontier_states.add(child_state.data)
    
    # ไม่พบคำตอบ
    print(f"BFS: ไม่พบคำตอบ ขยายโหนดทั้งหมด {nodes_expanded} โหนด")
    return None


# ==================== ตัวอย่างการใช้งาน ====================

if __name__ == "__main__":
    # ทดสอบกับ 8-Puzzle (ใช้คลาสจากตัวอย่างก่อนหน้า)
    # สถานะเริ่มต้นที่ใกล้กับเป้าหมาย (ต้องการ 2 การเคลื่อนที่)
    initial = (1, 2, 3, 4, 5, 0, 7, 8, 6)
    
    print("=" * 50)
    print("ทดสอบ BFS กับปัญหา 8-Puzzle")
    print("=" * 50)
    
    puzzle = EightPuzzle(initial)
    
    print("\nสถานะเริ่มต้น:")
    print(puzzle.display(puzzle.initial_state()))
    
    # ค้นหาด้วย BFS
    result = breadth_first_search(puzzle)
    
    if result:
        print("\nเส้นทางคำตอบ:")
        path = get_solution_path(result)
        
        current_state = puzzle.initial_state()
        for i, (action, state) in enumerate(path, 1):
            print(f"\nขั้นตอนที่ {i}: {action}")
            print(puzzle.display(state))

3.3 การค้นหาตามลึก (Depth-First Search - DFS)

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

DFS ค้นหาโดยขยายโหนดลึกสุดก่อน ลงไปจนถึงใบ (leaf) แล้วจึงย้อนกลับ (backtrack) ใช้โครงสร้างข้อมูล สแตก (Stack) แบบ LIFO (Last-In-First-Out) หรือการเรียกซ้ำ (Recursion)

graph TD
    subgraph dfs_example["DFS: ลำดับการขยายโหนด"]
        style dfs_example fill:#282828,stroke:#a89984,color:#ebdbb2
        
        A["A
ขยายที่ 1"]
        B["B
ขยายที่ 2"]
        C["C
ขยายที่ 6"]
        D["D
ขยายที่ 3"]
        E["E
ขยายที่ 5"]
        F["F
ขยายที่ 7"]
        G["G ⭐
Goal!
ขยายที่ 8"]
        H["H
ขยายที่ 4
(dead end)"]
        
        A --> B
        A --> C
        B --> D
        B --> E
        D --> H
        C --> F
        C --> G
    end
    
    style A fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style C fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
    style D fill:#458588,stroke:#83a598,color:#ebdbb2
    style E fill:#b16286,stroke:#d3869b,color:#ebdbb2
    style F fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style G fill:#fabd2f,stroke:#d79921,color:#282828
    style H fill:#928374,stroke:#a89984,color:#ebdbb2

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

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

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

3.3.3 การ Implement DFS

"""
โมดูล Depth-First Search (DFS)
การค้นหาตามลึกสำหรับปัญหาการค้นหาทั่วไป
"""


def depth_first_search(problem, max_depth: int = 1000) -> Optional[Node]:
    """
    อัลกอริทึม Depth-First Search
    
    ค้นหาโดยขยายโหนดลึกสุดก่อน ใช้ Stack (LIFO)
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        max_depth: ความลึกสูงสุดที่อนุญาต (ป้องกันการลงลึกไม่สิ้นสุด)
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    Time Complexity: O(b^m)
    Space Complexity: O(bm)
    """
    # สร้างโหนดเริ่มต้น
    initial_node = Node(
        state=problem.initial_state(),
        parent=None,
        action=None,
        path_cost=0,
        depth=0
    )
    
    # ตรวจสอบเป้าหมาย
    if problem.goal_test(initial_node.state):
        return initial_node
    
    # สร้าง frontier เป็น Stack (LIFO) - ใช้ list
    frontier = [initial_node]
    
    # สร้าง explored set
    explored = set()
    
    nodes_expanded = 0
    
    while frontier:
        # ดึงโหนดออกจาก Stack (LIFO)
        node = frontier.pop()
        
        # ข้ามถ้าเกินความลึกที่กำหนด
        if node.depth > max_depth:
            continue
        
        # ข้ามถ้าสถานะนี้ถูกสำรวจแล้ว
        if node.state.data in explored:
            continue
        
        explored.add(node.state.data)
        nodes_expanded += 1
        
        # ขยายโหนด
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            
            if child_state.data not in explored:
                child_node = Node(
                    state=child_state,
                    parent=node,
                    action=action,
                    path_cost=problem.path_cost(
                        node.path_cost, node.state, action, child_state
                    ),
                    depth=node.depth + 1
                )
                
                # ตรวจสอบเป้าหมาย
                if problem.goal_test(child_state):
                    print(f"DFS: พบคำตอบ! ขยายโหนด {nodes_expanded} โหนด")
                    print(f"ความลึกของคำตอบ: {child_node.depth}")
                    return child_node
                
                frontier.append(child_node)
    
    print(f"DFS: ไม่พบคำตอบ ขยายโหนด {nodes_expanded} โหนด")
    return None


def depth_first_search_recursive(problem, node: Node = None, 
                                  explored: set = None,
                                  max_depth: int = 1000) -> Optional[Node]:
    """
    DFS แบบ Recursive
    
    เหมาะสำหรับการทำความเข้าใจอัลกอริทึม
    แต่อาจเกิด Stack Overflow กับปัญหาที่ลึกมาก
    """
    # กรณีเริ่มต้น
    if node is None:
        node = Node(
            state=problem.initial_state(),
            parent=None,
            action=None,
            path_cost=0,
            depth=0
        )
        explored = set()
    
    # Base cases
    if problem.goal_test(node.state):
        return node
    
    if node.depth >= max_depth:
        return None
    
    # เพิ่มสถานะปัจจุบันเข้า explored
    explored.add(node.state.data)
    
    # Recursive case: ลองทุกการกระทำ
    for action in problem.actions(node.state):
        child_state = problem.result(node.state, action)
        
        if child_state.data not in explored:
            child_node = Node(
                state=child_state,
                parent=node,
                action=action,
                path_cost=node.path_cost + 1,
                depth=node.depth + 1
            )
            
            # เรียกซ้ำ
            result = depth_first_search_recursive(
                problem, child_node, explored, max_depth
            )
            
            if result is not None:
                return result
    
    return None

3.4 การค้นหาตามต้นทุน (Uniform Cost Search - UCS)

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

Uniform Cost Search (UCS) ขยายโหนดที่มี ต้นทุนเส้นทางต่ำที่สุด ก่อน ใช้ Priority Queue โดยจัดลำดับตาม g(n) ซึ่งคือต้นทุนจากโหนดเริ่มต้นถึงโหนด n

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

g (n) = \sum_{i = 0}^{k - 1} c (s_{i}, a_{i}, s_{i + 1})

โดยที่:

g(n) = ต้นทุนสะสมจากสถานะเริ่มต้นถึงโหนด n
c(sᵢ, aᵢ, sᵢ₊₁) = ต้นทุนของการกระทำ aᵢ ที่เปลี่ยนจากสถานะ sᵢ ไปเป็น sᵢ₊₁
k = จำนวนขั้นตอนในเส้นทาง

graph TD
    subgraph ucs_example["UCS: ขยายตามต้นทุนต่ำสุด"]
        style ucs_example fill:#282828,stroke:#a89984,color:#ebdbb2
        
        A["A
g=0
ขยายที่ 1"]
        B["B
g=1
ขยายที่ 2"]
        C["C
g=5
ขยายที่ 5"]
        D["D
g=3
ขยายที่ 3"]
        E["E
g=4
ขยายที่ 4"]
        G["G ⭐
g=6
Goal!"]
        
        A -->|"cost=1"| B
        A -->|"cost=5"| C
        B -->|"cost=2"| D
        B -->|"cost=3"| E
        D -->|"cost=3"| G
        C -->|"cost=2"| G
    end
    
    style A fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style B fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style C fill:#b16286,stroke:#d3869b,color:#ebdbb2
    style D fill:#458588,stroke:#83a598,color:#ebdbb2
    style E fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
    style G fill:#98971a,stroke:#b8bb26,color:#ebdbb2

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

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

3.4.3 การ Implement UCS

"""
โมดูล Uniform Cost Search (UCS)
การค้นหาตามต้นทุนต่ำสุดสำหรับปัญหาการค้นหาทั่วไป
"""

import heapq
from typing import Optional


class PriorityQueue:
    """
    Priority Queue สำหรับการค้นหา
    รองรับการอัปเดตลำดับความสำคัญของโหนด
    """
    
    def __init__(self):
        self._queue = []  # heap
        self._entry_finder = {}  # state -> entry
        self._counter = 0  # unique sequence count
        self._REMOVED = '<removed>'
    
    def push(self, node: Node, priority: float):
        """เพิ่มโหนดหรืออัปเดตลำดับความสำคัญ"""
        if node.state.data in self._entry_finder:
            self._remove(node)
        
        entry = [priority, self._counter, node]
        self._entry_finder[node.state.data] = entry
        heapq.heappush(self._queue, entry)
        self._counter += 1
    
    def _remove(self, node: Node):
        """ทำเครื่องหมายว่าโหนดถูกลบ"""
        entry = self._entry_finder.pop(node.state.data)
        entry[-1] = self._REMOVED
    
    def pop(self) -> Optional[Node]:
        """ดึงโหนดที่มี priority ต่ำสุดออก"""
        while self._queue:
            priority, count, node = heapq.heappop(self._queue)
            if node is not self._REMOVED:
                del self._entry_finder[node.state.data]
                return node
        return None
    
    def __contains__(self, state_data):
        return state_data in self._entry_finder
    
    def __len__(self):
        return len(self._entry_finder)
    
    def get_priority(self, state_data) -> Optional[float]:
        """คืนค่า priority ของสถานะ"""
        if state_data in self._entry_finder:
            return self._entry_finder[state_data][0]
        return None


def uniform_cost_search(problem) -> Optional[Node]:
    """
    อัลกอริทึม Uniform Cost Search
    
    ค้นหาเส้นทางที่มีต้นทุนต่ำที่สุดจากสถานะเริ่มต้นไปยังเป้าหมาย
    ใช้ Priority Queue จัดลำดับตาม g(n)
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    ความแตกต่างจาก BFS:
    - BFS ใช้ Queue (FIFO) - เหมาะเมื่อต้นทุนเท่ากันหมด
    - UCS ใช้ Priority Queue - เหมาะเมื่อต้นทุนไม่เท่ากัน
    """
    # สร้างโหนดเริ่มต้น
    initial_node = Node(
        state=problem.initial_state(),
        parent=None,
        action=None,
        path_cost=0,
        depth=0
    )
    
    # สร้าง Priority Queue
    frontier = PriorityQueue()
    frontier.push(initial_node, initial_node.path_cost)
    
    # Explored set
    explored = set()
    
    nodes_expanded = 0
    
    while len(frontier) > 0:
        # ดึงโหนดที่มีต้นทุนต่ำสุด
        node = frontier.pop()
        
        if node is None:
            break
        
        # ตรวจสอบเป้าหมาย (ตรวจสอบตอน pop ไม่ใช่ตอน expand)
        if problem.goal_test(node.state):
            print(f"UCS: พบคำตอบ! ขยายโหนด {nodes_expanded} โหนด")
            print(f"ต้นทุนรวม: {node.path_cost}")
            return node
        
        # เพิ่มเข้า explored
        explored.add(node.state.data)
        nodes_expanded += 1
        
        # ขยายโหนด
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            child_cost = problem.path_cost(
                node.path_cost, node.state, action, child_state
            )
            
            child_node = Node(
                state=child_state,
                parent=node,
                action=action,
                path_cost=child_cost,
                depth=node.depth + 1
            )
            
            # ตรวจสอบและเพิ่มเข้า frontier
            if child_state.data not in explored:
                current_priority = frontier.get_priority(child_state.data)
                
                if current_priority is None:
                    # ยังไม่อยู่ใน frontier
                    frontier.push(child_node, child_cost)
                elif child_cost < current_priority:
                    # พบเส้นทางที่ดีกว่า - อัปเดต
                    frontier.push(child_node, child_cost)
    
    print(f"UCS: ไม่พบคำตอบ ขยายโหนด {nodes_expanded} โหนด")
    return None

3.5 การค้นหาจำกัดความลึก (Depth-Limited Search - DLS)

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

Depth-Limited Search (DLS) เป็น DFS ที่จำกัดความลึกสูงสุดไว้ที่ค่า l (limit) เพื่อป้องกันการค้นหาลงลึกไม่สิ้นสุด

"""
โมดูล Depth-Limited Search (DLS)
การค้นหาตามลึกแบบจำกัดความลึก
"""

from enum import Enum


class SearchResult(Enum):
    """ผลลัพธ์ของการค้นหา"""
    SUCCESS = "success"
    FAILURE = "failure"
    CUTOFF = "cutoff"  # ถึงขอบเขตความลึกแต่ยังไม่พบคำตอบ


def depth_limited_search(problem, limit: int) -> Tuple:
    """
    อัลกอริทึม Depth-Limited Search
    
    DFS ที่จำกัดความลึกไว้ที่ limit
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        limit: ความลึกสูงสุดที่อนุญาต
    
    Returns:
        Tuple ของ (SearchResult, Node หรือ None)
    """
    
    def recursive_dls(node: Node, limit: int) -> Tuple:
        """ฟังก์ชัน recursive สำหรับ DLS"""
        
        # ตรวจสอบเป้าหมาย
        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):
            child_state = problem.result(node.state, action)
            child_node = Node(
                state=child_state,
                parent=node,
                action=action,
                path_cost=node.path_cost + 1,
                depth=node.depth + 1
            )
            
            result, found_node = recursive_dls(child_node, limit - 1)
            
            if result == SearchResult.CUTOFF:
                cutoff_occurred = True
            elif result == SearchResult.SUCCESS:
                return (SearchResult.SUCCESS, found_node)
        
        if cutoff_occurred:
            return (SearchResult.CUTOFF, None)
        
        return (SearchResult.FAILURE, None)
    
    # เริ่มค้นหา
    initial_node = Node(
        state=problem.initial_state(),
        parent=None,
        action=None,
        path_cost=0,
        depth=0
    )
    
    return recursive_dls(initial_node, limit)

3.6 การค้นหาแบบลึกขึ้นเรื่อยๆ (Iterative Deepening Search - IDS)

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

Iterative Deepening Search (IDS) รวมข้อดีของ BFS (Completeness, Optimality) และ DFS (Space Efficiency) โดยทำ DLS ซ้ำหลายรอบ เพิ่มขีดจำกัดความลึกทีละหนึ่ง

graph TD
    subgraph ids_process["IDS: กระบวนการค้นหา"]
        style ids_process fill:#282828,stroke:#a89984,color:#ebdbb2
        
        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"]
            C1["C"]
            A1 --> B1
            A1 --> C1
        end
        
        subgraph iter2["Iteration 2: limit=2"]
            style iter2 fill:#98971a,stroke:#b8bb26,color:#ebdbb2
            A2["A"]
            B2["B"]
            C2["C"]
            D2["D"]
            E2["E"]
            F2["F"]
            G2["G ⭐"]
            A2 --> B2
            A2 --> C2
            B2 --> D2
            B2 --> E2
            C2 --> F2
            C2 --> G2
        end
    end
    
    iter0 -.->|"cutoff"| iter1
    iter1 -.->|"cutoff"| iter2
    
    style A0 fill:#458588,stroke:#83a598,color:#ebdbb2
    style A1 fill:#458588,stroke:#83a598,color:#ebdbb2
    style B1 fill:#458588,stroke:#83a598,color:#ebdbb2
    style C1 fill:#458588,stroke:#83a598,color:#ebdbb2
    style A2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style B2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style C2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style D2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style E2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style F2 fill:#458588,stroke:#83a598,color:#ebdbb2
    style G2 fill:#fabd2f,stroke:#d79921,color:#282828

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

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

การวิเคราะห์ความซับซ้อน:

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

N (I D S) = (d) b + (d - 1) b^{2} + \dots + (1) b^{d} = O (b^{d})

โดยที่:

b = branching factor
d = ความลึกของคำตอบ

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

Overhead = \frac{N (I D S)}{N (B F S)} = \frac{b}{b - 1}

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

3.6.3 การ Implement IDS

"""
โมดูล Iterative Deepening Search (IDS)
การค้นหาแบบลึกขึ้นเรื่อยๆ - รวมข้อดีของ BFS และ DFS
"""


def iterative_deepening_search(problem, max_limit: int = 100) -> Optional[Node]:
    """
    อัลกอริทึม Iterative Deepening Search
    
    ทำ DLS ซ้ำหลายรอบ โดยเพิ่ม limit ทีละหนึ่ง
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        max_limit: ความลึกสูงสุดที่จะลอง
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    ข้อดี:
    - Complete และ Optimal เหมือน BFS
    - Space Complexity O(bd) เหมือน DFS
    
    ข้อเสีย:
    - มีการขยายโหนดซ้ำ (แต่ overhead น้อย)
    """
    total_nodes = 0
    
    for depth_limit in range(max_limit + 1):
        print(f"  IDS: กำลังค้นหาที่ความลึก {depth_limit}...", end=" ")
        
        result, node = depth_limited_search(problem, depth_limit)
        
        if result == SearchResult.SUCCESS:
            print(f"พบคำตอบ!")
            return node
        elif result == SearchResult.FAILURE:
            print("FAILURE - ไม่มีคำตอบ")
            return None
        else:  # CUTOFF
            print("CUTOFF - เพิ่มความลึก")
    
    print(f"IDS: เกินขอบเขตความลึกสูงสุด ({max_limit})")
    return None


# ==================== ตัวอย่างการใช้งานและเปรียบเทียบ ====================

def compare_uninformed_searches(problem):
    """
    เปรียบเทียบประสิทธิภาพของอัลกอริทึมการค้นหาแบบไม่มีข้อมูลนำทาง
    """
    import time
    
    algorithms = [
        ("BFS", breadth_first_search),
        ("DFS", depth_first_search),
        ("UCS", uniform_cost_search),
        ("IDS", iterative_deepening_search)
    ]
    
    print("\n" + "=" * 60)
    print("เปรียบเทียบอัลกอริทึม Uninformed Search")
    print("=" * 60)
    
    results = []
    
    for name, algorithm in algorithms:
        print(f"\n--- {name} ---")
        start_time = time.time()
        result = algorithm(problem)
        elapsed = time.time() - start_time
        
        if result:
            path = get_solution_path(result)
            results.append({
                'name': name,
                'found': True,
                'depth': result.depth,
                'cost': result.path_cost,
                'time': elapsed
            })
        else:
            results.append({
                'name': name,
                'found': False,
                'time': elapsed
            })
    
    # สรุปผล
    print("\n" + "=" * 60)
    print("สรุปผลการเปรียบเทียบ")
    print("=" * 60)
    print(f"{'Algorithm':<10} {'Found':<8} {'Depth':<8} {'Cost':<8} {'Time (s)':<10}")
    print("-" * 44)
    
    for r in results:
        if r['found']:
            print(f"{r['name']:<10} {'Yes':<8} {r['depth']:<8} {r['cost']:<8.1f} {r['time']:<10.4f}")
        else:
            print(f"{r['name']:<10} {'No':<8} {'-':<8} {'-':<8} {r['time']:<10.4f}")

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

อัลกอริทึม	Complete	Optimal	Time	Space	โครงสร้างข้อมูล
BFS	✅ Yes (ถ้า b จำกัด)	✅ Yes*	O(b^d)	O(b^d)	Queue (FIFO)
DFS	❌ No	❌ No	O(b^m)	O(bm)	Stack (LIFO)
UCS	✅ Yes (ถ้า cost > 0)	✅ Yes	O(b^(1+⌊C*/ε⌋))	O(b^(1+⌊C*/ε⌋))	Priority Queue
DLS	❌ No	❌ No	O(b^l)	O(bl)	Stack (LIFO)
IDS	✅ Yes	✅ Yes*	O(b^d)	O(bd)	Stack (LIFO)

หมายเหตุ: *Optimal เมื่อต้นทุนทุกขั้นตอนเท่ากัน

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

4.1 แนวคิดของฮิวริสติก (Heuristic Concept)

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

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

h (n) = ค่าประมาณของต้นทุนจาก n ไปยังเป้าหมาย

โดยที่:

h(n) ≥ 0 เสมอ
h(goal) = 0 (ที่เป้าหมาย ค่าประมาณเป็น 0)

graph TD
    subgraph heuristic_concept["แนวคิด Heuristic"]
        style heuristic_concept fill:#282828,stroke:#a89984,color:#ebdbb2
        
        START["สถานะเริ่มต้น
Start"]
        N1["Node n₁
h(n₁) = 8"]
        N2["Node n₂
h(n₂) = 5"]
        N3["Node n₃
h(n₃) = 3"]
        GOAL["เป้าหมาย
h(goal) = 0"]
        
        START --> N1
        START --> N2
        N1 --> N3
        N2 --> N3
        N3 --> GOAL
        
        N2 -.->|"Heuristic นำทาง"| GOAL
    end
    
    style START fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style N1 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style N2 fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style N3 fill:#458588,stroke:#83a598,color:#ebdbb2
    style GOAL fill:#689d6a,stroke:#8ec07c,color:#ebdbb2

4.2 ฟังก์ชันประเมิน (Evaluation Functions)

graph LR
    subgraph eval_functions["ฟังก์ชันประเมิน"]
        style eval_functions fill:#282828,stroke:#a89984,color:#ebdbb2
        
        GN["g(n)
ต้นทุนจริง
จาก Start ถึง n"]
        HN["h(n)
ค่าประมาณ
จาก n ถึง Goal"]
        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

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

Greedy Best-First Search เลือกขยายโหนดที่มี h(n) ต่ำที่สุด เสมอ โดยไม่พิจารณาต้นทุนที่ผ่านมา (g(n))

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

f (n) = h (n)

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

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

4.3.3 การ Implement Greedy Best-First Search

"""
โมดูล Greedy Best-First Search
การค้นหาแบบโลภโดยใช้ฮิวริสติก
"""

from typing import Callable


def greedy_best_first_search(problem, 
                              heuristic: Callable) -> Optional[Node]:
    """
    อัลกอริทึม Greedy Best-First Search
    
    ขยายโหนดที่มี h(n) ต่ำที่สุดก่อนเสมอ
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        heuristic: ฟังก์ชัน h(state) -> float
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    ข้อดี:
    - เร็วเมื่อ heuristic ดี
    
    ข้อเสีย:
    - ไม่ Complete, ไม่ Optimal
    - อาจเลือกเส้นทางที่ดูดีแต่จริงๆ แย่
    """
    # สร้างโหนดเริ่มต้น
    initial_node = Node(
        state=problem.initial_state(),
        parent=None,
        action=None,
        path_cost=0,
        depth=0
    )
    
    # Priority Queue จัดลำดับตาม h(n)
    frontier = PriorityQueue()
    h_initial = heuristic(initial_node.state)
    frontier.push(initial_node, h_initial)
    
    explored = set()
    nodes_expanded = 0
    
    while len(frontier) > 0:
        node = frontier.pop()
        
        if node is None:
            break
        
        # ตรวจสอบเป้าหมาย
        if problem.goal_test(node.state):
            print(f"Greedy: พบคำตอบ! ขยายโหนด {nodes_expanded} โหนด")
            return node
        
        explored.add(node.state.data)
        nodes_expanded += 1
        
        # ขยายโหนด
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            
            if child_state.data not in explored:
                child_node = Node(
                    state=child_state,
                    parent=node,
                    action=action,
                    path_cost=node.path_cost + 1,
                    depth=node.depth + 1
                )
                
                # ใช้เฉพาะ h(n) เป็นลำดับความสำคัญ
                h_value = heuristic(child_state)
                frontier.push(child_node, h_value)
    
    print(f"Greedy: ไม่พบคำตอบ ขยายโหนด {nodes_expanded} โหนด")
    return None

4.4 อัลกอริทึม A* Search

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

A Search* เป็นอัลกอริทึมการค้นหาที่ดีที่สุดและนิยมใช้มากที่สุด รวมข้อดีของ UCS (ใช้ g(n)) และ Greedy (ใช้ h(n)) เข้าด้วยกัน

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

f (n) = g (n) + h (n)

โดยที่:

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

graph TD
    subgraph astar_example["A* Search: การทำงาน"]
        style astar_example 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 ✓"]
        C["C
g=2, h=5
f=7"]
        D["D
g=5, h=2
f=7"]
        G["G ⭐
g=6, h=0
f=6"]
        
        S -->|"cost=1"| A
        S -->|"cost=4"| B
        A -->|"cost=1"| C
        A -->|"cost=4"| D
        B -->|"cost=2"| G
        C -->|"cost=3"| G
    end
    
    style S fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style A fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style B fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style C fill:#458588,stroke:#83a598,color:#ebdbb2
    style D fill:#b16286,stroke:#d3869b,color:#ebdbb2
    style G fill:#689d6a,stroke:#8ec07c,color:#ebdbb2

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

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

0 \leq h (n) \leq h^{*} (n)

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

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

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

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

4.4.4 การ Implement A* Search

"""
โมดูล A* Search Algorithm
อัลกอริทึมการค้นหาที่ดีที่สุดสำหรับการหาเส้นทางที่ Optimal
"""


def astar_search(problem, heuristic: Callable) -> Optional[Node]:
    """
    อัลกอริทึม A* Search
    
    ค้นหาเส้นทางที่มีต้นทุนต่ำที่สุดโดยใช้ f(n) = g(n) + h(n)
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        heuristic: ฟังก์ชัน h(state) -> float ที่เป็น admissible
    
    Returns:
        Node ที่เป็นเป้าหมาย หรือ None ถ้าไม่พบคำตอบ
    
    การทำงาน:
    1. ใช้ Priority Queue จัดลำดับตาม f(n) = g(n) + h(n)
    2. ขยายโหนดที่มี f(n) ต่ำที่สุดก่อน
    3. ถ้า h(n) เป็น admissible รับประกันหาคำตอบที่ optimal
    
    Optimality Proof:
    - ถ้า h(n) ≤ h*(n) สำหรับทุก n
    - A* จะขยายโหนดที่มี f(n) ≤ f* (f* = ต้นทุนที่ดีที่สุด)
    - ดังนั้นเมื่อขยายถึง goal จะได้คำตอบที่ดีที่สุด
    """
    # สร้างโหนดเริ่มต้น
    initial_state = problem.initial_state()
    initial_node = Node(
        state=initial_state,
        parent=None,
        action=None,
        path_cost=0,  # g(n) = 0
        depth=0
    )
    
    # คำนวณ f(n) เริ่มต้น
    h_initial = heuristic(initial_state)
    f_initial = initial_node.path_cost + h_initial  # f(n) = g(n) + h(n)
    
    # Priority Queue จัดลำดับตาม f(n)
    frontier = PriorityQueue()
    frontier.push(initial_node, f_initial)
    
    # เก็บ g-values ที่ดีที่สุดสำหรับแต่ละสถานะ
    g_values = {initial_state.data: 0}
    
    # Explored set
    explored = set()
    
    nodes_expanded = 0
    
    while len(frontier) > 0:
        # ดึงโหนดที่มี f(n) ต่ำที่สุด
        node = frontier.pop()
        
        if node is None:
            break
        
        # ตรวจสอบเป้าหมาย
        if problem.goal_test(node.state):
            print(f"A*: พบคำตอบที่ optimal!")
            print(f"  - โหนดที่ขยาย: {nodes_expanded}")
            print(f"  - ต้นทุนรวม: {node.path_cost}")
            print(f"  - ความลึก: {node.depth}")
            return node
        
        # ข้ามถ้าเจอเส้นทางที่ดีกว่าแล้ว
        if node.state.data in explored:
            continue
        
        explored.add(node.state.data)
        nodes_expanded += 1
        
        # ขยายโหนด
        for action in problem.actions(node.state):
            child_state = problem.result(node.state, action)
            
            # คำนวณ g(n') = g(n) + step_cost
            child_g = problem.path_cost(
                node.path_cost, node.state, action, child_state
            )
            
            # ตรวจสอบว่าเป็นเส้นทางที่ดีกว่าหรือไม่
            if child_state.data not in explored:
                old_g = g_values.get(child_state.data, float('inf'))
                
                if child_g < old_g:
                    # พบเส้นทางที่ดีกว่า
                    g_values[child_state.data] = child_g
                    
                    child_node = Node(
                        state=child_state,
                        parent=node,
                        action=action,
                        path_cost=child_g,
                        depth=node.depth + 1
                    )
                    
                    # คำนวณ f(n') = g(n') + h(n')
                    h_value = heuristic(child_state)
                    f_value = child_g + h_value
                    
                    frontier.push(child_node, f_value)
    
    print(f"A*: ไม่พบคำตอบ ขยายโหนด {nodes_expanded} โหนด")
    return None

4.5 ฟังก์ชันฮิวริสติก (Heuristic Functions)

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

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

h (n) \leq h^{*} (n) สำหรับทุก n

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

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

h (n) \leq c (n, a, n^{'}) + h (n^{'})

เป็นไปตาม Triangle Inequality
Consistent ⟹ Admissible (แต่กลับกันไม่จริง)
ทำให้ A* มีประสิทธิภาพมากขึ้น

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

"""
โมดูลฟังก์ชันฮิวริสติกสำหรับ 8-Puzzle
"""


def misplaced_tiles(state) -> int:
    """
    ฮิวริสติก h₁: จำนวนช่องที่อยู่ผิดตำแหน่ง (Misplaced Tiles)
    
    นับจำนวนตัวเลขที่ไม่อยู่ในตำแหน่งที่ถูกต้อง (ไม่นับช่องว่าง)
    
    Args:
        state: สถานะของ 8-Puzzle
    
    Returns:
        จำนวนช่องที่อยู่ผิดตำแหน่ง
    
    ตัวอย่าง:
        State: (1, 2, 3, 4, 0, 5, 7, 8, 6)
        Goal:  (1, 2, 3, 4, 5, 6, 7, 8, 0)
        Misplaced: 5, 7, 8, 6, 0 → h₁ = 4 (ไม่นับ 0)
    
    คุณสมบัติ:
        - Admissible: ใช่ (ต้องเคลื่อนที่อย่างน้อย 1 ครั้งต่อช่องที่ผิด)
        - Consistent: ใช่
    """
    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


def manhattan_distance(state) -> int:
    """
    ฮิวริสติก h₂: ระยะทางแมนฮัตตัน (Manhattan Distance)
    
    ผลรวมของระยะทางแนวนอนและแนวตั้งที่แต่ละช่อง
    ต้องเคลื่อนที่ไปยังตำแหน่งที่ถูกต้อง
    
    Args:
        state: สถานะของ 8-Puzzle
    
    Returns:
        ผลรวมระยะทางแมนฮัตตัน
    
    สูตร:
        h₂(n) = Σ |xᵢ - xᵢ*| + |yᵢ - yᵢ*|
        
        โดยที่ (xᵢ, yᵢ) คือตำแหน่งปัจจุบันของช่อง i
        และ (xᵢ*, yᵢ*) คือตำแหน่งเป้าหมายของช่อง i
    
    ตัวอย่าง:
        ตำแหน่งช่อง 7 ใน state: row=2, col=0
        ตำแหน่งเป้าหมายของ 7:    row=2, col=1
        ระยะทาง = |2-2| + |0-1| = 1
    
    คุณสมบัติ:
        - Admissible: ใช่ (แต่ละช่องต้องเคลื่อนที่อย่างน้อยเท่านี้)
        - Consistent: ใช่
        - h₂ ≥ h₁ เสมอ (ดีกว่า misplaced tiles)
    """
    # ตำแหน่งเป้าหมายของแต่ละตัวเลข (index -> (row, col))
    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_distance = 0
    
    for i in range(9):
        tile = state.data[i]
        
        if tile != 0:  # ไม่นับช่องว่าง
            # ตำแหน่งปัจจุบัน
            current_row, current_col = i // 3, i % 3
            
            # ตำแหน่งเป้าหมาย
            goal_row, goal_col = goal_positions[tile]
            
            # ระยะทางแมนฮัตตัน
            distance = abs(current_row - goal_row) + abs(current_col - goal_col)
            total_distance += distance
    
    return total_distance


def linear_conflict(state) -> int:
    """
    ฮิวริสติก h₃: Manhattan Distance + Linear Conflict
    
    ปรับปรุง Manhattan Distance โดยบวก penalty เมื่อมี linear conflict
    
    Linear Conflict เกิดขึ้นเมื่อ:
    - ช่อง 2 ช่องอยู่ในแถว/คอลัมน์เป้าหมายเดียวกัน
    - แต่สลับลำดับกัน (ต้องเอาช่องหนึ่งออกไปก่อน)
    
    ตัวอย่าง: แถว [3, 1, 2] เป้าหมาย [1, 2, 3]
    - 3 และ 1 conflict (3 อยู่ซ้าย 1 แต่ควรอยู่ขวา)
    - 3 และ 2 conflict
    - ต้องบวก 2*2 = 4 เข้ากับ Manhattan
    
    คุณสมบัติ:
        - Admissible: ใช่
        - Consistent: ใช่
        - h₃ ≥ h₂ ≥ h₁
    """
    md = manhattan_distance(state)
    conflict = 0
    
    # Goal positions for reference
    goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
    
    # ตรวจสอบแต่ละแถว
    for row in range(3):
        tiles_in_row = []
        for col in range(3):
            idx = row * 3 + col
            tile = state.data[idx]
            
            # ตรวจสอบว่าช่องนี้อยู่ในแถวเป้าหมายที่ถูกต้องหรือไม่
            if tile != 0 and (tile - 1) // 3 == row:
                tiles_in_row.append((tile, col))
        
        # นับ conflicts ในแถว
        for i in range(len(tiles_in_row)):
            for j in range(i + 1, len(tiles_in_row)):
                t1, c1 = tiles_in_row[i]
                t2, c2 = tiles_in_row[j]
                
                # goal column ของ t1 และ t2
                goal_c1 = (t1 - 1) % 3
                goal_c2 = (t2 - 1) % 3
                
                # conflict ถ้าลำดับสลับกัน
                if (c1 < c2 and goal_c1 > goal_c2) or \
                   (c1 > c2 and goal_c1 < goal_c2):
                    conflict += 2
    
    # ตรวจสอบแต่ละคอลัมน์ (คล้ายกัน)
    for col in range(3):
        tiles_in_col = []
        for row in range(3):
            idx = row * 3 + col
            tile = state.data[idx]
            
            if tile != 0 and (tile - 1) % 3 == col:
                tiles_in_col.append((tile, row))
        
        for i in range(len(tiles_in_col)):
            for j in range(i + 1, len(tiles_in_col)):
                t1, r1 = tiles_in_col[i]
                t2, r2 = tiles_in_col[j]
                
                goal_r1 = (t1 - 1) // 3
                goal_r2 = (t2 - 1) // 3
                
                if (r1 < r2 and goal_r1 > goal_r2) or \
                   (r1 > r2 and goal_r1 < goal_r2):
                    conflict += 2
    
    return md + conflict


# ==================== ฮิวริสติกสำหรับปัญหาแผนที่ ====================

def euclidean_distance(current: tuple, goal: tuple) -> float:
    """
    ฮิวริสติก: ระยะทางยูคลิด (Euclidean Distance)
    
    ระยะทางเส้นตรงระหว่างจุดสองจุดในระนาบ 2 มิติ
    
    Args:
        current: พิกัด (x, y) ปัจจุบัน
        goal: พิกัด (x, y) เป้าหมาย
    
    Returns:
        ระยะทางยูคลิด
    
    สูตร:
        h(n) = √[(x₂-x₁)² + (y₂-y₁)²]
    
    คุณสมบัติ:
        - Admissible: ใช่ (เส้นตรงสั้นที่สุดเสมอ)
        - เหมาะสำหรับเคลื่อนที่ได้ทุกทิศทาง
    """
    import math
    x1, y1 = current
    x2, y2 = goal
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)


def manhattan_distance_grid(current: tuple, goal: tuple) -> int:
    """
    ฮิวริสติก: ระยะทางแมนฮัตตัน สำหรับ Grid Map
    
    ผลรวมของระยะทางแนวนอนและแนวตั้ง
    
    Args:
        current: พิกัด (x, y) ปัจจุบัน
        goal: พิกัด (x, y) เป้าหมาย
    
    Returns:
        ระยะทางแมนฮัตตัน
    
    สูตร:
        h(n) = |x₂-x₁| + |y₂-y₁|
    
    คุณสมบัติ:
        - Admissible: ใช่ (สำหรับ 4-directional movement)
        - เหมาะสำหรับเคลื่อนที่แบบ 4 ทิศ (ขึ้น/ลง/ซ้าย/ขวา)
    """
    x1, y1 = current
    x2, y2 = goal
    return abs(x2 - x1) + abs(y2 - y1)


def chebyshev_distance(current: tuple, goal: tuple) -> int:
    """
    ฮิวริสติก: ระยะทางเชบีเชฟ (Chebyshev Distance)
    
    ค่าสูงสุดของระยะทางแนวนอนและแนวตั้ง
    เหมาะสำหรับการเคลื่อนที่ 8 ทิศทาง (รวมทแยง)
    
    สูตร:
        h(n) = max(|x₂-x₁|, |y₂-y₁|)
    """
    x1, y1 = current
    x2, y2 = goal
    return max(abs(x2 - x1), abs(y2 - y1))

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

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

หลักการ Dominance:

ถ้า h_{2} (n) \geq h_{1} (n) สำหรับทุก n, แล้ว h_{2} dominate h_{1}

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

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

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

Local Search เป็นอัลกอริทึมที่:

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

ข้อดี:

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

ข้อเสีย:

ไม่รับประกันว่าจะพบคำตอบที่ดีที่สุดทั่วไป (Global Optimum)
อาจติดอยู่ที่ Local Optimum

graph TD
    subgraph landscape["Search Landscape"]
        style landscape fill:#282828,stroke:#a89984,color:#ebdbb2
        
        LO1["Local Maximum
จุดสูงสุดเฉพาะที่"]
        GO["Global Maximum
จุดสูงสุดรวม ⭐"]
        LO2["Local Maximum
จุดสูงสุดเฉพาะที่"]
        P["Plateau
ที่ราบสูง"]
        
        START["จุดเริ่มต้น"]
        
        START -.->|"Hill Climbing
อาจติดที่นี่"| LO1
        START -.->|"หลายจุดเริ่มต้น
อาจถึงที่นี่"| GO
    end
    
    style LO1 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style GO fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style LO2 fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style P fill:#458588,stroke:#83a598,color:#ebdbb2
    style START fill:#cc241d,stroke:#fb4934,color:#ebdbb2

5.2 อัลกอริทึม Hill Climbing

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

Hill Climbing เป็นอัลกอริทึมที่เลือกเคลื่อนที่ไปยังสถานะที่ดีกว่าเสมอ เหมือนการปีนเขาในหมอกที่มองเห็นแค่รอบตัว

"""
โมดูล Hill Climbing Algorithms
อัลกอริทึมการค้นหาแบบ Local Search
"""

import random
from typing import Callable, Optional, List


def hill_climbing(problem, 
                  evaluation: Callable,
                  maximize: bool = True) -> tuple:
    """
    อัลกอริทึม Hill Climbing พื้นฐาน (Steepest Ascent)
    
    เลือกเคลื่อนที่ไปยังเพื่อนบ้านที่ดีที่สุดเสมอ
    หยุดเมื่อไม่มีเพื่อนบ้านที่ดีกว่า
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        evaluation: ฟังก์ชันประเมินค่า (ยิ่งสูงยิ่งดีถ้า maximize=True)
        maximize: True = หาค่าสูงสุด, False = หาค่าต่ำสุด
    
    Returns:
        Tuple ของ (สถานะที่ดีที่สุด, ค่าประเมิน, จำนวนขั้นตอน)
    
    ข้อจำกัด:
    - อาจติด Local Maximum/Minimum
    - อาจติด Plateau (ที่ราบสูง)
    - อาจติด Ridge (สันเขาแคบ)
    """
    current = problem.initial_state()
    current_value = evaluation(current)
    steps = 0
    
    while True:
        steps += 1
        
        # หาเพื่อนบ้านทั้งหมด
        neighbors = []
        for action in problem.actions(current):
            neighbor = problem.result(current, action)
            neighbor_value = evaluation(neighbor)
            neighbors.append((neighbor, neighbor_value, action))
        
        if not neighbors:
            break
        
        # เลือกเพื่อนบ้านที่ดีที่สุด
        if maximize:
            best_neighbor, best_value, best_action = max(
                neighbors, key=lambda x: x[1]
            )
        else:
            best_neighbor, best_value, best_action = min(
                neighbors, key=lambda x: x[1]
            )
        
        # ตรวจสอบว่าดีกว่าปัจจุบันหรือไม่
        if (maximize and best_value <= current_value) or \
           (not maximize and best_value >= current_value):
            # ไม่มีเพื่อนบ้านที่ดีกว่า - หยุด
            break
        
        # เคลื่อนที่ไปยังเพื่อนบ้านที่ดีกว่า
        current = best_neighbor
        current_value = best_value
    
    return current, current_value, steps


def hill_climbing_first_choice(problem,
                                evaluation: Callable,
                                maximize: bool = True,
                                max_sideways: int = 100) -> tuple:
    """
    First-Choice Hill Climbing
    
    เลือกเพื่อนบ้านแรกที่ดีกว่าแทนการหาที่ดีที่สุด
    เร็วกว่าเมื่อมีเพื่อนบ้านจำนวนมาก
    """
    current = problem.initial_state()
    current_value = evaluation(current)
    steps = 0
    sideways = 0  # นับการเคลื่อนที่แบบ sideways
    
    while True:
        steps += 1
        
        # สุ่มลำดับเพื่อนบ้าน
        actions = problem.actions(current)
        random.shuffle(actions)
        
        moved = False
        
        for action in actions:
            neighbor = problem.result(current, action)
            neighbor_value = evaluation(neighbor)
            
            # ตรวจสอบว่าดีกว่าหรือเท่ากับ
            if maximize:
                is_better = neighbor_value > current_value
                is_equal = neighbor_value == current_value
            else:
                is_better = neighbor_value < current_value
                is_equal = neighbor_value == current_value
            
            if is_better:
                current = neighbor
                current_value = neighbor_value
                moved = True
                sideways = 0
                break
            elif is_equal and sideways < max_sideways:
                # Sideways move - ช่วยหลุดจาก plateau
                current = neighbor
                sideways += 1
                moved = True
                break
        
        if not moved:
            break
    
    return current, current_value, steps


def hill_climbing_random_restart(problem,
                                  evaluation: Callable,
                                  maximize: bool = True,
                                  num_restarts: int = 10,
                                  random_state_generator: Callable = None) -> tuple:
    """
    Random Restart Hill Climbing
    
    ทำ Hill Climbing หลายรอบจากจุดเริ่มต้นแบบสุ่ม
    ช่วยหลีกเลี่ยง Local Optimum
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        evaluation: ฟังก์ชันประเมินค่า
        maximize: True = หาค่าสูงสุด
        num_restarts: จำนวนรอบที่จะลอง
        random_state_generator: ฟังก์ชันสร้างสถานะสุ่ม
    
    Returns:
        Tuple ของ (สถานะที่ดีที่สุด, ค่าประเมิน, รอบที่พบ)
    
    ทฤษฎี:
    - ถ้า local maximum แต่ละจุดมีโอกาส p ที่จะถึง global
    - รอบที่คาดว่าจะพบ global = 1/p
    """
    best_state = None
    best_value = float('-inf') if maximize else float('inf')
    best_round = 0
    
    for i in range(num_restarts):
        # สร้างสถานะเริ่มต้นใหม่ (หรือใช้ default)
        if random_state_generator and i > 0:
            # ตั้งค่าสถานะเริ่มต้นใหม่
            problem._initial = random_state_generator()
        
        # ทำ Hill Climbing
        state, value, steps = hill_climbing(problem, evaluation, maximize)
        
        # ตรวจสอบว่าดีกว่าที่เคยพบหรือไม่
        if maximize:
            if value > best_value:
                best_state = state
                best_value = value
                best_round = i + 1
        else:
            if value < best_value:
                best_state = state
                best_value = value
                best_round = i + 1
    
    return best_state, best_value, best_round


def simulated_annealing(problem,
                        evaluation: Callable,
                        schedule: Callable,
                        maximize: bool = True,
                        max_iterations: int = 10000) -> tuple:
    """
    อัลกอริทึม Simulated Annealing
    
    ปรับปรุง Hill Climbing โดยยอมให้เคลื่อนที่ไปทางที่แย่กว่าได้บ้าง
    โดยความน่าจะเป็นขึ้นกับ "อุณหภูมิ" ที่ลดลงเรื่อยๆ
    
    Args:
        problem: อินสแตนซ์ของ SearchProblem
        evaluation: ฟังก์ชันประเมินค่า
        schedule: ฟังก์ชัน T(t) คืนค่าอุณหภูมิตามเวลา t
        maximize: True = หาค่าสูงสุด
        max_iterations: จำนวนรอบสูงสุด
    
    Returns:
        Tuple ของ (สถานะที่ดีที่สุด, ค่าประเมิน, จำนวนรอบ)
    
    ความน่าจะเป็นในการยอมรับการเคลื่อนที่ที่แย่กว่า:
        P(accept) = exp(ΔE / T)
        
        โดยที่:
        - ΔE = ความแตกต่างของค่าประเมิน (ติดลบ = แย่กว่า)
        - T = อุณหภูมิปัจจุบัน
    """
    import math
    
    current = problem.initial_state()
    current_value = evaluation(current)
    
    best = current
    best_value = current_value
    
    for t in range(max_iterations):
        # คำนวณอุณหภูมิ
        T = schedule(t)
        
        if T <= 0:
            break
        
        # เลือกเพื่อนบ้านแบบสุ่ม
        actions = problem.actions(current)
        if not actions:
            break
        
        action = random.choice(actions)
        neighbor = problem.result(current, action)
        neighbor_value = evaluation(neighbor)
        
        # คำนวณความแตกต่าง
        if maximize:
            delta = neighbor_value - current_value
        else:
            delta = current_value - neighbor_value
        
        # ตัดสินใจว่าจะเคลื่อนที่หรือไม่
        if delta > 0:
            # ดีกว่า - เคลื่อนที่เสมอ
            current = neighbor
            current_value = neighbor_value
        else:
            # แย่กว่า - เคลื่อนที่ด้วยความน่าจะเป็น
            probability = math.exp(delta / T)
            if random.random() < probability:
                current = neighbor
                current_value = neighbor_value
        
        # อัปเดตคำตอบที่ดีที่สุด
        if maximize:
            if current_value > best_value:
                best = current
                best_value = current_value
        else:
            if current_value < best_value:
                best = current
                best_value = current_value
    
    return best, best_value, t


def exponential_schedule(t: int, T0: float = 1000, alpha: float = 0.995) -> float:
    """
    ฟังก์ชัน Schedule แบบ Exponential Decay
    
    T(t) = T₀ × α^t
    
    Args:
        t: เวลา (จำนวนรอบ)
        T0: อุณหภูมิเริ่มต้น
        alpha: อัตราการลด (0 < α < 1)
    """
    return T0 * (alpha ** t)


def linear_schedule(t: int, T0: float = 1000, rate: float = 0.1) -> float:
    """
    ฟังก์ชัน Schedule แบบ Linear Decay
    
    T(t) = max(0, T₀ - rate × t)
    """
    return max(0, T0 - rate * t)

5.3 ตารางเปรียบเทียบ Local Search Algorithms

อัลกอริทึม	ข้อดี	ข้อเสีย	เหมาะกับ
Hill Climbing	เร็ว, เรียบง่าย	ติด Local Optimum	ปัญหาง่าย, landscape นุ่ม
First-Choice HC	เร็วกว่าเมื่อ neighbor มาก	ติด Local Optimum	เพื่อนบ้านจำนวนมาก
Random Restart	หลีกเลี่ยง Local Optimum ได้ดี	ช้ากว่า	ปัญหาที่มี Local Optimum หลายจุด
Simulated Annealing	หลีกเลี่ยง Local Optimum	ต้องปรับ 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)	h(n)
A*	✅	✅	O(b^d)	O(b^d)	g(n), h(n)
Hill Climbing	❌	❌	O(∞)	O(1)	evaluation

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

flowchart TD
    START["เริ่มต้น
เลือกอัลกอริทึม"]
    
    Q1{"ต้องการ
เส้นทางหรือไม่?"}
    Q2{"มีฟังก์ชัน
ฮิวริสติกหรือไม่?"}
    Q3{"ต้นทุนทุกขั้น
เท่ากันหรือไม่?"}
    Q4{"หน่วยความจำ
จำกัดหรือไม่?"}
    Q5{"ต้องการ
optimal หรือไม่?"}
    
    ASTAR["A* Search
✅ Complete
✅ Optimal"]
    GREEDY["Greedy Best-First
❌ Complete
❌ Optimal"]
    UCS["Uniform Cost
✅ Complete
✅ Optimal"]
    BFS["BFS
✅ Complete
✅ Optimal*"]
    IDS["Iterative Deepening
✅ Complete
✅ Optimal*"]
    SA["Simulated Annealing
หรือ Hill Climbing"]
    
    START --> Q1
    
    Q1 -->|"ใช่"| Q2
    Q1 -->|"ไม่
(Optimization)"| SA
    
    Q2 -->|"ใช่"| Q5
    Q2 -->|"ไม่"| Q3
    
    Q5 -->|"ใช่"| ASTAR
    Q5 -->|"ไม่"| GREEDY
    
    Q3 -->|"ใช่"| Q4
    Q3 -->|"ไม่"| UCS
    
    Q4 -->|"ใช่"| IDS
    Q4 -->|"ไม่"| BFS
    
    style START fill:#cc241d,stroke:#fb4934,color:#ebdbb2
    style ASTAR fill:#98971a,stroke:#b8bb26,color:#ebdbb2
    style GREEDY fill:#d65d0e,stroke:#fe8019,color:#ebdbb2
    style UCS fill:#458588,stroke:#83a598,color:#ebdbb2
    style BFS fill:#458588,stroke:#83a598,color:#ebdbb2
    style IDS fill:#689d6a,stroke:#8ec07c,color:#ebdbb2
    style SA fill:#b16286,stroke:#d3869b,color:#ebdbb2
    style Q1 fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style Q2 fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style Q3 fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style Q4 fill:#3c3836,stroke:#a89984,color:#ebdbb2
    style Q5 fill:#3c3836,stroke:#a89984,color:#ebdbb2

6.3 ตัวอย่างการประยุกต์ใช้งานจริง

"""
โมดูลตัวอย่างการประยุกต์ใช้อัลกอริทึมการค้นหา
"""


class GridPathfinding:
    """
    ปัญหาการหาเส้นทางบนตาราง 2 มิติ
    ใช้สำหรับเกม, หุ่นยนต์, GPS Navigation
    """
    
    def __init__(self, grid: List[List[int]], 
                 start: tuple, goal: tuple):
        """
        Args:
            grid: ตาราง 2 มิติ (0 = ว่าง, 1 = สิ่งกีดขวาง)
            start: ตำแหน่งเริ่มต้น (row, col)
            goal: ตำแหน่งเป้าหมาย (row, col)
        """
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0])
        self.start = start
        self.goal = goal
        
        # ทิศทางการเคลื่อนที่ 4 ทิศ
        self.directions = [
            (-1, 0, 'UP'),
            (1, 0, 'DOWN'),
            (0, -1, 'LEFT'),
            (0, 1, 'RIGHT')
        ]
    
    def initial_state(self):
        return State(data=self.start)
    
    def actions(self, state):
        row, col = state.data
        valid_actions = []
        
        for dr, dc, action in self.directions:
            new_row, new_col = row + dr, col + dc
            
            # ตรวจสอบขอบเขตและสิ่งกีดขวาง
            if (0 <= new_row < self.rows and 
                0 <= new_col < self.cols and
                self.grid[new_row][new_col] == 0):
                valid_actions.append(action)
        
        return valid_actions
    
    def result(self, state, action):
        row, col = state.data
        
        for dr, dc, act in self.directions:
            if act == action:
                return State(data=(row + dr, col + dc))
        
        return state
    
    def goal_test(self, state):
        return state.data == self.goal
    
    def path_cost(self, cost, state1, action, state2):
        return cost + 1
    
    def heuristic(self, state):
        """Manhattan Distance Heuristic"""
        row, col = state.data
        goal_row, goal_col = self.goal
        return abs(row - goal_row) + abs(col - goal_col)


def visualize_path(grid, path, start, goal):
    """
    แสดงผลเส้นทางบนตาราง
    """
    # สร้างสำเนาของ grid
    display = [row[:] for row in grid]
    
    # ทำเครื่องหมายเส้นทาง
    for state in path:
        row, col = state.data
        display[row][col] = 2  # 2 = เส้นทาง
    
    # ทำเครื่องหมาย start และ goal
    display[start[0]][start[1]] = 3  # 3 = start
    display[goal[0]][goal[1]] = 4    # 4 = goal
    
    # แสดงผล
    symbols = {0: '·', 1: '█', 2: '○', 3: 'S', 4: 'G'}
    
    print("\nแผนที่และเส้นทาง:")
    for row in display:
        print(' '.join(symbols[cell] for cell in row))


# ==================== ตัวอย่างการใช้งาน ====================

if __name__ == "__main__":
    # สร้างแผนที่ (0 = ว่าง, 1 = กำแพง)
    grid = [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 1, 1, 0],
        [0, 0, 1, 0, 0, 1, 0, 0],
        [0, 0, 1, 1, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
    ]
    
    start = (0, 0)
    goal = (6, 7)
    
    problem = GridPathfinding(grid, start, goal)
    
    print("=" * 50)
    print("การหาเส้นทางบนตาราง (Grid Pathfinding)")
    print("=" * 50)
    
    # ค้นหาด้วย A*
    print("\n--- ค้นหาด้วย A* ---")
    result = astar_search(problem, problem.heuristic)
    
    if result:
        path = []
        node = result
        while node:
            path.append(node.state)
            node = node.parent
        path.reverse()
        
        visualize_path(grid, path, start, goal)
        print(f"\nความยาวเส้นทาง: {len(path) - 1} ขั้นตอน")

7. สรุป

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

การกำหนดปัญหา (Problem Formulation) เป็นขั้นตอนแรกและสำคัญที่สุด ต้องระบุ State Space, Actions, Transition Model, Goal Test, และ Path Cost ให้ชัดเจน
Uninformed Search ไม่ต้องการความรู้เพิ่มเติม แต่มีประสิทธิภาพจำกัด:
- BFS หาคำตอบที่ตื้นที่สุด แต่ใช้หน่วยความจำมาก
- DFS ใช้หน่วยความจำน้อย แต่ไม่ Complete และไม่ Optimal
- IDS รวมข้อดีของทั้งคู่ เหมาะสำหรับ unknown depth
Informed Search ใช้ Heuristic นำทาง มีประสิทธิภาพสูงกว่า:
- A* เป็นอัลกอริทึมที่ดีที่สุดเมื่อมี Admissible Heuristic
- คุณภาพของ Heuristic ส่งผลโดยตรงต่อประสิทธิภาพ
Local Search เหมาะสำหรับปัญหา Optimization ที่ไม่ต้องการเส้นทาง:
- ใช้หน่วยความจำน้อยมาก
- Simulated Annealing ช่วยหลีกเลี่ยง Local Optimum
การเลือกอัลกอริทึม ขึ้นอยู่กับ:
- ต้องการ Optimal หรือไม่?
- มี Heuristic หรือไม่?
- หน่วยความจำจำกัดหรือไม่?
- ปริภูมิสถานะมีขนาดใหญ่แค่ไหน?

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

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

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

หนังสือหลัก

Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach (4th Edition). Pearson. - บทที่ 3-4 ครอบคลุมเนื้อหาการค้นหาอย่างละเอียด
Poole, D., & Mackworth, A. (2023). Artificial Intelligence: Foundations of Computational Agents (3rd Edition). Cambridge University Press. - เน้นการประยุกต์ใช้จริง

บทความวิจัยสำคัญ

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. - บทความต้นฉบับของ A* Algorithm
Korf, R. E. (1985). Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence, 27(1), 97-109. - บทความต้นฉบับของ IDS

แหล่งเรียนรู้ออนไลน์

Stanford CS221 - Artificial Intelligence: Principles and Techniques
- https://stanford-cs221.github.io/
MIT 6.034 - Artificial Intelligence
- https://ocw.mit.edu/courses/6-034-artificial-intelligence-fall-2010/

เครื่องมือและไลบรารี

NetworkX - Python Library for Graph Analysis
- https://networkx.org/
python-pathfinding - A* และอัลกอริทึมการหาเส้นทาง
- https://github.com/brean/python-pathfinding

หมายเหตุ: เอกสารนี้จัดทำขึ้นสำหรับวิชา Artificial Intelligence ระดับปริญญาตรี สาขาวิทยาการคอมพิวเตอร์ ครอบคลุมเนื้อหาสัปดาห์ที่ 3-4 ของหลักสูตร