การค้นหาแบบเอสตาร์

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีเอสตาร์ (อังกฤษ: A* algorithm) เป็นขั้นตอนวิธีที่ใช้ในการหาเส้นทางและการท่องในกราฟซึ่งเป็นกระบวนการในการหาเส้นทางระหว่างจุด (เรียกจุดดังกล่าวว่า "โนด" (node)) ขั้นตอนวิธีนี้มีประสิทธิภาพและความแม่นยำสูงจึงมีการนำไปใช้งานอย่างแพร่หลาย ผู้นิยามขั้นตอนวิธีนี้คือ ปีเตอร์ ฮาท์, นิล นีลสัน และเบิร์ดแรม เรฟเซด ซึ่งนิยามไว้ในปี ค.ศ. 1968 ขั้นตอนวิธีนี้เป็นส่วนขยายของขั้นตอนวิธีของไดค์สตราซึ่งสร้างในค.ศ. 1959 เอสตาร์มีประสิทธิภาพที่ดีกว่า (โดยขึ้นกับเวลา) จากการนำเทคนิคฮิวริสติกมาใช้ แต่ถ้าฮิวริสติกเป็นแบบโมโนโทนจะทำให้ความเร็วในการทำงานเท่ากับขั้นตอนวิธีของไดค์สตรา

นิยาม

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

• ค่าระยะทางทางจากโหนดเริ่มต้นมายังโหนดปัจจุบัน (ใช้สัญลักษณ์ $g(x)$)
• ค่าประมาณฮิวริสติกที่ยอมรับได้ ของระยะทางที่จะถึงจุดหมาย(ใช้สัญลักษณ์ $h(x)$)

ซึ่งฟังก์ชัน $h(x)$ ที่เป็นส่วนหนึ่งของ $f(x)$ จะต้องมีฮิวริสติกที่ยอมรับได้ กล่าวคือค่าประมาณฮิวริสติกยอมรับได้จะต้องไม่สูงกว่าระยะทางจากจุดเริ่มต้นไปยังจุดสิ้นสุด ตัวอย่างเช่นในการจัดเส้นทางซึ่งมีทั้งเส้นทางที่เป็นเส้นตรงและเส้นโค้ง $h(x)$ อาจแทนด้วยเส้นตรงจากจุดเริ่มต้นไปยังจุดสิ้นสุด ซึ่งหากวัดทางกายภาพแล้ว เส้นตรงที่เชื่อมจุดสองจุดจะมีระยะทางน้อยที่สุดในบรรดาเส้นเชื่อมทั้งหมดที่เชื่อมระหว่างจุดเริ่มต้นไปยังจุดสิ้นสุด

ถ้าฮิวริสติกของ h สอดคล้องกับเงื่อนไข $h(x)\leq d(x,y)+h(y)$ สำหรับทุกเส้นเชื่อม x,y ในกราฟ (เมื่อ d หมายถึงความยาวของเส้น) จะเรียก h ว่าเป็นฮิวริสติกชนิดโมโนโทน หรือฮิวริสติดแบบเสถียร ซึ่งในกรณีดังกล่าวเอสตาร์สามารถมีประสิทธิภาพสูงเทียบเท่าได้กับการใช้ขั้นตอนวิธีของเดสสตาร์แบบปรับแต่งให้ $d'(x,y):=d(x,y)-h(x)+h(y)$ ซึ่งไม่มีโหนดใด ๆ จะต้องถูกดำเนินการมากกว่าหนึ่งครั้ง นอกจากนี้เอสตาร์ยังสามารถปรับปรุงเป็นรูปทั่วไปของการค้นหาแบบสองทิศทางได้อีกด้วย

ประวัติ

