Search & Pathfinding in AI: จากอัลกอริทึมคลาสสิกสู่การประยุกต์ใช้สมัยใหม่

“การค้นหา (Search) คือหัวใจของปัญญาประดิษฐ์ - ตั้งแต่การเดินหมากรุกไปจนถึงการที่ ChatGPT เลือกคำตอบให้คุณ”

🎯 บทนำ: ทำไม "Search" ถึงสำคัญ?

ลองนึกภาพว่าคุณอยู่ที่ MRT จตุจักร และต้องการไปตลาด อ.ต.ก. คุณมีทางเลือกมากมาย - จะเดินตรงไป? จะอ้อมไปตามถนนใหญ่? หรือจะลัดซอย? การตัดสินใจนี้คือสิ่งที่เราเรียกว่า “Search Problem” ในโลกของ AI

แต่ “Search” ในที่นี้ไม่ได้หมายถึงการค้นหาแบบ Google Search นะครับ แต่หมายถึง การสำรวจทางเลือกต่างๆ อย่างเป็นระบบเพื่อหาคำตอบที่ดีที่สุด ไม่ว่าจะเป็น:

• 🗺️ Google Maps ค้นหาเส้นทางที่ดีที่สุดจากบ้านไปที่ทำงาน
• ♟️ หมากรุก AI ค้นหาการเดินหมากที่ดีที่สุดจากสถานการณ์ปัจจุบัน
• 🤖 ChatGPT ค้นหาคำที่เหมาะสมที่สุดในการตอบคำถาม
• 📦 หุ่นยนต์ในคลังสินค้า ค้นหาเส้นทางที่เร็วที่สุดในการเก็บของ

ทั้งหมดนี้ใช้หลักการ "Search" เหมือนกันหมด!

🧩 State-Space: การมองปัญหาแบบ AI

หัวใจของการแก้ปัญหาด้วย Search คือการแปลงปัญหาในโลกจริงให้เป็น “State-Space Representation” ลองดูองค์ประกอบสำคัญ:

1. State (สถานะ)

“ตอนนี้อยู่ตรงไหน” — การบรรยายสถานการณ์ ณ ขณะใดขณะหนึ่ง

• ในแผนที่: “อยู่ที่สี่แยกลาดพร้าว”
• ในหมากรุก: “ตำแหน่งของหมากทุกตัวบนกระดาน”
• ใน 8-puzzle: “ตำแหน่งของตัวเลขแต่ละตัว”

2. Initial State (สถานะเริ่มต้น)

“จุดเริ่มต้นของปัญหา” เช่น “ตอนนี้อยู่ที่ MRT จตุจักร”

3. Actions (การกระทำ)

“ทำอะไรได้บ้างในแต่ละสถานะ”

• บนถนน: “เลี้ยวซ้าย, เลี้ยวขวา, ตรงไป, กลับรถ”
• ใน 8-puzzle: “เลื่อนช่องว่างขึ้น, ลง, ซ้าย, ขวา”

4. Transition Model (ผลของการกระทำ)

“ถ้าทำ Action X ใน State Y จะไปอยู่ State ไหน” เช่น “ถ้าเลี้ยวซ้ายที่สี่แยกลาดพร้าว → จะไปอยู่ที่ถนนพหลโยธิน”

5. Goal Test (การทดสอบเป้าหมาย)

“ถึงจุดหมายหรือยัง?” เช่น “ถึงตลาด อ.ต.ก. แล้วหรือยัง?”

6. Path Cost (ต้นทุน)

“ใช้ทรัพยากรไปเท่าไหร่” เช่น ระยะทาง, เวลา, ค่าน้ำมัน, ค่าผ่านทาง

🎲 ตัวอย่างที่ชัดเจน: 8-Puzzle

Initial State:        Goal State:
2 8 3                1 2 3
1 6 4       →        4 5 6
7 _ 5                7 8 _
    

States: การจัดเรียงตัวเลขที่เป็นไปได้ทั้งหมด (362,880 แบบ!)
Actions: เลื่อนช่องว่างไปทิศทางที่เป็นไปได้
Path Cost: จำนวนครั้งที่เลื่อน
คำถามคือ: จะหาลำดับการเลื่อนที่น้อยที่สุดได้อย่างไร? 🤔

🌲 Search Tree: การมองปัญหาเป็นต้นไม้

                    [Start State]
                    /     |      \
               [State A] [State B] [State C]
              /    \        |         /    \
          [...]   [...]  [Goal!]  [...]   [...]
  

