![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Кубик Рубика
Когда-то давно, еще во времена Спектрума, я написал программу для собирания кубика-рубика не более, чем за 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 килобайт был:)
Вы вот, френды, кубиком рубика маньячили?
Использовалась концепция "жадного" алгоритма. 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 килобайт был:)
Вы вот, френды, кубиком рубика маньячили?
no subject
no subject
умею до сих пор.
no subject
no subject
no subject
no subject
no subject
no subject
во-вторых, 3000 это уже из разряда баек)) у меня рекорд ~1200.
в-третьих, повторить мне в последние пару лет не удавалось.
no subject
Жадный алгоритм - это не такой, который стремиться занять все ресурсы. Это такой, который ищет локальные оптимумы на каждом этапе для поиска глобального оптимума (http://en.wikipedia.org/wiki/Greedy_algorithm). (Некоторые задачи жадным алгоритмом решаются точно, некоторые приблизительно, а некоторые не решаются вообще). Т.е. описанный тобой алгоритм - таки да, жадный :), но с ресурсами это никак не связано (и реализации жадных алгоритмов для других задач могут, наоборот, потреблять совсем мало ресурсов).
no subject
no subject
хранить ранги, кстати, очень выгодно в плане использования памяти. Ранг (1 байт) приемлемо покрывает все повороты данного рисунка на грани вокруг оси и 120 (факториал ведь, да?) вариантов раскраски отдельных квадратиков, facelet-ов по терминологии чувачков из ccs.neu.edu.
Вообще, ранг позиции -- чудесная концепция.
no subject
я ещё и слово algorithm неверно написал, позор мне на седеющую голову.
no subject