นิลส์ นิลสัน สร้างวิธีที่ใช้ฮิวริสติก มาเพิ่มความเร็วของขั้นตอนวิธีของไดค์สตราในปี ค.ศ. 1964 และเรียกขั้นตอนวิธีนี้ว่า A1 ต่อมาในปี ค.ศ. 1967 เบิร์ดแรม เรมเซสปรับปรุงขั้นตอนวิธีตัวนี้เพิ่มเติม แต่ไม่สามารถพิสูจน์ถึงความเร็วที่เพิ่มนี้ได้ เขาเรียกขั้นตอนวิธีนี้ว่า A2 ในปี ค.ศ. 1968 ปีเตอร์ อี ฮาร์ทแสดงการพิสูจน์ว่า A2 เป็นขั้นตอนวิธีที่เร็วขึ้นได้ และการพิสูจน์ของเขาได้แสดงอีกด้วยว่าขั้นตอนวิธี A2 เป็นขั้นตอนวิธีที่ดีที่สุดในเงื่อนไขที่กำหนด เขาจึงใส่คลีนสตาร์ (*) หลังตัว A เพื่อตั้งชื่ออัลกอรึทึมตัวนี้ซึ่งหมายถึง A และทุกรูปแบบของ A

หลักการ

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

กระบวนการ

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

เช่นเดียวกับขั้นตอนวิธีการหาแบบมีข้อมูลประเภทอื่น ๆ เอสตาร์จะเริ่มจากหาเส้นทางที่น่าจะไปถึงจุดหมายมากที่สุดก่อน นอกจากเซตเอสตาร์จะเป็นส่วนนึงของขั้นตอนวิธีแบบละโมบเชิงการค้นหาแนวกว้างแล้ว เซตเอสตาร์ยังจะเก็บค่าระยะทางที่ไปมาแล้ว โดย $g(x)$ จะเป็นส่วนของฮิวริสติกที่เก็บค่าระยะทางจากจุดเริ่มต้น ไม่ใช่ค่าระยะทางจากโหนดที่ผ่านมาเท่านั้น

การทำงานของเอสตาร์จะเริ่มจากโหนดแรกสุด จากนั้นจะนำโหนดที่อยู่ในเซตเปิดที่ต้องท่องไปเข้าสู่แถวคอยลำดับความสำคัญ แถวคอยลำดับความสำคัญที่ใช้จะจัดอันดับความสำคัญให้โหนด $x$ ที่มีค่า $f(x)$ น้อยสุดมีความสำคัญมากกว่า ในแต่ละขั้นตอนของอัลกอรึทึมจะทำการดึงโหนด $x$ ที่มีค่า $f(x)$ ต่ำที่สุด และปรับค่า $f$ และ $h$ ของโหนดที่อยู่ติดกัน แล้วนำโหนดที่อยู่ติดกับโหนด $x$ นี้ใส่ในแถวคอย จากนั้นอัลกอรึทึมก็ทำกระบวนการนี้ต่อไปจนกระทั่งโหนดเป้าหมายมีค่า $f$ น้อยกว่าโหนดทุกโหนดในแถวคอย หรือหยุดเมื่อแถวคอยไม่มีข้อมูลอยู่แล้ว ซึ่งกระบวนการนี้อาจจะมีการพิจารณาโหนดเป้าหมายหลายครั้ง เช่น หากมีโหนดที่มีค่า f ต่ำกว่าโหนดที่ถูกดึงไปแล้ว เพื่อให้แน่ใจว่าเส้นทางที่เลือกจะเป็นเส้นทางที่สั้นที่สุด ค่าระยะทางที่สั้นที่สุดคือค่า $f$ ของจุดเป้าหมายโดย $h$ ของจุดเป้าหมายจะเป็นศูนย์ในฮิวริสติกที่ยอมรับได้ ถ้าต้องการหาจุดทั้งหมดที่ทำให้ได้ค่าเส้นทางที่สั้นที่สุดอัลกอรึทึมตัวนี้อาจจะเพิ่มให้โหนดจำโหนดก่อนหน้านี้ถัดขึ้นไป 1 โหนดของเส้นทางที่ดีที่สุดเท่าที่พบ และข้อมูลนี้ก็จะช่วยในการสร้างเส้นทางได้โดยการกระทำย้อนกลับจากจุดเป้าหมายไปยังจุดเริ่มต้น นอกจากนี้หากฮิวริสติกมีลักษณะโมโนโทน หรือเสถียร อาจใช้เซตปิดของโหนดที่ท่องไปแล้วเพื่อให้การค้นหามีประสิทธิภาพมากขึ้นก็ได้

รหัสเทียม

