|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Kostya Sudilovsky 2:452/64.4 11 Aug 2001 00:01:02
To : Andrey Dashkovsky
Subject : Sokoban (логическая игра)
--------------------------------------------------------------------------------
Я заметил, что в Понедельник Август 06 2001, Andrey Dashkovsky писал:
VG>> Существует ли алгоритм прохождения лабиринтов игры Sokoban?
AD> Для 1 ящика и поля nxn делали виртуальным графом,
Ого! Это что за алгоритм? Чем делали?! Дейкстрой, очередью?
AD> получается ящик может находиться в одном из n^2 положения+сам
AD> двигающий в одном из n^2 положений,
А вот и нет!!! Для человека достаточно m*4 положений, где m - кол-во ящиков, и
то, это - максимум. Hапример:
ШШШШШШШШШ ШШ - стена, ЯЯ - ящик, 1,2,3 - положения бедного роботяги
ШШШ 2ШШШШ положение 4 здесь никогда не достигается, а 1=3
Ш 1ЯЯ3 ШШ
Ш ШШ ШШ
Ш ШШ
ШШШШШШШШШ
AD> Другого алгоритма для этой задачи наша бригада в своё
AD> время не придумала, да я сомневаюсь есть ли он.
Плохо думали! Здесь еще кучу всякого можно придумать - например все тупики
залить стенками, чтобы туда ящики не затаскивать.
AD> Разве что можно сюда приплести динамическое программирование.
Так это же оно, по-сути, и есть!
Digitally yours, Sudilovsky Kostya.
--- GoldED+/W32 1.1.4.5
* Origin: Gomel State Univesity (2:452/64.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Sokoban (логическая игра) 