Решение логической игры Lights out с помощью алгоритма A *

Question

У меня возникли проблемы с решением логической головоломки Lights out с использованием алгоритма A *.Сейчас я использую реализацию алгоритма A *, где я рассматриваю всю матрицу источников света как узел в алгоритме (где 1 представляет включенные источники света, а 0 - выключенные источники света) вместе с координатами текущего узла.это будет переключено.После того, как я выберу узел из открытого списка с наименьшим значением f, я переключу его и получу его 8 соседних соседей, а затем добавлю их в открытый список и повторяю, пока не найду узел, у которого сумма всех источников света равна0 (все источники света выключены).

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

Я знаю, что алгоритм будет не таким производительным, даже если сравнивать с методом "Chasing the Lights", но я не понимаю, как указать алгоритму, какой узел выбрать, поэтому какую функцию подсчета f использовать, потому что рассмотрение суммы источников света в матрице приведет к тому, что алгоритм будет проходить через одни и те же 3/4 узла каждый раз.

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

Язык, на котором я реализовал всю работу - это Lua.

Спасибо.

EDIT от 27.05.19 Так как я новичок в Lua, я обвиняю свои ошибки и свои способностинаписание кода в нем, а также мое понимание алгоритма на тот факт, что я не могу найти решение.Я не очень хорошо объяснил проблему, с которой столкнулся, поэтому я попытался извлечь максимум пользы из полученных комментариев, и теперь я опубликую измененный код, чтобы ребята, если вы хотите помочь, лучше понимали (code >> wordsхаха).

Примечание: я написал алгоритм, основанный на этой статье A * алгоритм

lua исходный код

Answer 1

Не уверен, что вы ищете.

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

Вы можете пойти с очень плохим подходом и создать 2 ^ n игровых состояний (узлов на вашем графике), где n - количество полей на игровой доске. Почему это ужасно? Для создания графика вам понадобится как минимум O (2 ^ n) времени и пространства. За O (2 ^ n) времени вы можете просто проверить все возможные ходы (поскольку вы хотите переключать каждую доску по одному разу) и просто без промедления сообщить результат вместо запуска дополнительной A *.

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

Как я уже сказал, вы можете представить состояние игры в виде битовой маски размера n - 0 на i-й позиции, если i-тое поле не было переключено, 1 в противном случае.

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