อัลกอรึทึมสามารถแสดงด้วยรหัสเทียมได้ดังนี้

 function A*(start,goal)
     closedset := the empty set    // เซตของโหนดที่พิจารณาแล้ว
     openset := {start}    // เซตของโหนดที่ยังไม่ได้พิจารณา เริ่มด้วยใส่โหนดเริ่มต้นลงไป
     came_from := the empty map    // เพื่อหาโหนดที่ผ่านมา ซึ่งจะใช้ในการระบุเส้นทาง

     g_score[start] := 0    // ค่าระยะทางของจุดเริ่มต้น
     h_score[start] := heuristic_cost_estimate(start, goal) // เป็นฟังก์ชันที่ใช้หาค่าประมาณฮิวริสติก
     f_score[start] := g_score[start] + h_score[start]    // ค่าประมาณการของจุดเริ่มไปยังจุดเป้าหมาย

     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from, came_from[goal])

         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset
                 tentative_is_better := true
             else if tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false

             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_cost_estimate(y, goal) //ประมาณหาค่าฮิวริสติกจากจุด y ไปถึงเป้าหมาย
                 f_score[y] := g_score[y] + h_score[y] //ปรับปรุงค่าการประมาณ

     return failure

 function reconstruct_path(came_from, current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from, came_from[current_node])
         return (p + current_node)
     else
         return current_node

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

ตัวอย่างการทำงานของขั้นตอนวิธี

ในตัวอย่างนี้สมมติให้โหนดแต่ละโหนดเป็นเมืองที่ต่อกับเมืองอื่นด้วยถนนและ h(x) เป็นเส้นตรงที่ระบุระยะทางไปยังจุดเป้าหมาย ตัวอย่างนี้ใช้ สีเขียวคือจุดเริ่มต้น สีฟ้าคือจุดเป้าหมาย สีส้มคือจุดที่ผ่านแล้ว และใช้สัญลักษณ์ ",” แสดงจุดทศนิยม

คุณสมบัติ

เช่นเดียวกับการค้นหาตามแนวกว้างก่อน เอสตาร์จะมีจุดสิ้นสุดและได้คำตอบเสมอ ถ้ามีคำตอบที่เป็นไปได้นั้น ในกรณีที่ฟังก์ชันฮิวริสติก $h$ เป็นฮิวริสติกยอมรับได้ ซึ่งจะไม่ประมาณค่าเกินไปกว่าค่าคำตอบที่ต่ำที่สุดจริงๆ ของเป้าหมาย เอสตาร์จะยอมรับได้เมื่อไม่ได้ใช้เซตปิด หรือถ้ามีการใช้เซตปิด คำตอบของ $h$ จะต้องเป็นแบบโมโนโทนิกจึงจะทำให้เอสตาร์จะเป็นคำตอบที่ยอมรับได้ ซึ่งการเป็นโมโนโทนิกนั้นหมายความว่าทุกๆ เส้นของโหนด $x$ และ $y$ ที่อยู่ติดกัน และ $d(x,y)$ หมายถึงความยาวของเส้นระหว่างโหนดทั้งสอง เราจะได้ว่า

$h(x)\leq d(x,y)+h(y)$

ทำให้สามารถพิสูจน์ได้ว่าทุกเส้นทาง $X$ จากโหนดเริ่มต้นไปยังโหนด $x$ เป็น

$L(X)+h(x)\leq L(X)+d(x,y)+h(y)=L(Y)+h(y)$

โดยที่ $L(\cdot )$ แสดงถึงความยาวของเส้นทาง และ$Y$ แสดงเส้นทางที่เกิดจากเส้นทาง $X$ รวมกับเส้นทางไปยัง $y$ ซึ่งจะไม่สามารถลดค่าของระยะทางสะสมได้โดยใส่โหนดที่อยู่ติดกันในเส้นทางนั้น ๆ (มีลักษณะคล้ายกับขั้นตอนวิธีของเดกสตาร์ที่มีข้อจำกัดว่าไม่สามารถจัดการกับเส้นที่ติดลบได้) รูปแบบโมโนโทนิกอาจถือได้ว่าเป็นรูปแบบที่ยอมรับได้เมื่อค่าประมาณฮิวริสติกที่ทุก ๆ โหนดเป้าหมายนั้นเองมีค่าเป็นศูนย์ ซึ่งแสดงได้โดยอสมการต่อไปนี้ เมื่อกำหนดให้ $P=(f,v_{1},v_{2},\ldots ,v_{n},g)$ เป็นเส้นทางที่สั้นที่สุดจากจุด $f$ ใด ๆ ไปยังจุดหมาย $g$

