Какие допустимые эвристики и почему?

Question

На сетке n x n есть n автомобилей. В начале они упорядочены в верхнем ряду 1. Транспортные средства должны попасть в нижний ряд, так что транспортное средство в точке (1,n) должно добраться до (n, n - i + 1). На каждом временном шаге каждое из транспортных средств может двигаться на одну клетку вверх, вниз, влево или вправо или оставаться на месте. Если транспортное средство остается на месте, одно соседнее транспортное средство (но не более одного) может перепрыгнуть через него. Два транспортных средства не могут занимать одну и ту же площадь. Какие из следующих эвристик допустимы для задачи перемещения всех транспортных средств к месту назначения?

я. сумма от 1 до n (h1... hn)

II. max (h1... hn)

III. мин (ч1... чн)

Я думаю, что iii является единственно правильным, но я не уверен, как сформулировать свои соображения о том, почему.

Answer 1

Я уверен, что кто-то придет с очень подробным ответом, но в качестве одолжения для тех, кто, как я, может быть немного перегружен ИИ, допустимая эвристика довольно проста:

Эвристика, которая никогда не переоценивает истинную стоимость достижения цели

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

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