> 1 <

Автор Сообщение

quest

Members


Статус

2 сообщений

Где: Russia
Род занятий: quest
Возраст:

#14   2008-09-17 22:01 GMT+3 часа(ов)      
Господа, подскажите с чего начать решение задачи о сборке кубика Рубика? Ссылки, идеи и прочая - приветствуются

AYKO

Members


Статус

36 сообщений

Где: Russia
Род занятий: Чайник
Возраст:

#18   2008-09-19 17:52 GMT+3 часа(ов)      
Есть мнение, что начать нужно с того что бы научиться его собирать руками =)

quest

Members


Статус

2 сообщений

Где: Russia
Род занятий: quest
Возраст:

#40   2008-09-26 16:06 GMT+3 часа(ов)      
Руками то могу. В инете море ссылок где описывается как его собрать. Именно руками. А хотелось бы что бы компьютер собрал... И вот как подойтиии к этой задаче - не могу придумать. Понятно что кубик будет представлен списком с 6 элементами, понятно что будут функции которые крутят грани, вопрос в другом немножко - как понять какую последовательность движений делать?

andy128k

Members


Статус

5 сообщений

Где: Ukraine
Род занятий: Программист
Возраст: 36

#51   2008-10-01 16:24 GMT+3 часа(ов)      
Несколько лет назад я такую хотел написать на C++ и Qt. Начал и вскоре забросил. Потом переписал на OCaml и GTK+. Она собирает только один слой, если лень свою поборю, думаю доделать. Задумывалась программа для проверки собираемости: "нарисовать" на кубике "рисунок" и заставить программу из этого положения собрать кубик, т. е. доказать, что такой "рисунок" возможен. Если интересно, могу дать исходники.

_lee

Members


Статус

69 сообщений

Где: Russia
Род занятий:
Возраст:

#85   2008-10-07 12:49 GMT+3 часа(ов)      
Кубик Рубика (КР) описывается теорией групп, есть даже старая советская книжка по ТГ в которой все объясняется на примере КР.
А учитывая небольшое (по сегодняшним компьютерным меркам) количество комбинаций возможно просчитать задачу полным перебором. Игра в русские шашки 8x8 уже просчитана таким образом до конца.

andy128k

Members


Статус

5 сообщений

Где: Ukraine
Род занятий: Программист
Возраст: 36

#86   2008-10-07 13:11 GMT+3 часа(ов)      
Цитата
_lee :
А учитывая небольшое (по сегодняшним компьютерным меркам) количество комбинаций возможно просчитать задачу полным перебором.


Это вызывающе неверно. "Число возможных различных состояний кубика Рубика равно 43 252 003 274 489 856 000".

http://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D0%BA_%D0%A0%D1%83%D0%B1%D0%B8%D0%BA%D0%B0#.D0.9A.D0.BE.D0.BC.D0.B1.D0.B8.D0.BD.D0.B0.D1.82.D0.BE.D1.80.D0.B8.D0.BA.D0.B0

А это никакому обычному компьютеру не по зубам.

Iggi

Members


Статус

10 сообщений

Где: Russia Москва
Род занятий: Developer
Возраст: 34

#87   2008-10-07 13:59 GMT+3 часа(ов)      
Можно собирать кубик по известным алгоритмам, эту задачу можно обобщить для кубика (NxNxN). Есть даже ютубки где собираются кубики 128x128x128 (или около того).
А можно пробовать найти оптимальный путь сборки. Существует теорема (не доказанная вроде), что кубик (3х3х3) можно собрать не более чем за 25 поворотов из любого положения.
Головной мозг - это орган, которым мы думаем, будто мы думаем.
А. Бирс

_lee

Members


Статус

69 сообщений

Где: Russia
Род занятий:
Возраст:

#88   2008-10-07 15:46 GMT+3 часа(ов)      
Уже доказано что :
За 23 можно собрать

andy128k
Это вызывающе неверно. "Число возможных различных состояний кубика Рубика равно 43 252 003 274 489 856 000".


Видимо перебирали целые группы состояний, с одной стороны Brute Force- решение, а с другой не полное

andy128k

Members


Статус

5 сообщений

Где: Ukraine
Род занятий: Программист
Возраст: 36

#92   2008-10-07 17:43 GMT+3 часа(ов)      
Цитата
_lee :
Уже доказано что :
За 23 можно собрать

andy128k
Это вызывающе неверно. "Число возможных различных состояний кубика Рубика равно 43 252 003 274 489 856 000".


Видимо перебирали целые группы состояний, с одной стороны Brute Force- решение, а с другой не полное



Если достаточно 23 хода, то для перебора потребуется (2 * 6) ^ 23 ходов, а это больше чем число, которое я привёл.

_lee

Members


Статус

69 сообщений

Где: Russia
Род занятий:
Возраст:

#93   2008-10-07 21:20 GMT+3 часа(ов)      
То что решается за 23 хода получили именно перебором разных классов состояний в течении 8 лет машинного времени.

Кратчайшее решение действительно нельзя найти перебором. Но нможно решать поэтапно, ища не кратчайшее решение.
2 первых ряда собираются тривиально. каждый следующий кубик приводится в нужное положение за 3-4 хода.

Нетривиально поставить только последнюю грань, а это
(4!*3^3)(4!*2^3)/2 = 62208 комбинаций
что уже поддается перебору вместо применения кучи сложных алгоритмов

отредактировал(а) _lee: 2008-10-07 21:25 GMT+3 часа(ов)

juna

Members


Статус

23 сообщений

Где: Russia
Род занятий:
Возраст:

#133   2008-10-31 20:27 GMT+3 часа(ов)      
_lee
То что решается за 23 хода получили именно перебором разных классов состояний в течении 8 лет машинного времени.

Более достоверная информация пока за 25. Вот ссылки:
http://www.gap-system.org/Doc/Examples/rubik.html
http://www.neu.edu/nupr/news/0507/rubik.html
http://www.ccs.neu.edu/home/gene/papers/rubik.pdf
http://hitech.newsru.com/article/22Aug2007/rubegg
http://www.geocities.com/CapeCanaveral/4344/192.html
http://arxiv.org/abs/0803.3435

LexxCherry

Members


Статус

41 сообщений

Где: Russia
Род занятий: студент, музыкант
Возраст: 27

#1288   2010-02-05 20:04 GMT+3 часа(ов)      
тема старая и вряд ли автор её ещё просмотрит, но я вот натолкнулся на пример программы, моделирующий Кубик Рубика, на языке Пролог. программа входит в набор примеров свободного интерпретатора SWI-Prolog.
Программа предусматривает графическую оболочку, в которой можно ресетнуть кубик и собирать самому или включить режим пошаговой сборки программой. Код этого примера приблизительно > 1000 строк.

_lee

Members


Статус

69 сообщений

Где: Russia
Род занятий:
Возраст:

#2706   2010-08-09 20:08 GMT+3 часа(ов)      
andy128k

А это никакому обычному компьютеру не по зубам.

Оказалось что по зубам.

Окончательное решение перебором нашли:
20 ходов
God's Number is 20
> 1 <


Онлайн :

1 пользователь(ей), 15 гость(ей) :
Hedin



Реклама на сайте: