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

h ( x ) ≤ d ( x , y ) + h ( y ) {\displaystyle h(x)\leq d(x,y)+h(y)}

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

L ( X ) + h ( x ) ≤ L ( X ) + d ( x , y ) + h ( y ) = L ( Y ) + h ( y ) {\displaystyle L(X)+h(x)\leq L(X)+d(x,y)+h(y)=L(Y)+h(y)}

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

h ( f ) ≤ d ( f , v 1 ) + h ( v 1 ) ≤ d ( f , v 1 ) + d ( v 1 , v 2 ) + h ( v 2 ) ≤ … ≤ L ( P ) + h ( g ) = L ( P ) {\displaystyle 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 {\displaystyle h} ใดๆ ดังนั้นจะไม่มีขั้นตอนวิธีใดที่ใช้ฮิวริสติกแบบเดียวกันแล้วใช้จำนวนโหนดในการพิจารณาน้อยกว่าเอสตาร์ ยกเว้นในกรณีที่มีหลายคำตอบซึ่ง h {\displaystyle h} จะประมาณค่าของเส้นทางที่ดีที่สุด ซึ่งแม้จะมีกรณีดังกล่าวเกิดขึ้นในแต่ละกราฟ ก็อาจมีลำดับของตัวเลือกในแถวคอยบุพริมภาพที่เอสตาร์จะนำมาใช้เพื่อพิจารณาโหนดจำนวนน้อยที่สุดที่เป็นไปได้

กรณีพิเศษ

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

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

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

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