การค้นหาและการแก้ปัญหา
การค้นหาและการแก้ปัญหาเป็นสาขาหนึ่งของปัญญาประดิษฐ์ที่เกี่ยวข้องกับการกำหนดงานในรูปแบบของการสำรวจพื้นที่ของสถานะหรือการกำหนดค่า และการค้นหาลำดับของการกระทำ การมอบหมาย หรืองานที่นำไปสู่เป้าหมาย
Definition
การแก้ปัญหาโดยอาศัยการค้นหา (search-based problem solving) แสดงงานในรูปแบบของสถานะเริ่มต้น (initial state) ชุดของการกระทำที่เปลี่ยนแปลงสถานะ การทดสอบเป้าหมาย (goal test) และต้นทุนเส้นทาง (path cost) และแก้ไขปัญหาโดยการสำรวจสถานะที่เข้าถึงได้ (reachable states) อย่างเป็นระบบจนกว่าจะพบสถานะเป้าหมาย (หรือเส้นทางที่มีต้นทุนต่ำที่สุดไปยังสถานะนั้น)
Scope
สาขานี้ครอบคลุมการกำหนดปัญหาในรูปแบบของปริภูมิสถานะ (state space) และอัลกอริทึมที่ใช้ในการสำรวจ ได้แก่ การค้นหาแบบไม่ใช้ข้อมูลนำทาง (uninformed/blind search) เช่น breadth-first และ depth-first, การค้นหาแบบใช้ข้อมูลนำทาง (informed/heuristic search) เช่น A* และ greedy best-first, การค้นหาแบบคู่แข่ง (adversarial search) สำหรับเกมผู้เล่นสองคน และการแก้ปัญหาข้อจำกัด (constraint satisfaction) โดยจะกล่าวถึงวิธีการจำลองปัญหาเป็นสถานะ การกระทำ และการทดสอบเป้าหมาย รวมถึงการวิเคราะห์ความสมบูรณ์ (completeness) ความเหมาะสมที่สุด (optimality) เวลา และพื้นที่ อย่างไรก็ตาม ไม่รวมถึงการเรียนรู้ฮิวริสติกส์ (heuristics) หรือฟังก์ชันการประเมินจากข้อมูล ซึ่งเป็นส่วนหนึ่งของสาขาย่อยการเรียนรู้ของเครื่อง (machine learning) ที่แยกต่างหาก
Sub-topics
Core questions
- งานในโลกแห่งความเป็นจริงถูกกำหนดเป็นปริภูมิสถานะที่มีสถานะ การกระทำ และการทดสอบเป้าหมายได้อย่างไร?
- อัลกอริทึมการค้นหาจะสมบูรณ์ (รับประกันว่าจะพบวิธีแก้ปัญหาหากมีอยู่) และเหมาะสมที่สุด (รับประกันว่าจะพบวิธีแก้ปัญหาที่มีต้นทุนต่ำที่สุด) เมื่อใด?
- ฟังก์ชันฮิวริสติกนำทางการค้นหาไปสู่เป้าหมายได้อย่างไรในขณะที่ยังคงรักษาความเหมาะสมที่สุดไว้?
- จะควบคุมการระเบิดเชิงการจัดหมู่ (combinatorial explosion) ของปริภูมิสถานะโดยการตัดแต่ง (pruning) หรือการจัดลำดับแบบมีข้อมูลนำทางได้อย่างไร?
- การค้นหาเปลี่ยนแปลงไปอย่างไรเมื่อมีคู่แข่งเลือกการเคลื่อนไหวบางอย่าง?
Key concepts
- ปริภูมิสถานะ (state space)
- ต้นไม้การค้นหา (search tree) และกราฟการค้นหา (search graph)
- การค้นหาแบบไม่ใช้ข้อมูลนำทาง (uninformed/blind search)
- ฟังก์ชันฮิวริสติก (heuristic function)
- ความยอมรับได้ (admissibility) และความสอดคล้อง (consistency)
- การค้นหา A* (A* search)
- ปัจจัยการแตกกิ่ง (branching factor) และความลึกของการค้นหา (search depth)
- ความสมบูรณ์ (completeness) และความเหมาะสมที่สุด (optimality)
- การแก้ปัญหาข้อจำกัด (constraint satisfaction)
Key theories
- ฮิวริสติกที่ยอมรับได้และความเหมาะสมที่สุดของ A*
- หากฮิวริสติกไม่เคยประเมินต้นทุนที่แท้จริงไปยังเป้าหมายสูงเกินไป (ยอมรับได้) การค้นหา A* จะขยายโหนดตามลำดับ best-first ของ f = g + h และรับประกันว่าจะได้วิธีแก้ปัญหาที่เหมาะสมที่สุด ความสอดคล้องยังรับประกันว่าจะไม่มีการขยายโหนดซ้ำ
- การแลกเปลี่ยนระหว่างการค้นหาแบบไม่ใช้ข้อมูลนำทางกับการค้นหาแบบใช้ข้อมูลนำทาง
- กลยุทธ์แบบไม่ใช้ข้อมูลนำทาง (blind strategies) (breadth-first, uniform-cost, depth-first, iterative deepening) แตกต่างกันเพียงลำดับของโหนดและให้การรับประกันโดยไม่ต้องใช้ความรู้เฉพาะโดเมน ในขณะที่การประมาณค่าฮิวริสติกของต้นทุนที่เหลืออยู่สามารถลดพื้นที่ที่สำรวจได้อย่างมาก แต่ก็มีความเสี่ยงที่จะสูญเสียความเหมาะสมที่สุดหากฮิวริสติกไม่ยอมรับได้
- การกำหนดปัญหาเป็นการค้นหาปริภูมิสถานะ
- งานหลากหลายประเภทสามารถแก้ไขได้เมื่อถูกกำหนดเป็นการค้นหาผ่านสถานะที่เชื่อมโยงกันด้วยการกระทำ ทำให้การเลือกการแสดงสถานะและตัวดำเนินการเป็นการตัดสินใจออกแบบที่สำคัญซึ่งกำหนดปัจจัยการแตกกิ่งและความลึกของวิธีแก้ปัญหา
Clinical relevance
การค้นหาเป็นพื้นฐานของระบบปฏิบัติการจำนวนมาก: การวางแผนเส้นทางและการนำทาง (A* บนเครือข่ายถนน), กลไกปริศนาและเกม, การกำหนดค่าและการจัดตารางเวลาอัตโนมัติ, การวางแผนการเคลื่อนที่ของหุ่นยนต์ และเป็นแกนหลักของการวางแผนอัตโนมัติและตัวแก้ปัญหาข้อจำกัดที่ใช้ในการขนส่งและวิจัยปฏิบัติการ
History
การค้นหาเป็นหัวใจสำคัญของ AI มาตั้งแต่ยุคแรกเริ่ม โดย General Problem Solver ของ Newell และ Simon (ปลายทศวรรษ 1950) ได้กำหนดกรอบของปัญญาเป็นการค้นหาผ่านปริภูมิปัญหา (problem spaces) อัลกอริทึม A* (Hart, Nilsson, Raphael, 1968) ได้ให้พื้นฐานความเหมาะสมที่สุดที่เข้มงวดแก่การค้นหาแบบฮิวริสติก และเอกสารวิชาการของ Pearl ในปี 1984 ได้จัดระบบทฤษฎีการค้นหาแบบฮิวริสติก กรอบการทำงานนี้ยังคงเป็นเลนส์จัดระเบียบมาตรฐานในตำราเรียน AI
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- ความแตกต่างระหว่างการค้นหาแบบไม่ใช้ข้อมูลนำทางกับการค้นหาแบบใช้ข้อมูลนำทางคืออะไร?
- การค้นหาแบบไม่ใช้ข้อมูลนำทาง (uninformed/blind search) เช่น breadth-first หรือ depth-first search จะไม่ใช้ข้อมูลใดๆ เกี่ยวกับความใกล้เคียงของสถานะกับเป้าหมาย และสำรวจโดยอาศัยโครงสร้างของปริภูมิสถานะเท่านั้น การค้นหาแบบใช้ข้อมูลนำทาง (informed/heuristic search) ใช้การประมาณค่าต้นทุนที่เหลืออยู่ไปยังเป้าหมายเพื่อจัดลำดับความสำคัญของสถานะที่จะขยาย ซึ่งอาจมีประสิทธิภาพมากกว่ามาก
- ทำไม A* จึงถูกใช้อย่างแพร่หลาย?
- A* รวมต้นทุนจริงจากจุดเริ่มต้น (g) เข้ากับการประมาณค่าฮิวริสติกไปยังเป้าหมาย (h) และเมื่อฮิวริสติกยอมรับได้ จะรับประกันว่าจะพบวิธีแก้ปัญหาที่เหมาะสมที่สุดในขณะที่โดยทั่วไปแล้วจะสำรวจสถานะน้อยกว่าการค้นหาแบบไม่ใช้ข้อมูลนำทางมาก ความสมดุลระหว่างความเหมาะสมที่สุดและประสิทธิภาพนี้ทำให้เป็นตัวเลือกเริ่มต้นสำหรับการค้นหาเส้นทาง