Алгоритм кубика Рубика сократили до 23 ходов

[and_rew]

Да. Пожалуй одна из самых известных головоломок будет занимать умы математиков еще долго.

[MYPABEU]

Да.. Неплохо было бы и алгоритм выложить.. Это моя мечта..
Представляете, на глазах у удивленных людей, на спор за 20 с небольшим ходов собирать рубик из любого состояния... =)

[almos]

Угу, а еще перед этим на глазух у изумленных людей, на бумажке просчитать 1-2 млн связанных состояний.

[almaz]

а кто-нибудь наблюдал за сколько в среднем ходов делают люди, которые легко собирают любую комбинацию рубика?
а то есть знакомые которые почти моментально, но наблюдать лень

[falone]

собираю в среднем за три минуты - не моментально конечно, но все-таки =)
вот только без практики забывается

[falone]

ну парниша молодец конечно. а Вы соберете кубик? =)

[mlurker]

Понравилась фраза "...математиков-теоретиков, которые посвятили свою карьеру решению этой задачи..."

[nooze]

ага, "будет что внукам рассказать"

[Stepanow]

... внукам других математиков, у которых на кубик Рубика ушла не вся жизнь, а только её часть.

[egorF]

эта задача имеет большое прикладное значение.

[dmitriev_dmitry]

да уж, нашли товарищи чем заняться :)

[Constantine]

Заинтриговали. Можно ссылку или суть в двух словах?

[girlie]

Я представляю, каково им было бы узнать, что эту задачу сможет решить компьютер за небольшое количество часов..

[grolse]

Может не часов, а лет?

[zvirusz]

Максимальное количество ходов

в смысле - минимальное? :)

[zvirusz]

бррр... :\

[dmitry_dvp]

минимальное имеет смысл только при заданном исходном состоянии.
Здесь речь идет о максимальном среди минимальных по всем исходным состояниям
:-)

[zvirusz]

ага, понял уже... со 2й попытки.
вредно что-то умное пытаться понять после 9 часов на работе :)

[diamant]

супремум :)

[ArSoron]

Максимин.

[diamant]

новояз

[ArSoron]

Нет. Математический сленг.Термины "Максимин" и "Минимакс" используются (по крайней мере у нас) на всех математических предметах.

[FeelBetter]

Теже шинусы и чосинусы, это все индивидуально по преподам, кафедрам, обобщать все возникающие у них в голове ассоциации под мат.сленг не стал бы.

[crazylammer]

Минимакс и максимин - термины теории игр (совершенно не сленг, устоявшиеся). Супремум и инфимум - теории множеств.

[FeelBetter]

как можете заметить во всех источниках эти "термины" заключаются в кавычки, что и означает их принадлежность именно к сленгу, с целью урезания полного выражения. Таким образом они не являются терминами теории игр.

[VovixLDR]

Вы имеете в виду "синх" и "кош"?:)

[toxa_xxl]

Вот не понимаю. Какое у этой задачи ПРАКТИЧЕСКОЕ значение? Т.е скольким людям на земле станет жить лучше от того за 23 или за 21 ход можно собрать кубик-рубик. Идиотизм в чистом виде.

[maximw]

А какое практическое применение полетов на Марс? Скольким людям станет лучше жить от новых фоток его поверхности? Или какое практическое применение от попыток доказать теорему Ферма?

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

[Lithium]

На счёт полезности полётов на Марс, я готов по спорить. Так как в Марсе вижу потенциальную планету обитания человека. Возможно это не очень скоро настанет, но настанет точно.

[odessky]

А не проще ли не засырать свою планету?

[MadJeck]

Проще, пока китайцы экспансию не начинают.

[blasto]

Ух-ты..новая обитель - Марс). Вы, наверное, не особо интересовались красной планетой) Либо сильно увлеклись просмотром к/ф "Вспомнить все".

[LokoMan]

нет, я прошёл Mass Effect.

[maximw]

Возомжно, пример не самый удачный. Но до практического применения и пользы от Марса так далеко, что на текущий момент это только убытки (и материальные и человеко-часы работы не самых плохих мозгов на планете), причем гораздо более значительные в сравнении с 7,8 ядро-лет вычислений, использованных для решения обсуждаемой задачи .

[Lithium]

А не проще ли не засырать свою планету?

Причём тут засорение своей планеты? Я ж говорю не о переселении на Марс, а об потенциальной планете для обитания.

Ух-ты..новая обитель - Марс). Вы, наверное, не особо интересовались красной планетой) Либо сильно увлеклись просмотром к/ф "Вспомнить все".

