Уважаемые пользователи Голос!
Сайт доступен в режиме «чтение» до сентября 2020 года. Операции с токенами Golos, Cyber можно проводить, используя альтернативные клиенты или через эксплорер Cyberway. Подробности здесь: https://golos.io/@goloscore/operacii-s-tokenami-golos-cyber-1594822432061
С уважением, команда “Голос”
GOLOS
RU
EN
UA
habreplicator
6 лет назад

Решение задачи замощения с помощью SAT солвера на примере пентамино

Автор: andy_p
Источник: https://geektimes.ru/post/295575/
Однажды попалась мне игра пентамино, где было необходимо уложить 13 фигурок в квадрат 8 на 8. После некоторого периода времени, втечение которого я безуспешно пытался решить эту задачу, я решил, что необходимо написать программу, которая бы делала это за меня. Для этого необходимо было выбрать алгоритм решения. Первое, что приходит на ум — это обычный алгоритм ветвей и границ, когда фигурки укладываются одна за другой примыкая друг к другу (алгоритм с танцующими ссылками здесь не подходит, поскольку фигурки разные). Для ускорения этого алгоритма обычно используются различные эвристики, например, предпочтение отдается ветвлению с наименьшим количеством вариантов. Можно придумать и реализовать и другие эвристики в этом алгоритме, но тут я подумал, что множество различных ухищрений для ускорения решения подобных задач уже реализовано в SAT солверах. Поэтому, необходимо перевести задачу на соответствующий математический язык и воспользоваться каким-либа SAT солвером. О том, как это было реализовано и какие получились результаты можно почитать под катом.
Читать дальше →
0
0.000 GOLOS
На Golos с April 2017
Комментарии (0)
Сортировать по:
Сначала старые