Root (ราก): สถานะเริ่มต้น
Branches (กิ่ง): การกระทำที่เป็นไปได้
Nodes (โหนด): สถานะต่างๆ
Leaves (ใบ): สถานะที่ไม่มีทางไปต่อ หรือเป้าหมาย

ปัญหาคือ: ต้นไม้นี้ใหญ่มาก! Bangkok มีสี่แยก ~50,000 แห่ง ถ้าแต่ละแยกไปได้ 4 ทิศ...นั่นคือทางเลือกมหาศาล! 😱

🔦 Uninformed Search: การค้นหาแบบ "มืดบอด"

1. Breadth-First Search (BFS) - ค้นหาแบบกว้าง

หลักการ: สำรวจทีละระดับ เหมือนคลื่นน้ำที่กระจายออกไป

ระดับ 0: [Start]
ระดับ 1: [ทุกจุดที่ห่าง 1 ก้าว]
ระดับ 2: [ทุกจุดที่ห่าง 2 ก้าว]
...จนเจอเป้าหมาย
  

• ✅ รับประกันว่าจะเจอเส้นทางที่สั้นที่สุด (ถ้าวัดเป็นจำนวนก้าว)
• ✅ จะเจอคำตอบแน่นอน (ถ้ามี)
• ❌ ใช้หน่วยความจำมหาศาล (ต้องจำทุกจุดที่เคยไป)
• ❌ ช้ามากถ้าเป้าหมายอยู่ไกล

เหมาะกับปัญหาที่เป้าหมายอยู่ไม่ลึก หรือต้องการเส้นทางที่สั้นที่สุดแน่ๆ

2. Depth-First Search (DFS) - ค้นหาแบบลึก

หลักการ: ดำดิ่งลงไปให้สุดก่อน ถ้าติดก็ถอยกลับมาลองทางอื่น

Start → A → B → C → ติด!
            ↑
            กลับมาที่ B
            ↓
            D → E → Goal!
  

• ✅ ใช้หน่วยความจำน้อย (จำแค่เส้นทางปัจจุบัน)
• ✅ อาจโชคดีเจอคำตอบเร็ว
• ❌ อาจไม่เจอเส้นทางที่ดีที่สุด
• ❌ อาจติดอยู่ในทางที่ลึกมากๆ

เหมาะกับปัญหาที่มีคำตอบหลายทาง และไม่จำเป็นต้องดีที่สุด

🧭 Informed Search: การค้นหาแบบ "มีเข็มทิศ"

Heuristic Function: เข็มทิศของ AI

Heuristic h(n) คือ "การประมาณการ" ว่าจากจุด n ไปถึงเป้าหมายน่าจะไกลแค่ไหน

ตัวอย่าง Heuristics ที่ดี:

1. ระยะทางเส้นตรง (Euclidean Distance)
   — จากจตุจักรถึงสยาม = 5.2 km ทางอากาศ
2. ระยะ Manhattan
   — |x₁-x₂| + |y₁-y₂| เหมาะกับเมืองที่ถนนเป็นตาราง
3. จำนวนชิ้นที่อยู่ผิดที่
   — สำหรับ 8-puzzle ถ้ามี 5 ตัวเลขอยู่ผิดที่ = h(n) = 5

คุณสมบัติของ Heuristic ที่ดี

• Admissible: ไม่ประมาณเกินจริง (h(n) ≤ ต้นทุนจริง) → A* ได้ผลลัพธ์ optimal
• Consistent: สม่ำเสมอ (h(n) ≤ cost(n,n') + h(n')) → A* ทำงานมีประสิทธิภาพ

⭐ A* Algorithm: จุดสุดยอดของ Search

สูตรทองคำ: f(n) = g(n) + h(n)

A* ผสมผสานระหว่าง:

• g(n): ต้นทุนจริงจาก start → n
• h(n): ประมาณการจาก n → goal
• f(n): ต้นทุนรวมที่คาดการณ์ผ่าน n

ทำไม A* ถึงฉลาด?

เลือกสำรวจ node ที่มี f(n) ต่ำสุดก่อน:

• ไม่มองแค่ “มาไกลแค่ไหน” (Dijkstra)
• ไม่มองแค่ “เหลืออีกไกลแค่ไหน” (Greedy)
• แต่มองทั้ง “มาไกลแค่ไหน + เหลืออีกเท่าไหร่”

ตัวอย่างการทำงาน

จาก จตุจักร → สยาม:

Node A: ผ่านพหลโยธิน
- g(A) = 2 km
- h(A) = 4 km
- f(A) = 6 km

Node B: ผ่านลาดพร้าว
- g(B) = 1.5 km
- h(B) = 4.5 km
- f(B) = 6 km

