Эвристическая функция для применения судоку A *

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

например, это входная сетка:

введите описание изображения здесь

и теперь мы должны заполнить ячейку (1,2).

Все узлы представляют собой разные сетки, которые представляют разные состояния. Фактор ветвления равен 4, поэтому у нас есть 4 возможности для следующей ячейки: 1, 2, 3 или 4, то есть 4 дочерних элемента для каждого узла.

Как я могу определить эвристическую функцию на узлах для применения A * на сетке?

Все, о чем я могу думать, это:

если новое число, которое было вставлено в сетку текущего состояния, является недопустимым (= появляется более одного раза в одной строке, столбце или поле), поэтому h (n) = бесконечность.

else, h(n)= [number of empty remain cells].

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


artificial-intelligence algorithm heuristics
person daniel    schedule 16.03.2016    source источник
comment
моя плохая .. это слева направо. 2-я ячейка 1-го ряда   -  person daniel    schedule 16.03.2016
comment
A * не является подходящим выбором алгоритма для этой проблемы.   -  person David Eisenstat    schedule 16.03.2016
comment
да, я думаю, ты прав, но это не мне решать   -  person daniel    schedule 16.03.2016

Ответы (2)


arrow_upward
3
arrow_downward

Одна из эвристических функций - выбрать ячейку с максимальным количеством ограничений.

Например. в вашем примере вы можете выбрать (2,3) =>, поскольку у него есть только одна возможность (максимальное количество ограничений). После того, как вы сделали «ставку» (разместили число), вы можете продолжить с той же стратегией => поставить S[2,3] = 2 => выбрать S[2,2] и так далее.

Под ограничениями я имею в виду, сколько вариантов у вас есть на ячейку, учитывая ограничения в правилах судоку.

h [ячейка] = 1 / (# вариантов на блок + # вариантов на строку + # вариантов на столбец)

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

h2 [ячейка] = h [ячейка-левая] + h [ячейка-правая] + ...;

person Tamas Ionut    schedule 16.03.2016
comment
Мне не нужна эвристическая функция для выбора следующей ячейки для обработки. По определению, я должен заполнять пустые ячейки слева направо и сверху вниз. Вот почему мне нужна эвристическая функция для определения того, какое число вставить (1,2, 3, 4?), А не какую ячейку обрабатывать ... В любом случае спасибо! - person daniel; 16.03.2016

arrow_upward
0
arrow_downward

Как отмечено в одном из комментариев, A * не подходит для такой игры, как судоку, поскольку, учитывая правила судоку, у вас есть только одно возможное решение. Значок * (с открытым списком) позволяет найти оптимальное решение с учетом эвристики допустимой, которая сообщает предполагаемую стоимость состоянию цели и меньше или равна фактической стоимости. Нет смысла совершать противоправные действия. От них можно отказаться, определив правильные действия для данного состояния.

Единственная формулировка поиска, которая может иметь смысл для судоку с A *, - это вложение стоимости поиска решения, и, таким образом, эвристика будет отражать оценочную стоимость поиска. В таком случае порядок заполнения ячеек имеет значение.

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

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

Дополнительные сведения об информированном поиске и эвристике см. В главе 3 документа Искусственный интеллект: современный подход автора Рассел и Норвиг.

person albertoql    schedule 20.03.2016