เทคนิคการค้นหาสำหรับปัญญาประดิษฐ์

การแก้ปัญหาในงานปัญญาประดิษฐ์จำนวนมากสามารถมองเป็นปัญหาการค้นหาได้ โดยเริ่มจากสถานะตั้งต้น แล้วใช้กฎหรือการกระทำเพื่อเปลี่ยนไปยังสถานะถัดไปจนถึงสถานะเป้าหมาย

ศึกษาแนวคิด State Space, Search Tree, Uninformed Search ได้แก่ BFS, DFS, Iterative Deepening และ Informed Search ได้แก่ Best-First Search และ A* พร้อมเปรียบเทียบประสิทธิภาพด้านเวลาและหน่วยความจำ ตลอดจนฝึกเขียนโปรแกรม Python โดยใช้เครื่องมืออย่าง heapq หรือแนวคิดกราฟเพื่อแก้ปัญหา

3. ความหมายของการค้นหาใน AI

การค้นหา คือกระบวนการหาลำดับของการกระทำจากสถานะเริ่มต้นไปยังเป้าหมาย เช่น การหาเส้นทางในเขาวงกต การจัดเรียงปริศนา หรือการวางแผนการทำงานในระบบอัตโนมัติ

องค์ประกอบสำคัญของปัญหาการค้นหา มีดังนี้

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

• สถานะเป้าหมาย (Goal State)

• ตัวดำเนินการ (Operators)

• เส้นทางคำตอบ (Solution Path)

• ต้นทุน (Cost)

4. State Space และ Search Tree

State Space คือเซตของสถานะทั้งหมดที่อาจเกิดขึ้นได้จากปัญหาหนึ่ง ส่วน Search Tree คือโครงสร้างต้นไม้ที่ใช้แสดงการแตกแขนงของการค้นหาจากสถานะเริ่มต้นไปยังสถานะอื่น ๆ

ตัวอย่างในปัญหา Maze แต่ละตำแหน่งในตารางสามารถถือเป็นหนึ่งสถานะ ส่วนการเดินขึ้น ลง ซ้าย ขวา เป็นการเปลี่ยนจากสถานะหนึ่งไปสู่อีกสถานะหนึ่ง

5. อัลกอริทึมการค้นหา

5.1 Breadth-First Search (BFS)

BFS เป็นการค้นหาแบบขยายโหนดทีละระดับ โดยจะสำรวจโหนดที่อยู่ชั้นเดียวกันให้ครบก่อนค่อยลงไปยังระดับลึกกว่า

ลักษณะเด่นของ BFS

• มักได้คำตอบที่สั้นที่สุดเมื่อแต่ละก้าวมีต้นทุนเท่ากัน

• เหมาะกับปัญหาที่คำตอบอยู่ไม่ลึกมาก

• ใช้หน่วยความจำมาก เพราะต้องเก็บโหนดในแต่ละระดับ

BFS มักใช้โครงสร้างข้อมูลแบบคิว (Queue)

5.2 Depth-First Search (DFS)

DFS เป็นการค้นหาแบบลงลึกไปตามกิ่งใดกิ่งหนึ่งก่อน หากยังไม่พบคำตอบจึงย้อนกลับมาสำรวจกิ่งอื่น

ลักษณะเด่นของ DFS

• ใช้หน่วยความจำน้อยกว่า BFS ในหลายกรณี

• เหมาะกับปัญหาที่ต้องการสำรวจเชิงลึก

• อาจไม่พบคำตอบที่สั้นที่สุด

DFS มักใช้โครงสร้างข้อมูลแบบสแตก (Stack) หรือการเรียกซ้ำ

5.3 A* Search

A* เป็นอัลกอริทึมที่พิจารณาทั้งต้นทุนที่ใช้ไปแล้วและต้นทุนประมาณการที่เหลือ โดยใช้ฟังก์ชันประเมิน

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

โดยที่

• g(n)g(n) คือ ต้นทุนจริงจากจุดเริ่มต้นมายังโหนดปัจจุบัน

• h(n)h(n) คือ ค่าประมาณจากโหนดปัจจุบันไปยังเป้าหมาย

• f(n)f(n) คือ ค่าที่ใช้ตัดสินใจเลือกโหนดถัดไป

A* นิยมใช้กับการหาเส้นทาง เพราะหากเลือกฮิวริสติกได้เหมาะสมจะให้ผลลัพธ์ที่ดีและมีประสิทธิภาพ

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

6. ตารางเปรียบเทียบอัลกอริทึม

อัลกอริทึมหลักการทำงานจุดเด่นข้อจำกัดBFSค้นหาแบบทีละระดับได้คำตอบสั้นที่สุดเมื่อ cost เท่ากัน ใช้หน่วยความจำมาก DFSค้นหาแบบลงลึกก่อนใช้หน่วยความจำน้อย อาจไม่ใช่คำตอบที่ดีที่สุด A*ใช้ต้นทุนจริงร่วมกับฮิวริสติกแม่นยำและมีประสิทธิภาพเมื่อฮิวริสติกดี ต้องออกแบบฮิวริสติกให้เหมาะสม

7. ตัวอย่างปัญหา Maze

ตัวอย่างต่อไปนี้ใช้ตาราง Maze ขนาดเล็ก โดยกำหนดให้ S เป็นจุดเริ่มต้น G เป็นเป้าหมาย # เป็นกำแพง และช่องว่างหมายถึงทางเดิน เพื่อใช้ทดลองกับ BFS, DFS และ A*