Найдите хороший heuristi c для следующей задачи (A *)

Question

Я пытаюсь найти функцию heuristi c для решения следующей проблемы. Вам дается n ведер краски с максимальной емкостью max_i, текущей емкостью curr_i и цветом краски colour_i, i = 1, n и списком o возможных комбинаций цветов: col1 + col2 -> col3. Конечным состоянием проблемы является набор пар (количество, цвет), которые должны быть найдены в контейнерах # (final_state) <= no. of buckets. </p>

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

Проблема в том, что я не могу придумать класс c heuristi c, чтобы соответствовать этой задаче поскольку я не могу сравнить сегменты из начального состояния с сегментами из конечного состояния (это не уникально). Должны ли heuristi c быть числами переходов от текущего состояния к окончательному или это может быть какое-то число, которое уменьшается по мере приближения к области?

Answer 1

Значение heuristi c должно быть допустимым , поэтому не следует недооценивать фактическое расстояние. Когда вы приближаетесь к цели, она в принципе должна быть более точной и, следовательно, может внезапно уменьшаться быстрее. Но это прекрасно, если не стоит недооценивать.

Поскольку расстояние до цели - это, как правило, количество ходов, трудно понять, как это может быть чем-то совершенно не связанным. Так что да, heuristi c должно быть связано с количеством ходов, но не обязательно, если это пессимистический c, а не оптимистический c.