Эвристика для задачи раздвижной плитки

Question

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

LLL[ ]RRR

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

Answer 1

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

Грубое определение — это «упрощающее предположение» или «достойное предположение».

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

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

Эвристика для вашей проблемы может быть такой: «никогда не перемещайте L вправо и никогда не перемещайте R влево» — она сужает «пространство поиска» всех возможных ходов, устраняя некоторые возможности с самого начала.

Answer 2

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

Answer 3

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

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

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