Кубик Рубика

[ermouth]

Когда-то давно, еще во времена Спектрума, я написал программу для собирания кубика-рубика не более, чем за 31 поворот. На ассемблере, как водится :)  Жаль, не сохранилось выкладок --  я тогда теорию групп изучал, а это как раз оттуда задачка. Помню, как примерно работало всё. 

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

Так вот, Сначала первая часть программы при запуске генерила в 3/4 доступной памяти разннобразные* ветвящиеся варианты групп поворотов и их оптимизировала. Это несколько минут занимало. Чтобы отличать одну группу поворотов от другой, вводилось 6 осевых рангов позиции. Ранг позиции -- это такое число, которое характеризует текущую «степень собранности*» грани. Чем оно выше, тем более упорядочена грань. Естественно, те группы поворотов, которые ранг позиции серьезно* понижали, удалялись. В конце по запомненным группам поворотов создавался хэш, который по паре «начальный ранг кубика -- конечный ранг кубика» подбирал наиболее подходящую группу поворотов -- самую короткую наиболее приближающую к цели.

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

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

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

Протрахался месяца три, прорабатывая разные варианты и выискивая ошибки -- ассемблерный код править это не хухры-мухры :) Строгого доказательства про 31 ход у меня нет, конечно, но хуже результатов не получалось -- даже на автоматической проверке. Подпрограмма запутывала кубик случайным образом, а потом основная программа распутывала. И так несколько сотен тысяч раз.

Я к чему этот гон написал -- вот нашел софтинку, которая красиво так собирает кубик рубика :) Неоптимально только ни разу, ну да пофиг. http://www.ravlyk.narod.ru/rubic/download.html

http://www.ccs.neu.edu/home/gene/papers/rubik.pdf -- описание алгоритма, который собирает не более чем за 26 поворотов, но они средний поворот, кажется, считают за 2, а я считал за 1, так что в их терминах у меня было б в худшем случае поворотов 40-50. У пацанов, правда, кэш составлял 7 терабайт, а у меня 36 килобайт был:)

Вы вот, френды, кубиком рубика маньячили?

Comments

[andrey-larin.livejournal.com]

Охуенно!