Tetravex решая алгоритм
Ну, я думал о создании программы решения Tetravex для осуществления моих навыков письма кода (язык propably будет Visual Basic), и я нуждаюсь в помощи, находя алгоритм для решения его. Для тех, которые не знают то, что tetravex, см. этот http://en.wikipedia.org/wiki/TetraVex. Единственный алгоритм, который я могу придумать, является грубой силой путь, поместите мозаику случайным образом в один угол и попробуйте каждую возможную мозаику рядом с нею и продолжите тот же процесс, если она достигает, тупик возвращаются к предыдущему состоянию и помещают другую мозаику. Таким образом, кто-либо может придумать лучший алгоритм? Спасибо за Ваше время.
4 ответа
вот несколько идей.
Обычный алгоритм грубой силы будет пытаться рекурсивно заполнить сетку, перечисляя позиции сетки в фиксированном порядке (например, в основной строке) и всегда пытаясь уместить все возможные части в текущую позицию, а затем рекурсивно. Это то, что вы упомянули, и это очень неэффективно.
Улучшение состоит в том, чтобы всегда подсчитывать для каждой свободной позиции количество элементов, которые в нее помещаются, а затем возвращаться к позиции, которая имеет наименьшее соответствие ; если у кого-то нет подходящих деталей, немедленно возвращайтесь; если есть один, в который подходит только одна деталь, заполните его и продолжайте (ветка не создается); в противном случае выберите тот, у которого меньше всего подходящих частей (≥ 2), и продолжайте оттуда.
Когда у вас есть этот алгоритм, возникает следующий вопрос: как можно еще больше сократить пространство поиска. Если у вас есть, скажем, фигуры A с "1" в верхней позиции и B фигур с "1" в нижней позиции, а A> B, то вы знаете, что по крайней мере A - B фигур "1 в верхней позиции" должны быть фактически размещены в верхнем ряду, поэтому вы можете исключить их из любой другой позиции. Это помогает снизить фактор ветвления и раньше выявлять тупики.
Вы также должны проверять на каждом шаге рекурсии, что каждая деталь имеет хотя бы одно место, где она подходит (сделайте эту проверку после того, как убедитесь, что нет никакой детали, которая умещалась бы только в одном месте для скорости). Если есть кусок, который никуда не помещается, вам нужно немедленно отступить.Вы можете расширить это до проверки того, что каждая пара частей подходит для потенциально лучшей возможности ранней проверки мертвой блокировки.
Существует также стратегия, называемая «не хронологический возврат» или «обратный переход», которая берет свое начало в исследованиях решения SAT. Это поможет вам вернуться более чем на один уровень за раз, когда вы зайдете в тупик; если хотите, вы можете найти в Google эти термины, чтобы найти больше, но вам нужно проделать некоторую умственную работу, чтобы сопоставить концепцию с вашим проблемным пространством.
A first improvement would be counting how many matching pairs of numbers there are, and if, say, there are 5 "1"'s on the top of squares, but only 4 on the bottom, then there must be a "1" pointing off the top of the grid.
На любой данной частично решенной доске я бы
искал место, где нельзя было бы сыграть ни одну из оставшихся плиток. В случае обнаружения доску необходимо размотать до последнего места, на котором случайным образом разыграли плитку.
Найдите место, где разрешено играть только 1 из оставшихся плиток. Если найдете, поместите эту плитку.
Разместите тайл в случайном порядке в том месте на доске, где можно легально разыграть наименьшее количество оставшихся тайлов. Помните эту раскладку доски до Я кладу плитку, я могу вернуться к этой доске и сыграть другую плитку.
В псевдокоде это будет
top:
evaluate # of tiles that match at each empty square
if any square has 0 matches, unwind to <prev>
if any square has 1 match, lay tile, goto top
save current board as <prev>
play randomly at square with minimum number of matches, goto top
В качестве оптимизации вы можете игнорировать оценку квадратов, которые не касаются квадратов с плитками, поскольку они всегда разрешают все оставшиеся плитки.
Похоже, что Tetravex - это Constraint Satisfaction Problem, поэтому нужно как можно быстрее ограничить возможности. Это должно быть возможно лучше, чем случайное расположение. Как насчет?:
- Создайте связи между всеми гранями плиток с их возможным совпадением.
- Любая плитка с несвязанной поверхностью должна быть плиткой по краям.
- Любая плитка с двумя смежными несвязанными сторонами должна быть угловой плиткой.
- Центральная плитка должна иметь четыре активных звена.
- Теперь поместите плитку в правильное место и признайте недействительными используемые ссылки. Если какая-либо незакрепленная плитка содержит три несвязанные или несвязанные стороны на противоположных сторонах, перемещение будет недопустимым, и вы сможете выполнить обратное движение.
- Вы должны иметь возможность использовать ссылки на лица плиток для поиска следующей возможной плитки по сравнению с поиском по всем плиткам. Если их нет, отступайте.