Интересуюсь красной планетой в достаточной мере. Разумеется что это не наступит завтра, но наступит.

2  maximw
- Мобильные телефоны никогда не станут популярными, это очень дорого и вредно для здоровья...
- Человек ещё очень не скоро полетит в космос...
- Интернет - сеть которой будут пользоваться только учёные и военные...

[maximw]

Отличные цитаты. Они лишь подтверждают, то что предсказание практической пользы (или ее отсутствия) от развития той или иной идеи или достижения есть дело небалгодарное :)

[VovixLDR]

и поэтому лучше идею развить, а там посмотрим, что получится:)

[SpeCT]

Простите за занудство, но не могли бы вы привести пример чего-то материального, в основу модели чего входит кубег?

Марс - понятно, исследования, история планеты, вселенной, возможная колонизация и т.д. Но кубег...

[maximw]

Я не претендую на достоверность и реальность приведенной далее цепочки, пусть это будет такая же фантастика как и колонизация Марса.

Итак:
Решение задачи Кубика-рубина => Новые алгоритмы комбинаторики => Новые системы криптоанализа => Новые системы защиты информации => Государственная безопасность и коммерческая тайна.

[SpeCT]

Спасибо за пример, о данном направлении не задумывался.

PS: На ум сразу пришла статья, где описывалось, что с появлением молекулярных (нано?/био? — не помню) компьютеров мощности поднимутся на столько, что все(!) современные алгоритмы криптования станут просто бесполезны.

[LeeNiffko]

Скорее всего, речь шла о квантовых компьютерах :)

[Li0liQ]

Извините, теорему Ферма уже доказали...

[maximw]

Огромное спасибо за ссылку! Поищу более подробную информацию по поводу этого доказательства. Одной лишь википедии сложно доверять в таком вопросе :)

[Ag47]

Доказать, то доказали, и этих доказательств несколько.
Все ищут наиболее простое, цепляясь за слова самого Ферма
который говорил,что её можно доказать в пару строчек.
Едисвенное:он не привёл её доказательства, по слухам,
сославшись на нехватку бумаги под рукой.

[toxa_xxl]

Полет на Марс то как раз связан с практическими задачами. Насчет теоремы ферма не знаю. Возможно её доказательства могут открыть какие то скрытые закономерности.
В науке ПОЛНО задач гораздо более прикладных. А фундаментальная наука это тоже хорошо. Вот только важно чтобы у нее прицел был на прикладное применение. Пусть даже гипотетическое. А кубик-рубик идиотизм, во всяком случае пока мне не доказали обратное.

[yellka]

Практическое применение находят те технологии, которые разрабатываются для полётов на Марс.
Вообще вся космическая индустрия - это большой полигон, на котором делается множество открытий-изобретений-разработок, которыми мы затем наслаждаемся в реальной жизни. Множество полимерных материалов, например, обязаны своим изобретениям поискам идеальной одежды для космонавтов. то же и со множеством других изобретений

[jerom]

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

[Lithium]

Где-то слышал что у всех подобных игр практическое применение заключается в торможении работы учёных. В частности слышал про известную игру пятнашки, где на поле 4х4 находится 15 фишек с номерами и их нужно выстроить по прядку. Соответственно разрабатывается врагами для торможения технического прогресса страны противника. Вместо того чтоб придумывать новый вид оружия, учёный сидит и играется в пятнашки.

[Faxfox]

Так ведь это основы основ алгоритмов!

[shai_xylyd]

Ученый посидит-посидит, подумает. Используя теорию групп, поймет, что решить можно не все комбинации, до от злости нажмет красную кнопку.

[maximw]

Описанное Вами больше похоже на "офисный планктон", чем на реальных ученых, впрочем, и среди них есть "планктон" :)

[namor]

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

[Faxfox]

Не чувак ты неправ, если так рассуждать, то можно ваще на все забить и сидеть пиво у телека сосать!

[naishin]

Есть анекдот в тему - про негра, который нифига не делал, сидел под пальмой и ел бананы. ))
Дета тут в притчах вроде.

[VovixLDR]

Угу, если забыть о том, сколько его собратьев не дожили даже до момента, когда они смогли бы съесть свой первый банан:(

[SmartBye]

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

[dmitriev_dmitry]

Может быть продолжить дальнейшее развития человечества подальше от обезьяны?

[1allen]

далеко не всё делается практики ради.

[nihilanth]

У Томаша Рокицки слишком много свободного времени.

[lovermann]

Этот Томаш завтра свои вычисления применит где-нибудь в физике, алгоритмике или математике и завхатит весь мир со всякими майкрософтами и гуглами :)

