การค้นหาปริภูมิสถานะ

การค้นหาปริภูมิสถานะคือการสำรวจอย่างเป็นระบบของชุดสถานะที่สามารถเข้าถึงได้จากสถานะเริ่มต้นผ่านการกระทำที่มีอยู่ เพื่อค้นหาสถานะที่ตรงตามเงื่อนไขเป้าหมายหรือเส้นทางที่นำไปสู่สถานะนั้น

Definition

การค้นหาปริภูมิสถานะถือว่าปัญหาเป็นกราฟที่โหนดคือสถานะและขอบคือกิจกรรม และดำเนินการโดยการขยายสถานะจากแนวหน้าตามกลยุทธ์ที่กำหนดไว้จนกว่าจะพบสถานะเป้าหมายหรือปริภูมิสถานะถูกสำรวจจนหมด

Scope

หัวข้อนี้ครอบคลุมการกำหนดปัญหาในรูปแบบปริภูมิสถานะ (สถานะ, การกระทำ, แบบจำลองการเปลี่ยนสถานะ, การทดสอบเป้าหมาย, ต้นทุนเส้นทาง) และกลยุทธ์การค้นหาแบบไม่ใช้ข้อมูลนำทาง (uninformed search strategies) ที่สำรวจปริภูมิสถานะโดยไม่มีคำแนะนำเฉพาะโดเมน ได้แก่ การค้นหาแบบกว้างก่อน (breadth-first), การค้นหาแบบต้นทุนสม่ำเสมอ (uniform-cost), การค้นหาแบบลึกก่อน (depth-first), การค้นหาแบบจำกัดความลึก (depth-limited) และการค้นหาแบบวนซ้ำเพิ่มความลึก (iterative-deepening search) รวมถึงการวิเคราะห์กลยุทธ์เหล่านี้ในด้านความสมบูรณ์ (completeness), ความเหมาะสมที่สุด (optimality), ความซับซ้อนเชิงเวลา (time complexity) และความซับซ้อนเชิงพื้นที่ (space complexity) และความแตกต่างระหว่างการค้นหาแบบต้นไม้ (tree search) กับการค้นหาแบบกราฟ (graph search) พร้อมการตรวจจับสถานะซ้ำ คำแนะนำแบบฮิวริสติกจะกล่าวถึงในหัวข้อแยกต่างหากเกี่ยวกับการค้นหาแบบฮิวริสติก (heuristic search) และ A*.

Core questions

• ปัญหาถูกนำเสนอเป็นสถานะ การกระทำ แบบจำลองการเปลี่ยนสถานะ และการทดสอบเป้าหมายได้อย่างไร?
• การค้นหาแบบกว้างก่อน แบบลึกก่อน แบบต้นทุนสม่ำเสมอ และแบบวนซ้ำเพิ่มความลึก แตกต่างกันอย่างไรในการจัดลำดับแนวหน้า?
• การรับประกันด้านความสมบูรณ์ ความเหมาะสมที่สุด เวลา และพื้นที่ของแต่ละกลยุทธ์แบบไม่ใช้ข้อมูลนำทางคืออะไร?
• การค้นหาแบบกราฟหลีกเลี่ยงการสำรวจสถานะซ้ำที่สิ้นเปลืองซึ่งการค้นหาแบบต้นไม้ยอมให้ได้อย่างไร?

Key concepts

• สถานะเริ่มต้นและการทดสอบเป้าหมาย
• แบบจำลองการเปลี่ยนสถานะและสถานะถัดไป
• แนวหน้า (รายการเปิด) และชุดที่สำรวจแล้ว
• การค้นหาแบบกว้างก่อน
• การค้นหาแบบลึกก่อน
• การค้นหาแบบต้นทุนสม่ำเสมอ
• การวนซ้ำเพิ่มความลึก
• การค้นหาแบบต้นไม้เทียบกับการค้นหาแบบกราฟ

Key theories

การจัดลำดับแนวหน้ากำหนดกลยุทธ์

