Skip to content
กลับไปยังผลการค้นหา

ขั้นตอนวิธีค้นหา A*

ผู้เสนอ
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
ปี
1968
ประเภท
algorithm
กลุ่มวิธี
Graph Algorithms

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

ขั้นตอนวิธีค้นหา A* (A* Search Algorithm) ซึ่งพัฒนาโดย Peter E. Hart, Nils J. Nilsson และ Bertram Raphael ในปี 1968 เป็นขั้นตอนวิธีค้นหาเส้นทางที่เหมาะสมที่สุดที่รวมข้อดีของขั้นตอนวิธีของ Dijkstra เข้ากับการชี้นำด้วยฮิวริสติก โดยจะค้นหาเส้นทางที่สั้นที่สุดได้อย่างมีประสิทธิภาพโดยการปรับสมดุลระหว่างระยะทางจริงจากจุดเริ่มต้นกับระยะทางโดยประมาณไปยังเป้าหมาย

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

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

ควรใช้เมื่อใด

ใช้ A* เมื่อคุณต้องการค้นหาเส้นทางที่เหมาะสมที่สุดในกราฟที่มีฟังก์ชันฮิวริสติกที่ดี มันมีประสิทธิภาพเป็นพิเศษสำหรับการค้นหาเส้นทางในเกม หุ่นยนต์ และการวางแผนเส้นทางที่การค้นหาแบบรู้ข้อมูลสามารถลดการคำนวณลงได้อย่างมาก ใช้เมื่อความเร็วมีความสำคัญแต่ต้องการความเป็นที่สุด สำหรับกรณีที่ไม่มีฮิวริสติกที่เชื่อถือได้ ให้ใช้ขั้นตอนวิธีของ Dijkstra แทน

ข้อจำกัดและข้อควรพิจารณา

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

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

จุดแข็ง

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

การประยุกต์ใช้

  • การค้นหาเส้นทางในวิดีโอเกม: การนำทาง NPC แบบเรียลไทม์ในสภาพแวดล้อมเกมแบบไดนามิก
  • การวางแผนการเคลื่อนที่ของหุ่นยนต์: การวางแผนเส้นทางที่เหมาะสมที่สุดสำหรับหุ่นยนต์อัตโนมัติที่หลีกเลี่ยงสิ่งกีดขวาง
  • การนำทางด้วย GPS: การคำนวณเส้นทางที่มีประสิทธิภาพโดยพิจารณาเครือข่ายถนนและการจราจร
  • การแก้ปริศนา: การค้นหาคำตอบที่เหมาะสมที่สุดในปัญหาเชิงการจัดหมู่ เช่น ปริศนา 15 ตัว
  • การกำหนดเส้นทางเครือข่าย: การกำหนดเส้นทางแพ็กเก็ตที่มีประสิทธิภาพด้วยฮิวริสติกคุณภาพลิงก์
  • ชีวสารสนเทศ: การจัดเรียงลำดับและการค้นหาการทำนายโครงสร้างโปรตีน

วิธีการทำงาน

วิธีการทำงาน

1

สร้างชุดเปิด (open set) ด้วยโหนดเริ่มต้น กำหนดค่า g (ต้นทุนจากจุดเริ่มต้น) เป็นศูนย์ และคำนวณค่า h โดยใช้ฟังก์ชันฮิวริสติก

2

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

3

ดำเนินการขยายโหนดต่อไปจนกว่าจะถึงเป้าหมายด้วยค่า f ที่ต่ำที่สุด ซึ่งรับประกันเส้นทางที่เหมาะสมที่สุด สร้างเส้นทางขึ้นใหม่โดยการย้อนรอยตัวชี้พาเรนต์

ข้อผิดพลาดที่พบบ่อย

  • การใช้ฮิวริสติกที่ไม่สามารถยอมรับได้ซึ่งประเมินต้นทุนสูงเกินไป นำไปสู่เส้นทางที่ไม่เหมาะสมที่สุด
  • การเลือกฮิวริสติกที่ง่ายเกินไปหรือไม่เกี่ยวข้องกับปัญหา ทำให้ประสิทธิภาพการค้นหาลดลง
  • การนำชุดเปิดไปใช้ที่ไม่มีประสิทธิภาพ (ควรใช้คิวลำดับความสำคัญ) ทำให้การเลือกโหนดช้า

คำถามที่พบบ่อย

ฮิวริสติกที่ยอมรับได้คืออะไร และทำไมจึงสำคัญ?

ฮิวริสติกที่ยอมรับได้จะไม่ประเมินต้นทุนจริงไปยังเป้าหมายสูงเกินไป คุณสมบัตินี้รับประกันว่า A* จะพบเส้นทางที่เหมาะสมที่สุด หากฮิวริสติกประเมินค่าสูงเกินไป A* อาจพลาดเส้นทางที่สั้นกว่าและส่งคืนคำตอบที่ไม่เหมาะสมที่สุด

คุณจะออกแบบฮิวริสติกที่ดีสำหรับปัญหาได้อย่างไร?

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

ความแตกต่างระหว่าง A* และขั้นตอนวิธีของ Dijkstra คืออะไร?

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

A* สามารถรับประกันการค้นหาเส้นทางที่สั้นที่สุดได้หรือไม่?

ได้ A* รับประกันเส้นทางที่สั้นที่สุดเมื่อฮิวริสติกสามารถยอมรับได้ (ไม่ประเมินต้นทุนจริงสูงเกินไป) ด้วยฮิวริสติกที่ไม่สามารถยอมรับได้ จะไม่รับประกันความเป็นที่สุด

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.

    ISBN: 978-0-13-604259-4
    คัดลอกแล้ว