Меня попросили изучить улучшения алгоритма Дейкстры. Я изучал алгоритм A Star, но обнаружил, что во многих объяснениях используются незнакомые слова и математические обозначения.
Я понимаю, что A Star рассматривает только ребра, направленные к целевому узлу. Например, если бы алгоритм A Star применялся к дорожной сети Великобритании, пунктом назначения был Данди, а я начал с Лондона, то будут проверены только края, ведущие на север.
Это хоть как-то правильно?
A* использует эвристику, чтобы угадать минимальную стоимость узла для цели. Поэтому при выборе узла вы анализируете не только стоимость от начала до этого узла, но и вероятную стоимость от узла до цели. Это позволяет игнорировать пути, которые, вероятно, ведут в неправильном направлении.
Если эвристика в вашем примере использует географическое расстояние узлов, то дороги, ведущие на север, будут проверены в первую очередь (поскольку они имеют небольшую предполагаемую общую стоимость). Но возможно, что во время выполнения алгоритма эти дороги аккумулируются на очень большом фактическом расстоянии от начала (может быть, из-за большого количества кривых). Затем также можно осмотреть дороги, ведущие на юг. Так что можно немного съездить на юг и прямо на север, если это короче всех извилистых дорог, ведущих на север (не принимая во внимание реальную дорожную карту Великобритании).
Характер эвристики определяет качество алгоритма. Если эвристика дает нижнюю границу расстояния (т. е. невозможно добраться до цели с меньшими затратами, чем говорит эвристика), то путь действительно является кратчайшим путем. Если эвристика не является нижней границей, могут быть разрешены и другие пути (что может быть компромиссом между временем выполнения алгоритма и качеством пути). Чем лучше эвристика оценивает минимальную стоимость, тем меньше неправильных направлений вы будете исследовать. т.е. если эвристика постоянна, вы получите простой алгоритм Дейкстры. Если эвристика вычисляет фактическую стоимость цели, вы будете следовать только кратчайшему пути, и никакие другие узлы не будут проверяться.