อัลกอริทึมการค้นหาแบบไม่ใช้ข้อมูลนำทางแตกต่างกันเพียงแค่ลำดับที่พวกมันนำสถานะออกจากแนวหน้า: คิวแบบ FIFO ให้การค้นหาแบบกว้างก่อน, สแต็กแบบ LIFO ให้การค้นหาแบบลึกก่อน, และคิวลำดับความสำคัญตามต้นทุนเส้นทางให้การค้นหาแบบต้นทุนสม่ำเสมอ

การวนซ้ำเพิ่มความลึกเป็นค่าที่เหมาะสมที่สุดที่มีประสิทธิภาพเชิงพื้นที่

การค้นหาแบบวนซ้ำเพิ่มความลึกแบบลึกก่อนจะทำการค้นหาแบบลึกก่อนแบบจำกัดความลึกซ้ำๆ โดยเพิ่มขีดจำกัดความลึก ซึ่งรวมพื้นที่เชิงเส้นของการค้นหาแบบลึกก่อนเข้ากับความสมบูรณ์และความเหมาะสมที่สุด (สำหรับต้นทุนหน่วย) ของการค้นหาแบบกว้างก่อน

Clinical relevance

การค้นหาปริภูมิสถานะแบบไม่ใช้ข้อมูลนำทางเป็นรากฐานแนวคิดและการนำไปใช้สำหรับการค้นหาเส้นทาง การแก้ปริศนา การวิเคราะห์การเข้าถึงได้ในการตรวจสอบแบบจำลอง และเป็นพื้นฐานที่การค้นหาแบบฮิวริสติกและการค้นหาแบบคู่แข่งสร้างขึ้น การทำความเข้าใจความซับซ้อนของมันช่วยแนะนำว่าเมื่อใดที่การค้นหาแบบสุ่มสามารถทำได้เทียบกับเมื่อใดที่จำเป็นต้องใช้ฮิวริสติก

History

การค้นหาปริภูมิสถานะอย่างเป็นระบบสืบทอดมาจากอัลกอริทึมการสำรวจกราฟในทศวรรษ 1950 รวมถึงงานของมัวร์และไดค์สตราเกี่ยวกับการหาเส้นทางที่สั้นที่สุด และถูกกำหนดให้เป็นแบบจำลองของการแก้ปัญหาใน AI ยุคแรก การวิเคราะห์ของคอร์ฟในปี 1985 เกี่ยวกับการค้นหาแบบวนซ้ำเพิ่มความลึกได้สร้างความเหมาะสมที่สุดในบรรดาการค้นหาแบบต้นไม้ที่ยอมรับได้ซึ่งมีพื้นที่เชิงเส้น

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

เมื่อใดที่การค้นหาแบบกว้างก่อนเหมาะสมที่สุด?

การค้นหาแบบกว้างก่อนเหมาะสมที่สุดเมื่อทุกขั้นตอนมีต้นทุนเท่ากัน เนื่องจากมันจะพบเป้าหมายที่ตื้นที่สุดก่อน เมื่อต้นทุนขั้นตอนแตกต่างกัน การค้นหาแบบต้นทุนสม่ำเสมอ (ซึ่งจัดลำดับแนวหน้าตามต้นทุนเส้นทางสะสม) เป็นกลยุทธ์แบบไม่ใช้ข้อมูลนำทางที่รับประกันการได้มาซึ่งคำตอบที่มีต้นทุนต่ำที่สุด

ทำไมถึงใช้การวนซ้ำเพิ่มความลึกแทนการค้นหาแบบกว้างก่อนธรรมดา?

การค้นหาแบบกว้างก่อนจะเก็บแนวหน้าทั้งหมดและอาจต้องใช้หน่วยความจำแบบเอกซ์โพเนนเชียลตามความลึก การวนซ้ำเพิ่มความลึกจะทำการค้นหาแบบลึกก่อนซ้ำๆ โดยมีขีดจำกัดความลึกที่เพิ่มขึ้น โดยใช้หน่วยความจำเชิงเส้นเท่านั้นในขณะที่ยังคงสมบูรณ์และเหมาะสมที่สุดสำหรับปัญหาที่มีต้นทุนหน่วย โดยมีค่าใช้จ่ายในการขยายโหนดตื้นซ้ำ