Node C: ผ่านรัชดา
- g(C) = 2.5 km
- h(C) = 3 km
- f(C) = 5.5 km ← A* จะเลือกทางนี้!
  

ประสิทธิภาพของ A*

• Optimal: ได้คำตอบดีที่สุดถ้า h(n) admissible
• Complete: จะหาคำตอบได้แน่นอนถ้ามี
• Efficient: ไม่มีอัลกอริทึม optimal ใดสำรวจ node น้อยกว่า

🌍 การประยุกต์ใช้ในโลกจริง

1. 🗺️ Navigation Systems (Google Maps, Grab)

Nodes: สี่แยก, ทางแยก (~50,000 จุดใน กทม.)
Edges: ถนนที่เชื่อมระหว่างจุด
Weights: ระยะทาง, เวลา, ค่าผ่านทาง

• ข้อมูลขนาดใหญ่ (ประเทศ = ล้าน nodes)
• Multiple criteria (เร็ว vs ประหยัด vs ปลอดภัย)
• Real-time updates (การจราจร, อุบัติเหตุ)

เทคนิคเพิ่มเติม: Hierarchical A*, Bidirectional Search, Contraction Hierarchies

2. 🤖 AI Text Generation (ChatGPT, Gemini)

State: ประโยคที่สร้างมาแล้ว
Actions: เลือกคำถัดไป
Goal: ประโยคที่สมบูรณ์และตอบโจทย์

State space ใหญ่ (50,000ⁿ สำหรับ n คำ), ไม่มี goal state ชัดเจน

Beam Search: A* สำหรับ NLP

1. เก็บแค่ k ตัวเลือกที่ดีที่สุด (beam width)
2. ขยายทั้ง k ตัวเลือกในแต่ละขั้น
3. เลือกเก็บ k อันดับแรกใหม่

"The weather" →
  1. "The weather is" (score: 0.8)
  2. "The weather was" (score: 0.7)
  3. "The weather will" (score: 0.6)
  [ตัดทิ้ง: "The weather cat" (score: 0.1)]
  

3. 🎮 Game AI

State: ตำแหน่งหมาก
Actions: การเดินที่ถูกกฎ
Evaluation: ประเมินความได้เปรียบ

Modern approach: Alpha-Beta Pruning, Monte Carlo Tree Search, Neural Networks for evaluation

4. 🤖 Robotics Path Planning

ความท้าทาย: Continuous space, Dynamic obstacles, Multiple dimensions

• Rapidly-exploring Random Trees (RRT)
• Probabilistic Roadmaps (PRM)
• Dynamic A* (D*)

💡 Insights ที่สำคัญ

1. Trade-offs ที่ต้องเลือก

• A* + admissible heuristic → Optimal
• หน่วยความจำจำกัด → IDA* (Iterative Deepening A*)
• Real-time → Anytime algorithms
• ไม่รู้ goal ชัดเจน → Best-first search variants

2. Heuristic คือกุญแจสำคัญ

• h(n)=0 → A* กลายเป็น Dijkstra (ช้าแต่ optimal)
• h(n)=ระยะเส้นตรง → A* มีประสิทธิภาพ
• h(n)>ต้นทุนจริง → อาจไม่ optimal แต่เร็วขึ้น

3. จาก 1960s → 2020s

• 1968: A* ถูกคิดค้น
• 1990s: ใช้ใน video games
• 2000s: Google Maps scale up
• 2010s: ผสมกับ Machine Learning
• 2020s: Neural heuristics, Learned search

🎯 สรุป: ทำไมต้องเรียน Search?

1. Foundation of AI: พื้นฐานของ planning, reasoning, optimization
2. Computational Thinking: systematic thinking, แยกปัญหา, มอง trade-offs
3. Real Impact: ใช้จริงทุกวัน (Google Maps, AI ตอบคำถาม, เกมคอมพิวเตอร์)
4. Bridge to Modern AI: เชื่อมไปสู่ ML, Reinforcement Learning, Neural Networks

🚀 ก้าวต่อไป

Search algorithms เป็นเพียงจุดเริ่มต้น สัปดาห์หน้าเราจะเรียนรู้ว่า:

• ถ้าเราไม่รู้ rules ของปัญหาล่ะ?
• ถ้าเราต้องการให้ AI “เรียนรู้” จากข้อมูล?
• Machine Learning จะเข้ามาเปลี่ยนเกมอย่างไร?

บทความนี้เป็นส่วนหนึ่งของ AI Course Week 2: Search & Pathfinding
สามารถใช้ควบคู่กับ slides และ lab materials