การค้นหาแบบฮิวริสติกและ A*

การค้นหาแบบฮิวริสติกใช้การประมาณค่าเฉพาะปัญหาของต้นทุนที่เหลืออยู่เพื่อไปสู่เป้าหมายเพื่อนำทางว่าควรสำรวจสถานะใดก่อน; A* เป็นอัลกอริทึมหลัก โดยขยายสถานะตามลำดับผลรวมของต้นทุนที่เกิดขึ้นแล้วและต้นทุนที่ประมาณการว่าจะเกิดขึ้น

Definition

การค้นหาแบบฮิวริสติกคือการค้นหาแบบมีข้อมูลที่จัดลำดับขอบเขตโดยใช้ฟังก์ชันการประเมินที่รวมต้นทุนที่ทราบจากจุดเริ่มต้นเข้ากับการประมาณค่าฮิวริสติกของต้นทุนที่เหลืออยู่; A* ใช้ f(n) = g(n) + h(n) และเหมาะสมที่สุดเมื่อ h ยอมรับได้

Scope

หัวข้อนี้ครอบคลุมกลยุทธ์การค้นหาแบบมีข้อมูล (ฮิวริสติก) โดยเน้นที่การค้นหาแบบ Best-First และอัลกอริทึม A* รวมถึงการออกแบบและคุณสมบัติของฟังก์ชันฮิวริสติก (ความยอมรับได้, ความสอดคล้อง/ความเป็นโมโนโทนิก) การรับประกันความเหมาะสมและประสิทธิภาพที่คุณสมบัติเหล่านี้มอบให้ และรูปแบบที่จำกัดหน่วยความจำ เช่น Iterative-Deepening A* (IDA*) นอกจากนี้ยังกล่าวถึงวิธีการสร้างฮิวริสติก (ปัญหาที่ผ่อนคลาย, ฐานข้อมูลรูปแบบ) และวิธีการแลกเปลี่ยนความแม่นยำกับการคำนวณ การเรียนรู้ฮิวริสติกจากข้อมูลจัดอยู่ในสาขาย่อยของการเรียนรู้ของเครื่อง

Core questions

• อะไรทำให้ฮิวริสติกยอมรับได้ และเหตุใดความยอมรับได้จึงรับประกันความเป็นเลิศของ A*?
• ความสอดคล้อง (ความเป็นโมโนโทนิก) เสริมสร้างการรับประกันและป้องกันการขยายโหนดซ้ำได้อย่างไร?
• ฮิวริสติกที่ดีได้รับการออกแบบอย่างไร เช่น จากปัญหาเวอร์ชันที่ผ่อนคลาย?
• รูปแบบที่จำกัดหน่วยความจำ เช่น IDA* รักษาความเป็นเลิศด้วยพื้นที่จำกัดได้อย่างไร?

Key concepts

• ฟังก์ชันการประเมิน f = g + h
• ฮิวริสติกที่ยอมรับได้
• ฮิวริสติกที่สอดคล้อง (โมโนโทน)
• การค้นหาแบบ Greedy Best-First
• การค้นหาแบบ A*
• การค้นหาแบบ Iterative-Deepening A* (IDA*)
• การครอบงำของฮิวริสติก
• ปัญหาที่ผ่อนคลายและฐานข้อมูลรูปแบบ

Key theories

ความเป็นเลิศของ A* ภายใต้ฮิวริสติกที่ยอมรับได้

เมื่อฮิวริสติก h ไม่เคยประมาณค่าต้นทุนที่แท้จริงที่เหลืออยู่เกินจริง A* จะขยายโหนดโดยเพิ่ม f = g + h และรับประกันว่าจะส่งคืนเส้นทางที่มีต้นทุนน้อยที่สุด; ในบรรดาอัลกอริทึมที่ใช้ข้อมูลฮิวริสติกเดียวกัน A* มีประสิทธิภาพสูงสุด

การออกแบบฮิวริสติกผ่านการผ่อนคลาย

ฮิวริสติกที่ยอมรับได้สามารถได้มาอย่างเป็นระบบโดยการแก้ปัญหาเวอร์ชันที่ผ่อนคลาย (ปัญหาที่มีข้อจำกัดในการกระทำน้อยลง) เนื่องจากต้นทุนที่แน่นอนของปัญหาที่ง่ายกว่าเป็นขีดจำกัดล่างของปัญหาเดิม; ฮิวริสติกที่ครอบงำ (มีข้อมูลมากกว่า) จะขยายโหนดน้อยลง

การค้นหาแบบฮิวริสติกที่จำกัดหน่วยความจำ

Iterative-Deepening A* ทำการค้นหาแบบ Depth-First ที่ต่อเนื่องกันโดยมีขีดจำกัด f-cost ที่เพิ่มขึ้น ทำให้ได้ความเป็นเลิศแบบ A* ด้วยหน่วยความจำที่เป็นเชิงเส้นตามความลึกของคำตอบ

Clinical relevance

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

History

อัลกอริทึม A* ถูกนำเสนอโดย Hart, Nilsson, และ Raphael (1968) ซึ่งให้พื้นฐานความเป็นเลิศอย่างเป็นทางการแก่การค้นหาแบบฮิวริสติก หนังสือ Heuristics ของ Pearl ในปี 1984 ได้ให้การวิเคราะห์ทางทฤษฎีที่ชัดเจน และ IDA* ของ Korf ในปี 1985 ได้แก้ไขปัญหาต้นทุนหน่วยความจำของ A* ผลลัพธ์เหล่านี้ยังคงเป็นเนื้อหาหลักในการศึกษา AI

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

ฮิวริสติกที่ยอมรับได้คืออะไร?

ฮิวริสติกจะยอมรับได้ก็ต่อเมื่อไม่เคยประมาณค่าต้นทุนที่แท้จริงในการไปถึงเป้าหมายจากสถานะใดๆ เกินจริง ความยอมรับได้เป็นเงื่อนไขที่ A* รับประกันว่าจะพบคำตอบที่เหมาะสมที่สุด (ต้นทุนน้อยที่สุด)

ความแตกต่างระหว่างการค้นหาแบบ Greedy Best-First และ A* คืออะไร?

การค้นหาแบบ Greedy Best-First จะขยายสถานะที่ดูเหมือนใกล้เป้าหมายที่สุดตามฮิวริสติกเพียงอย่างเดียว (h) ซึ่งรวดเร็วแต่อาจห่างไกลจากความเหมาะสมที่สุด A* จะเพิ่มต้นทุนจริงที่เกิดขึ้นแล้ว (g) โดยขยายตาม f = g + h ซึ่งรักษาความเป็นเลิศเมื่อฮิวริสติกยอมรับได้