$h(f)\leq d(f,v_{1})+h(v_{1})\leq d(f,v_{1})+d(v_{1},v_{2})+h(v_{2})\leq \ldots \leq L(P)+h(g)=L(P)$

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

กรณีพิเศษ

เราสามารถมองขั้นตอนวิธีของเดกสตาร์ ซึ่งเป็นตัวอย่างหนึ่งของขั้นตอนวิธีค้นหาระยะทางแบบเอกรูป เป็นกรณีพิเศษของเอสตาร์โดยที่ $h(x)=0$ สำหรับทุก ๆ ค่า $x$ การค้นตามแนวกว้างก็สามารถประยุกต์จากเอสตาร์ได้เช่นกันโดยสร้างตัวนับ “C” ให้มีค่าเริ่มต้นที่ใหญ่มากๆ เมื่อทำการพิจารณาโหนดใดแล้วเราจะใส่ “C” ไปยังทุกโหนดที่อยู่ติดกัน ระหว่างที่กำลังใส่ “C” ให้กับโหนดจะต้องลดค่า “C” ทีละหนึ่งด้วย วิธีนี้ถ้ายิ่งหาโหนดพบเร็วเท่าใด ค่าของ $h(x)$ ก็จะยิ่งสูงขึ้นเท่านั้น อย่างไรก็ดีถ้าต้องการเพิ่มประสิทธิภาพของขั้นตอนวิธีของเดสสตาร์และการค้นตามแนวกว้าง ก็สามารถทำได้โดยไม่ใส่ค่า $h(x)$ ในแต่ละโหนด

การนำไปปรับใช้

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

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

การยอมรับได้และความเหมาะสม

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

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

ซึ่งข้อพิสูจน์ดังกล่าวจะเป็นจริงก็ต่อเมื่อเอสตาร์สอดคล้องกับเงื่อนไขต่อไปนี้

• เอสตาร์ใช้ฮิวริสติกที่ยอมรับได้ ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกเดียวกัน
• เอสตาร์แก้ปัญหาการค้นหาเพียงปัญหาเดียว ไม่ได้ใช้แก้ปัญหาการค้นหาที่คล้าย ๆ กันหลายปัญหา ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกที่มีส่วนเพิ่มขึ้นมา

ความซับซ้อนของขั้นตอนวิธี

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

$|h(x)-h^{*}(x)|=O(\log h^{*}(x))$

$h^{*}$ คือฮิวริสติกที่เป็นคำตอบซึ่งเป็นค่าจาก $x$ ไปถึงเป้าหมาย และค่าความผิดพลาดของ h จะโตช้ากว่าหรือเท่ากับค่าลอการิทึมของ ฮิวริสติกที่สมบูรณ์ $h^{*}$ ที่ซึ่ง $h^{*}$ จะเป็นค่าความยาวของ $x$ ถึงเป้าหมาย เปรียบเทียบระหว่าง ขั้นตอนวิธีของเดสตาร์กับขั้นตอนวิธีเอสตาร์

ขั้นตอนวิธีของเดสตาร์ใช้การประมาณฮิวริสติกเป็น 0 หรืออาจกล่าวได้ว่าไม่มีการประมาณเลย	ขั้นตอนวิธีเอสตาร์มีการประมาณฮิวริสติก

การนำไปใช้

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

ดูเพิ่ม

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

ดูเพิ่ม

• Breadth-first search
• Depth-first search
• Any-angle path planning

แหล่งข้อมูลอื่น

• อธิบายขั้นตอนวิธีเอสตาร์แบบง่าย เก็บถาวร 2005-12-24 ที่ เวย์แบ็กแมชชีน
• อธิบายขั้นตอนวิธีเอสตาร์เขียนด้วยภาษาจาวา
• อธิบายขั้นตอนวิธีเอสตาร์เขียนด้วยภาษาซีพลัสพลัส และ สอนขั้นตอนวิธีแบบเอสตาร์ เก็บถาวร 2012-11-03 ที่ เวย์แบ็กแมชชีน