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

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> поиск пути для кубика, в матрице 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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


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

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

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


Только сейчас обратил внимание, что тема абсолютно не на месте..
Цитата(Тёмный Эльф @ 24.11.2007 17:45) *

Привет! Подскажите пожалуйста с алгоритмом.

Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!

М
Переношу в Алгоритмы. И подозреваю, что скоро придется перенести в Задачи..



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


code warrior
****

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

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


Цитата(xds @ 24.11.2007 18:33) *
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой
Вполне согласен. Задача аналогична обходу шахматного поля конем. Как известно решение очень быстро находится.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


N337
****

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

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


Для n > 9 уже довольно долго.

Добавлено через 17 мин.
Кроме того, на время выполнения влияет порядок перебора - оно меньше, если в первую очередь делается попытка хода с поворотом плоскости "запрещенной" грани.


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


code warrior
****

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

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


Написал программу. Правда, на С# (паскаля нету на машине, но код неотличим от C-шного). Для размера поля 3х3 решение существует, для 6х6, для 7х7. Для размеров выше - не знаю.

З.Ы. багу исправлял =)) - вот и правил мессагу.

З.З.Ы. в аттаче пример обхода квадрата 6х6, который предложила программа - это известный фрактал, (не помню как называется) сразу наталкивает на мысли о множестве матриц, для которых существует решение.


Сообщение отредактировано: hardcase -


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


N337
****

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

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


Для 8x8 и 9x9 тоже. 10x10 лень дожидаться smile.gif


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


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

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

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


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

Не-е на клетку можно ступать только один раз. Ну а время в секундах измеряется.
С реализацией "в лоб" разобралась (спасибо xds)
Цитата(xds)
10x10 лень дожидаться

yes2.gif дольше чем полчаса.. (здесь то и встает вопрос, возможно ли оптимизировать на уровне алгоритма)
Цитата(Lapp)
Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!

промахнулась малость wink.gif
Цитата(Lapp)
И подозреваю, что скоро придется перенести в Задачи..

Да не, не придется: меня интересует алгоритм.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


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

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

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


Цитата(Lapp @ 25.11.2007 13:49) *
думается мне, что задача при n>3 не имеет решения..
Да, поспешил я с выводами.. smile.gif Вчера сделал прогу (в три ночи), запустил для эн равных 4 и 5, увидел, что решения нет - да и обобщил недолго думая.. smile.gif)))

Цитата(xds @ 25.11.2007 17:41) *

Для 8x8 и 9x9 тоже. 10x10 лень дожидаться smile.gif
Да, n=9 считалось на моем ноуте (AMD Turion 64 X2 @1.8 GHz) полминуты.. 10х10 пока все считается, уже 30 мин. Да, вопрос оптимизации встает, что называется, в полный рост smile.gif. Я предлагаю всем, кому интересно, сделать следующее.
1. Опубликовать здесь время работы своей программы без оптимизации (с указанием процессора).
2. Включиться в соревнование по оптимизации smile.gif.


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


N337
****

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

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


AMD Duron @ 800 MHz:
n = 8 - 1,43 с;
n = 9 - 18,84 с;
n = 10 - ? (точно больше 50 минут pardon.gif)

В первую очередь интересно, для каких ещё n нет решения smile.gif


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


code warrior
****

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

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


Ставлю свою софтину (C# .NET 2.0, без распараллеливания) на задачу с n=10 процессор Pentium D 925 (3GHz). Надеюсь, к вечеру закончит.

Сообщение отредактировано: hardcase -


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


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

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

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


После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘

Кстати, найденные первыми решения могут различаться в разных прогах - зависит от последовательности обхода клеток.

hardcase прав, очень похоже на фрактал. Но только я бы не стал искать сходства с каким-то конкретным фракталом. Если подумать, то так и должно быть (круто ляпнул, типа вумный.. smile.gif) - структура больших петель повторяет структуру малых. Вообще, забавно, что в таких простых условиях получается такой интересный результат.. smile.gif

2 xds: думаю, решения при n<>2,3 есть всегда. Я сейчас вывожу все решения, и их число растет с ростом n. Четверке и пятерке просто не повезло.. smile.gif

Сейчас тоже запущу свою прогу на n=10 и пойду спать smile.gif


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


Знаток
****

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

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


А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.


--------------------
Objective-C, Unity3d
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


N337
****

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

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


Цитата(Lapp @ 26.11.2007 22:50) *

После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘


1. По условию конец пути фиксирован - противоположная сторона первой строки (столбца).
2. И шо ж вы все транспонируете smile.gif


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


code warrior
****

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

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


Цитата(feniks25 @ 26.11.2007 16:17) *
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.

Для того, кто знает С, перевести будет не проблема. Единственный момент, у меня катается кубик с запрещенной гранью, остальные грани не нумерованы, результат она выдает в виде команд кубику (распечатываются они в обратном порядке при выходе из рекурсии).

З.Ы. Комп до сих пор считает - вот уже на протяжении 5 ч 30 м.

Сообщение отредактировано: hardcase -


Прикрепленные файлы
Прикрепленный файл  Program.txt ( 5.77 килобайт ) Кол-во скачиваний: 273


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


code warrior
****

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

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


Как то даже незаметно закончился расчет "в лоб" для решения задачи с n=10. Времени ушло 7ч 25м.
Вот результирующий файл. Еще раз замечу, что читать решение нужно задом-наперед (т.е. снизу - вверх).


Прикрепленные файлы
Прикрепленный файл  sol.txt ( 788 байт ) Кол-во скачиваний: 229


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


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

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

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


Цитата(hardcase)
Времени ушло 7ч 25м.

Вот это да-а-а mega_chok.gif
З.Ы Напишу средние значения для n=8 и n=9 (измеряла по 10 раз, потом считала среднее значение)
n=8 : 0.9 сек
n=9 : 8,2 сек
(Процессор Intel Pentium 4 CPU 2.80GHz)

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


code warrior
****

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

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


Судя по ответам xds'а, его программа справится с задачей часа за 3.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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