|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 06 Aug 2001 23:19:30
To : Vadim Guchenko
Subject : Re: Sokoban (логическая игра)
--------------------------------------------------------------------------------
06 Авг 01 20:47, you wrote to all:
VG> Существует ли алгоритм прохождения лабиринтов игры Sokoban? Если кто
VG> не знает, там грузчик толкает ящики. Их нужно поставить на
VG> определенные места. Кто-нибудь занимался написанием солвера?
Для 1 ящика и поля nxn делали виртуальным графом,
получается ящик может находиться в одном из n^2 положения+сам двигающий в одном
из n^2 положений, итого n^4 - вершин, для 2 ящиков - n^6 вершин. Другого
алгоритма для этой задачи наша бригада в своё время не придумала, да я
сомневаюсь есть ли он. Разве что можно сюда приплести динамическое
программирование.
Andrey
... ... Объявление в газете: "Тpахаю, тибидохаю. Стаpик Хоттабыч."...
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
