ermouth: (Default)
[personal profile] 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 килобайт был:)

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

Date: 2007-10-10 05:23 am (UTC)
From: [identity profile] bodry-yar.livejournal.com
чисто механически научили собирать еще в садике, в старшей группе (никто не верит). Забыл к третьему, что ли, классу. Сейчас вот не умею%)

Date: 2007-10-10 06:08 am (UTC)
From: [identity profile] lassi-.livejournal.com
научилась из "Техники молодежи", а от таких вот прибабахов далека.
умею до сих пор.

Date: 2007-10-10 10:09 am (UTC)
From: [identity profile] zosika.livejournal.com
когда ты такое пишешь - мне тут же хочется в тебя влюбиться на полчасика!

Date: 2007-10-10 11:31 am (UTC)
From: [identity profile] ermouth.livejournal.com
ой, спасибо :) влюбляться в этом конкретном случае стоило бы в меня 16-летнего...

Date: 2007-10-10 12:09 pm (UTC)
From: [identity profile] radioto4ka.livejournal.com
Я все хочу научиться собирать :)

Date: 2007-10-10 04:57 pm (UTC)
From: [identity profile] ktototam-lj.livejournal.com
дима, когда ты пишешь такие посты, со ссылкой ниже на 16 лет - у меня появляется некий благоверный трепет, что ли))))

Date: 2007-10-10 10:27 pm (UTC)
From: [identity profile] ermouth.livejournal.com
у меня, Серёжа, тоже (гыыы) трепет, когда мне говорят, что в 18 лет человек по 3000 народу собирал %)

Date: 2007-10-10 10:38 pm (UTC)
From: [identity profile] ktototam-lj.livejournal.com
ну во-первых, я не один это делал.
во-вторых, 3000 это уже из разряда баек)) у меня рекорд ~1200.
в-третьих, повторить мне в последние пару лет не удавалось.

Date: 2007-10-10 10:34 pm (UTC)
From: [identity profile] ex-neo-is-fl156.livejournal.com
Нет, не маньячил. Мне терпения не хватило.

Жадный алгоритм - это не такой, который стремиться занять все ресурсы. Это такой, который ищет локальные оптимумы на каждом этапе для поиска глобального оптимума (http://en.wikipedia.org/wiki/Greedy_algorithm). (Некоторые задачи жадным алгоритмом решаются точно, некоторые приблизительно, а некоторые не решаются вообще). Т.е. описанный тобой алгоритм - таки да, жадный :), но с ресурсами это никак не связано (и реализации жадных алгоритмов для других задач могут, наоборот, потреблять совсем мало ресурсов).

Date: 2007-10-10 10:37 pm (UTC)
From: [identity profile] ex-neo-is-fl156.livejournal.com
А жадным он называется потому, что он не предполагает временные потери для большей прибыли в будущем. По аналогии: ты хочешь заработать максимум, жадным алгоритмом ты тут же пойдёшь на работу, после чего будешь раз в два месяца её менять на более высокооплачиваемую. Куда оптимальнее, возможно, было бы лет 10 поучиться, не зарабатывая вообще ни фига, пройти ещё лет 5 стажировки, а потом (оставшиеся лет 10 до пенсии) работать хирургом-кардиологом и рубить свою капусту :)

Date: 2007-10-10 10:54 pm (UTC)
From: [identity profile] ermouth.livejournal.com
слушай, значит у меня не жадный был. хотя хэша 3000 пар рангов хватало, чтобы на спектруме собирать кубик за секунду примерно.

хранить ранги, кстати, очень выгодно в плане использования памяти. Ранг (1 байт) приемлемо покрывает все повороты данного рисунка на грани вокруг оси и 120 (факториал ведь, да?) вариантов раскраски отдельных квадратиков, facelet-ов по терминологии чувачков из ccs.neu.edu.

Вообще, ранг позиции -- чудесная концепция.

Date: 2007-10-10 10:40 pm (UTC)
From: [identity profile] ermouth.livejournal.com
о, спасибо за ссылочку, вывела меня на http://en.wikipedia.org/wiki/Spanning_tree_protocol.

я ещё и слово algorithm неверно написал, позор мне на седеющую голову.

Date: 2009-03-07 03:48 pm (UTC)
From: [identity profile] andrey-larin.livejournal.com
Охуенно!

Profile

ermouth: (Default)
ermouth

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 07:19 pm
Powered by Dreamwidth Studios