Почему путь между двумя углами прямоугольника выглядит странно?

Question

Я написал небольшую программу для поиска кратчайшего пути между двумя точками, используя A * алгоритм .

Я сделал каждый 10-й пиксель в прямоугольнике узлом (ширина: 100 узлов, высота: 50 узлов) и соединил его с четырьмя узлами, расположенными вокруг него (сверху, слева, снизу, справа).Программа должна была найти самый быстрый путь от верхнего левого угла до нижнего правого угла.Вот как выглядел результат:

Сначала я задавался вопросом, почему это на самом деле самый быстрый способ, но потом я подумал, что мне, вероятно, следует добавить диагональсоединения.Вот как это выглядело потом:

Потребовалось 100 узлов, чтобы добраться до конца и ок.1193px.Это раздражало меня еще больше, и теперь я задаюсь вопросом, неверна ли моя программа или это самый короткий путь.

Как вы думаете?

Разве не быстрее идти по тому же пути, что и на первом рисунке, просто идти по диагонали в конце?

Answer 1

Без диагональных ходов самый быстрый путь занял бы (width-1)+(height-1) ходов, чтобы достичь конца.но с диагоналями было бы меньше нет.ходов, но мы можем сделать только min(width-1,height-1) диагональных ходов, а остальные ходы должны быть недиагональными (в данном случае вправо).Таким образом, обе картинки действительно показывают кратчайший путь, который кажется правильным вашему коду.