[Stepanow]

Как правило у таких Томашей находится лаборант в очках, который и становится миллионером применяя идею в практической сфере. А сами теоретики кроме премий и грантов никакого богатства не наживают увы.

[LOGAN4eg]

Помнится в детстве я собирал кубик-рубик путем переклеивания наклеек.))

[Kirpichtion]

Мне больше нравилось разбирать его на кусочки )

[blasto]

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

[vollossy]

Я знал, знал, что не только я занимался этим :)

[eschava]

даже таким способом за 23 хода собрать невозможно )

[Vadi]

Интересно, а за сколько ходов можно разложить пасъянс и другие игры они тоже считают?

[Tigger]

Есть целый пласт игр, таких как Кубик Рубика и пятнашки (они называются механическими головоломками), задачка "Священники и черти" (логические головоломки), которые похоже решаются - через ориентированные графы. Для них всех существует понятие "божественный алгоритм" - алгоритм с минимальным числом ходов для решения задачи. Простой карточный пасьянс (как и покер, например) в число таких задачек не входит, он решается другими методами.

[iNight]

Косынку по 3 карты я как то за время меньшее минуты разложил, даже не помню за сколько, но 50 с чем-то. Скорее всего просто повезло.
А вот кубик Рубика я только одну сторону научился собирать :(

ЗЫ: Интересно, сколько народу сейчас ломанётся в Гугл искать алгоритм сборки?

[DevCode]

Могу сказать что один то точно.

P.S. Я :)

[yelbota]

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

[Tigger]

На раскладку пасьянсов человеко-часов тратится больше (особенно на работе :) ), а так они решаются по простому подсчету вероятности. При определенной сноровке это даже в уме можно делать. Ну не со 100% точностью, конечно, но серьезно повышая свои шансы.

[alcanoid]

ФИДЕ вовремя проплатила Вассерману. Поэтому шахматы до сих пор не решены.

[MindiveR]

А вот по шашкам проплатить не успели… :(

Кстати, а что еще мы «не знаем» об Анатолии Вассермане? Смотрим (ну, или вспоминаем) здесь: http://boyany.nnm.ru/vsya_pravda_ob_anat… ;)

[yellka]

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

[milkfake]

Вспомнился фильм с Виллом Смитом "В погоде за счастьем". Там, помнится, он кубик Рубика собирает минуты за 2.

[glider]

Для чемпионов по скоростной сборке кубика Рубика это вообще не результат :)

[Ruberoid]

Более того, вот ссылка на видео, где мальчуган собирает кубик рубика ногами за 50 секунд.

[hlomzik]

здесь сборка четырех разнокалиберных кубиков за 5 минут
недавний мировой рекорд - 9,18 (в Википедии информация, кстати, до сих пор не обновлена)

[dime]

За две я в детстве собирал без проблем. Это совсем не трудно.
Сейчас минуты за три-четыре соберу.

[kotobaks]

Одно дело сидеть и производить расчеты кол-ва комбинаций, а другое - собирать кубик одной рукой:)

[DeadlyShadow]

на математики-теоретики нашли самый важный в своей области предмет для исследований. Это как американские ученый всякие ненужности исслдуют типо влияние лунного света на рост телеграфных столбов.

А ну Томаш Рокицки конечно молодец!))

[domen]

Была бы возможность поднять касту поднял бы) >.

[force]

Была бы возможность поднять карму Томашу Рокицки, поднял бы ;)

[bugrimov]

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

[micle]

Это... А где собственно алгоритм сборки за 23 хода? :)

[A_N]

Зажали видимо...)

[jerom]

Он не строил алгоритм, а оценивал диаметр гигантского графа состояний. Алгоритм — отдельная, совсем другая задача.

[ober]

да-да, это же ТЕОРЕТИЧЕСКАЯ работа, а не практикум...

[force]

Я думаю алгоритм банальный. Выпускается книжка на 1000 страниц с фразой: "посмотрите на свой кубик Рубика, если у вас такая-то комбинация, поверните такую-то грань по/против часовой стрелки." И так 1000 страниц ;) И обещается что любую комбинацию можно разложить за максимум в 23 хода

[globik]

