IPB
ЛогинПароль:

> поиск пути для кубика, в матрице nxn
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной).
В самом начале пути эта запрещенная сторона находится сверху.

Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю!

Может, существует общий алгоритм нахождения этого пути?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Решение "в лоб" - катать по всякому кубик рекурсивной процедурой, исключая поворот на запрещенную сторону, попутно считая количество посещенных клеток (для определения в клетке (1, n) найдено решение или нет).


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(xds @ 24.11.2007 18:33) *

Решение "в лоб" - катать по всякому кубик рекурсивной процедурой

Да, я думала над этим. Но, по-моему, это будет выполняться долго. Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным?
И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение?

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Тёмный Эльф @ 24.11.2007 18:41) *
Да, я думала над этим. Но, по-моему, это будет выполняться долго.
А что означает "долго" в этом контексте?.. Минуты, часы, дни, годы?..

Цитата(Тёмный Эльф @ 24.11.2007 18:41) *
Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным?
Это можно почти всегда в простых случаях. Но почему ты отказываешься от рекурсии, даже не попробовав? Рекурсия обычно реализуется на порядок проще - так может, начать все же с нее?.. Если уж говорить об оптимальности, то не следует ли оптимизировать ВСЕ, в том числе и затраты собственного времени? smile.gif И вообще, об оптимизации можно говорить только тогда, когда уже что-то есть.

Цитата(Тёмный Эльф @ 24.11.2007 18:41) *
И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение?
Никакому, надо исследовать оба. В этом и есть смысл полного перебора (в виде рекурсии или нет).

Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Тёмный Эльф   поиск пути для кубика   24.11.2007 21:45
xds   Решение "в лоб" - катать по всякому куби…   24.11.2007 22:33
Тёмный Эльф   Решение "в лоб" - катать по всякому куб…   24.11.2007 22:41
Lapp   Да, я думала над этим. Но, по-моему, это будет вып…   25.11.2007 17:49
hardcase   Решение "в лоб" - катать по всякому куб…   25.11.2007 18:35
Lapp   Только сейчас обратил внимание, что тема абсолютно…   25.11.2007 18:23
xds   Для n > 9 уже довольно долго. Добавлено через …   25.11.2007 19:21
hardcase   Написал программу. Правда, на С# (паскаля нету на …   25.11.2007 21:09
xds   Для 8x8 и 9x9 тоже. 10x10 лень дожидаться :)   25.11.2007 21:41
Тёмный Эльф   :yes2: дольше чем полчаса.. (здесь то и встает в…   25.11.2007 23:21
Lapp   думается мне, что задача при n>3 не имеет решен…   26.11.2007 9:19
xds   AMD Duron @ 800 MHz: n = 8 - 1,43 с; n = 9 - 18,84…   26.11.2007 11:58
hardcase   Ставлю свою софтину (C# .NET 2.0, без распараллели…   26.11.2007 17:25
Lapp   После чистки очевидных несуразностей на компе Athl…   26.11.2007 19:50
feniks25   А можно исходники посмотреть. Уж больно интересно-…   26.11.2007 20:17
hardcase   А можно исходники посмотреть. Уж больно интересно…   26.11.2007 23:09
xds   После чистки очевидных несуразностей на компе Ath…   26.11.2007 21:01
hardcase   Как то даже незаметно закончился расчет "в ло…   27.11.2007 1:18
Тёмный Эльф   Времени ушло 7ч 25м. Вот это да-а-а :mega_chok: З…   27.11.2007 1:29
hardcase   Судя по ответам xds'а, его программа справится…   27.11.2007 1:47
Тёмный Эльф   Программа, откомпилированная на Microsoft Visual S…   27.11.2007 2:39
hardcase   Программа, откомпилированная на Microsoft Visual …   27.11.2007 3:11
Тёмный Эльф   Это какая такая программа?? Это программа xds. В…   27.11.2007 3:35
xds   Вот мой оригинальный вариант (BP 7.0), только доба…   27.11.2007 11:00
spill   Есть поиск в ширину: 1. Первую клетку пометить чис…   14.03.2008 17:44


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:33
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name