Почему допущение движения по диагонали сделало бы неприемлемыми А* и Манхэттенское расстояние?

Во многом, как указывает комментарий стакана, Манхэттенское расстояние будет переоценивать расстояние между состоянием и состояниями, доступными для него по диагонали. По определению, эвристика, переоценивающая расстояния, недопустима.

Теперь, почему именно это так?

Предположим, что ваша процедура Manhattan Distance выглядит примерно так:

function manhattan_dist(state): 
    y_dist = abs(state.y - goal.y)
    x_dist = abs(state.x - goal.x)
    return (y_dist + x_dist)

Теперь рассмотрим случай применения этой процедуры к состоянию (1,1) и предположим, что целью является состояние (3,3). Это вернет значение 4, которое переоценивает фактическое расстояние, равное 2. Следовательно, манхэттенское расстояние в этой ситуации не будет работать как допустимая эвристика.

На игровых полях, которые позволяют двигаться по диагонали, вместо этого обычно используется Расстояние Чебышева. Почему?

Рассмотрим эту новую процедуру:

function chebyshev dist(state): 
    y_dist = abs(state.y - goal.y)
    x_dist = abs(state.x - goal.x)
    return max(y_dist, x_dist)

Возвращаясь к предыдущему примеру (1,1) и (3,3), эта процедура вернет значение 2, которое действительно не является завышенной оценкой фактического расстояния.

Хотя эта тема старше, я хотел бы добавить другое решение, которое использует самый быстрый свободный путь к цели, если разрешено диагональное движение.

function heuristic(state):
    delta_x = abs(state.x - goal.x)
    delta_y = abs(state.y - goal.y)
    return min(delta_x, delta_y) * sqrt(2) + abs(delta_x - delta_y)

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