Число возможных различных состояний кубика Рубика равно (8!

[globik]

Извините, отфильтровалась формула. Хотел написать, что в книжке будет 43 252 003 274 489 856 000 страниц (такого колличество комбинаций кубика Рубика)

[force]

А зачем тратить целую страницу на одну комбинацию? Мелким шрифтом, с исключением некоторых простейших симметрий, думаю можно и в 1000 страниц уложится.

[BuriK666]

Обожаю кубик Рубика.

[force]

Я думаю в журнале Квант дано развернутое объяснение фразы: " но оно вполне соответствует выкладкам математиков-теоретиков, которые посвятили свою карьеру решению этой задачи. Они предполагают, что минимальное количество ходов находится где-то в начале третьего десятка."
Т.е. все предпологали, что ходов 22-23, но точное доказательство получили только сейчас.

[hlomzik]

23 хода, как я помню. В Кванте. И об этом вполне уверенно говорилось...
На самом деле тоже пугают подобные «исследования», оставляющие этот самый привкус дежавю...

[Smerig]

было кино с джимом керри, триллер что ли, 23 назывался :)

[blasto]

О как) Кубик! Уже с большой буковки начали называть)))

[mivlad]

Титановый, со стороной около километра.

[DeadlyShadow]

хорошо хоть над алгоритмом вкручивания лампочик за 22 "вращение" головы не ломают. Там вообще море комбинаций!

[Fanatik]

Блять ну почему эти сраные новости вызывают такой ажиотаж, все обсуждают и т.п. аж противно.

[lovermann]

Боятся упустить потенциального гения. Талантливых людей надо уметь "выцепить" как можно быстрее. Ну, вы же сами видите, какая проблема обстоит с поиском специалистов.

[sfinx]

А эти вычисления можно производить как распределенные? т.е. чтобы не искать суперкомпьюет а просто собрать сеть из нескольких тысяч компьютеров и считать себе спокойно, я бы свое процессорное время этому отдал не задумываясь

[VovixLDR]

Отдай лучше в F@H, больше пользы будет, а этот фанатик еще машинного времени за свои деньги купит.

[force]

Кстати, если кого интересует алгоритм сборки кубика Рубика, могу поискать у себя бумажку с ним (в детстве мне отец нарисовал). Алгоритм заключается в постепенном сборе кубика и использованием определенных паттернов. Естественно медленный, естественно неоптимальный, зато позволяет собрать кубик и может использоваться для понтов.

[hlomzik]

В Википедии есть много очень хороших ссылок (особенно ссылки на Квант).
Я использую не самый оптимальный алгоритм (зато после половины сборки используется всего одна формула) и уверенно собираю кубик меньше, чем за 3 минуты. Чувствую, что уже пора переходить на более оптимальные алгоритмы и развивать мизинцы ;)

[force]

Ага, согласен, там всё есть. Просто я хотел показать постом, что всё не так страшно. Ведь если глядеть профессионалов, которые собирают на эвристике и интуиции, то становится очень боязно. :)

[hlomzik]

Как я понял, его «доказательство» заклюается в оптимизированном брутфорсе?
Законченные логические выкладки ведь эффективнее...

[pxx]

А как на счет теоретической модели и доказательства для такого монстра?

[icCE]

Что уж мелочится!
http://www.youtube.com/watch?v=CruqZhN_5…

[HSBK]

Создатель кубика-рубика, наверно, и представить себе не мог, что над его игрушкой будут ломать голову математики и компьютеры =)

[FeedYourHead]

Кубик Рубика отлично тренирует мозг.. По старой памяти помню, как у меня болела голова после часа "игры" с ним.
P.s. Недавно ехал в метро. Люди вели себя как обычно - кто спал, кто читал, а один парень ехал и собирал кубик Рубика. Скажу честно, я позавидовал...

[maaD]

Вообще процессор Intel Core 2 Quad Q6600 имеет частоту 2.4 ГГц, а не 1,6 ГГц, как указано в новости.

[TigerClaw]

Я конечно понимаю, доказательство максимального числа ходов сборки кубика хорошо. Но как то уж получается решил он это брутфорсом. ИМХО не спортивно. Дайте мне такой кластер и я докажу, что квейк первый за 25 минут можно пройти ;)

[Pilot34]

на компе проверять неспортивно) надо математически доказывать)

[CibronNethis]

Все время его имя читаю как Томаш Росицки (Чешский футболист) =)
А вообще на то она и фундаментальная наука математика что основа многим технологиям.

[dobersoft]

Я придумал, как значительно упростить вычислительное решение задачи о кубике Рубика.
kartz.ru/2012/01/02/rainbow-rubik/
Опубликовать его здесь сейчас не могу.