אתה מכיר את Dijkstra?
כי אם כן, אז זה אלגוריתם Dijkstra משופץ. יש לך גרף, ובגרף הזה יש מספר צמתים שנקראים "צמתי מטרה". המטרה של האלגוריתם היא למצוא את המסלול הקצר ביותר מצומת מקור כלשהו לאחד מצמתי המטרה. יש לך פונקציה f שמתאימה לכל צומת v מספר ממשי שתפקידו להעריך את אורך המסלול הקצר ביותר מ-v עד למטרה הכי קרובה אליו (כמה שהמספר שהיא מחזירה יותר קטן כך הפונקציה מעריכה שהוא קרוב יותר לאחת המטרות). בנוסף, כמו ב-Dijstra, לכל צומת אתה שומר את אורך המסלול הקצר ביותר שנמצא עד עכשיו. נקרא לערך הזה g. אז האלגוריתם פועל בדיוק כמו Dijkstra, רק שלכל צומת לפני שהוא מכניס אותו לתור העדיפויות הוא מחשב את הערך f, ובנוסף תור העדיפויות ממויין לפי הערך f+g. יש משפט שאומר שאם הפונקציה f תמיד "אופטימית" (כלומר אף פעם לא מעריכה יותר ממה שבאמת נשאר. ז"א לא עושה OverEstimation) אז המסלול ש-A* ימצא הוא באמת המסלול הקצר ביותר.
