Эвристика для проблемы с раздвижной плиткой

Question

Идея состоит в том, чтобы переместить все правые элементы влево и влево вправо с пустым пространством в середине. Элементы могут перепрыгивать через одну или две части в пустое пространство.

LLL[ ]RRR

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

Answer 1

Похоже, вы немного запутались в том, что такое эвристика.

Грубое определение - "упрощающее предположение" или "приличное предположение"

Например, допустим, вам нужно собрать баскетбольную команду, и у вас есть информационные бюллетени о людях, которые хотят сыграть в этом списке, их контактную информацию, дату рождения и рост. Вы могли бы провести испытания, где вы проверяете конкретные навыки каждого кандидата; это потребует привлечения всех кандидатов, и это может занять много времени. Вы используете эвристику для сужения поиска - звоните только людям ростом не менее 6'2 ". Это может игнорировать некоторых великих баскетболистов, но это довольно приличное предположение.

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

Эвристикой для вашей проблемы может быть «никогда не перемещать Ls вправо и никогда не перемещать Rs влево» - это сужает «пространство поиска» всех возможных ходов, исключая некоторые возможности с самого начала.

Answer 2

Вы ищете эвристику или алгоритм? Эвристика может или не может решить данную проблему. На самом деле он просто предназначен для того, чтобы указать вам направление, в котором, вероятно, находится решение. Алгоритм действительно должен решить данную проблему.

Answer 3

Эвристика - это, как правило, «подсказка», которая обычно (но не всегда) направляет вашу процедуру в правильном направлении. Использование эвристики ускоряет ваши процедуры (ваши алгоритмы), опять же, обычно , но не всегда. Это как «совет» алгоритму, который чаще всего верен, чем нет.

Я не уверен, что вы ищете, так как описание немного расплывчато. Если вам нужен алгоритм, вам нужно изучить, какое влияние окажет конкретный ход на текущую ситуацию, и как каждый раз шагать вперед для всех возможных ходов, фактически проходя через дерево состояний (т. Е. Состояний, которые будут развиваться, если Вы делаете определенную последовательность ходов).

Вы также можете видеть, что, возможно, имеет значение как близко текущая позиция к тому, чего вы хотите достичь (желаемая конечная позиция). Так что вместо вычисления всех возможных путей от вашего начального состояния до находя конечное состояние, вы можете руководствоваться своим алгоритмом на основе эвристики «насколько близко текущее состояние к желаемому» и проходить только часть дерева.