И быстрое решение, использующее алгоритм Тистлтуэйта
Кубик Рубика - это увлекательная вечная головоломка с квинтиллионами возможных состояний. Когда компьютерный фанатик превратился в энтузиаста искусственного интеллекта и вооружился горсткой ориентированных на человека алгоритмов для решения куба, я решил попробовать свои силы в программировании решателя кубика Рубика. Возможно, немного наивно, я не сразу понял, что решение куба оптимальным образом или доказательство того, что любой куб разрешим за 20 или меньше ходов, потребует приличного понимания математики, комбинаторики, оптимизации и теории групп. Веселая штука. Итак, я пролистал кучу статей, отмахнулся от старых книг по математике и искусственному интеллекту и приступил к написанию двух алгоритмов. Сначала я реализовал алгоритм Тистлтуэйта, который может решить любой куб за 52 хода или меньше, а затем оптимальный алгоритм Корфа, также известный как «Алгоритм Бога», который может решить любой куб за 20 или меньше ходов.
В этой статье я дам обзор некоторых структур данных, которые я использовал, и высокоуровневое описание каждого алгоритма. Мой код доступен на GitHub, и на момент написания версия 4.0.0 является последней версией. У меня также есть видео на YouTube, демонстрирующее программу (обратите внимание, что на видео показана версия 2.2.0, и с тех пор программа была усовершенствована).
Хотя это может быть очевидно, я хочу избавиться от этого как можно раньше. На современном компьютере невозможно собрать куб с помощью простого алгоритма грубой силы. Кубик Рубика 3x3 имеет 43 252 003 274 489 856 000 перестановок с коэффициентом ветвления около 13, и это слишком много состояний для повторения. Создание программного решателя включает в себя несколько эффективных структур данных, немного теории групп и множество умных алгоритмов.
Терминология и обозначения
Для тех, кто не знаком с кубиком Рубика, я буду использовать следующие термины и обозначения.
- Куби: один из 26 мини-кубиков, составляющих весь кубик Рубика.
- Центральный кубик: кубик с одной наклейкой в центре лица. Обратите внимание, что центральные кубы статичны. Их нельзя перемещать относительно друг друга (красный центральный куб всегда находится напротив оранжевого), а также их нельзя перемещать, скручивая грани.
- Edge cubie: кубик с двумя наклейками, похожий на красно-желтый кубик.
- Угловой кубик: кубик с тремя наклейками, например, красно-сине-желтый кубик.
- Лицевая сторона: сторона кубика Рубика, состоящая из 9 кубиков: 1 центр, 4 ребра и 4 угла. Есть шесть граней: передняя, задняя, левая, правая, верхняя и нижняя.
- Поворот: поворот на 90 или 180 градусов одной из шести граней. Учитывая, что каждую грань можно повернуть на 90 градусов по часовой стрелке, на 90 градусов против часовой стрелки («штрих») или на 180 градусов, существует 18 возможных поворотов.
Скручивания обычно следуют обозначению, что первая буква скручивающейся грани - это поворот на 90 градусов по часовой стрелке. Таким образом, F, B, U, D, L и R обозначают поворот на 90 градусов передней, задней, верхней, нижней, левой и правой сторон соответственно. Суффикс апострофа (’) обозначает« первичный »поворот на 90 градусов против часовой стрелки, поэтому R’ означает поворот правой стороны на 90 градусов против часовой стрелки. А суффикс «2» указывает на поворот на 180 градусов. L2 означает, что левая грань повернута на 180 градусов.
Вы также должны быть в курсе алгоритмов A * search и итеративного углубленного поиска в глубину (IDDFS), по крайней мере, на высоком уровне, хотя эта статья содержит краткий обзор каждого из них.
Некоторые O.K. Структуры данных для кубика Рубика
Написание программы для решения кубика Рубика с использованием человеческого метода, такого как послойный подход - тот, который идет в брошюре с новым кубиком Рубика - тривиально, и лежащая в основе структура данных не будет иметь большого значения. разница. Компьютер может собрать куб, используя человеческий метод, за незначительное время, менее секунды, даже на самых медленных языках программирования. Но при решении куба с использованием более ресурсоемких методов, таких как методы Корфа или Тистлтуэйта, структура данных и язык программирования имеют первостепенное значение. Алгоритмы, описанные в этой статье, включают в себя миллиарды раз скручивание куба и выполнение миллиардов сравнений, поэтому структура данных, используемая для представления куба, оказывает большое влияние на время, необходимое для решения. В начале своей реализации я протестировал следующие структуры:
- Трехмерный массив символов 6x3x3. Цвет лица индексируется как
cube[SIDE][ROW][COL]. Это интуитивно понятно, но медленно. - Единый массив из 54 символов. Это быстрее, чем первая структура, а ряд и шаг вычисляются вручную (тривиально). Это все еще медленно.
- 6 64-битных целых чисел. Для тех, кто знаком с шахматной областью, этот метод, по сути, является битовой доской, и он значительно быстрее, чем первый и второй методы. Скручивание может выполняться с помощью побитовых операций, а сравнение лиц можно выполнять с помощью масок и сравнения 64-битных целых чисел.
- Массив угловых кубов и отдельный массив краевых кубов. Элементы каждого массива содержат индекс куба (0–11 для ребер; 0–7 для углов) и ориентацию (0 или 1 для ребер; 0, 1 или 2 для углов).
Я использовал третью структуру для своей первоначальной реализации алгоритма Thistlethwaite, которая была реализована с использованием деревьев решений. Позже я улучшил алгоритм, чтобы использовать базы данных шаблонов, которые подробно описаны ниже. Четвертая структура намного быстрее при использовании баз данных шаблонов, и в конце концов я использовал эту структуру как для алгоритмов Тистлтуэйта, так и для алгоритмов Корфа. Структуры три и четыре подробно описаны в следующих двух разделах.
Структура битовой доски
Расширяя структуру три, каждая грань куба состоит из 9 наклеек, но центр неподвижен, поэтому нужно сохранить только 8. И есть 6 цветов, поэтому цвет может храниться в одном байте. Таким образом, 8 наклеек на лицевой стороне кубика Рубика могут храниться в 64-битном формате.
Учитывая эти (произвольные) определения цвета:
enum class COLOR : uchar {WHITE, GREEN, RED, BLUE, ORANGE, YELLOW};Лицо может выглядеть так, сохраненное в виде одного 64-битного целого числа:
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001Что расшифровывается как:
WGR
G B
WYOПреимущество использования этой структуры состоит в том, что побитовые инструкции сборки rolq и rorq могут использоваться для перемещения грани. Прокрутка на 16 бит вызывает поворот на 90 градусов, а прокрутка на 32 бита дает поворот на 180 градусов. Смежные части нужно обрабатывать вручную - например, после поворота верхней грани необходимо переместить самые верхние цвета передней, левой, задней и правой граней. Повернуть лица таким образом действительно быстро. Например, прокатка
00000000 00000001 00000010 00000011 00000100 00000101 00000000 00000001на 16 бит дает
00000000 00000001 00000000 00000001 00000010 00000011 00000100 00000101Расшифровано, это выглядит так:
WGW
Y G
OBRВот как это выглядит со встроенной сборкой на C ++ с использованием g ++ с синтаксисом сборки AT&T. (Вот модель на GitHub.)
/* Where face is an array of 8 characters cast to a
64-bit number. */
asm volatile ("rolq $16, %[face]" : [face] "+r" (face) : );
Еще одно преимущество этой структуры состоит в том, что сравнение состояний куба в некоторых случаях может быть выполнено с использованием умных битовых масок и стандартных целочисленных сравнений. Это может значительно ускорить работу решателя. Кроме того, для создания копий куба при поиске решения требуется скопировать только 8 целых чисел.
Структура индекса-ориентации
Переходя к четвертой структуре из приведенного выше списка, алгоритм Корфа использует поиск A * с базами данных шаблонов в качестве эвристики. Базы данных шаблонов описаны более подробно ниже, но вкратце базу данных шаблонов можно рассматривать как функцию значения, которая принимает состояние куба и возвращает оценку нижней границы количества ходов, необходимых для выхода из этого состояния. в решенное состояние. Для алгоритма Корфа «состояние» представлено как перестановка и ориентация кубов. Например, индексы и ориентации 8 угловых кубов могут составлять часть состояния куба. При таком представлении имеет смысл хранить упорядоченный массив индексов угловых кубов i ∈ {0, ..., 7} и ориентаций o ∈ {0, 1, 2}.
Произвольно определяя соглашение, угловые кубы могут быть проиндексированы следующим образом:
0 1 2 3 4 5 6 7
ULB URB URF ULF DLF DLB DRB DRF
RBY RGY RGW RBW OBW OBY OGY OGWСтроки представляют индекс (0,…, 7), позицию в решенном состоянии (вверх-влево-назад,…, внизу-вправо-вперед) и цвета (красный-синий-желтый, ..., оранжево-зеленый -белый). Таким образом, красно-сине-желтый (RBY) куб имеет индекс 0 и находится в верхнем-левом-заднем (ULB) углу, когда куб находится в решенном состоянии. Оранжево-зелено-желтый (OGY) кубик имеет индекс 6 и находится в нижнем-правом-заднем (DRB) углу.
Точно так же реберные кубы могут быть проиндексированы следующим образом (опять же, произвольно).
0 1 2 3 4 5 6 7 8 9 10 11
UB UR UF UL FR FL BL BR DF DL DB DR
RY RG RW RB WG WB YB YG OW OB OY OGКрасно-желтый (RY) куб имеет индекс 0 и находится на пересечении верхней и задней (UB) граней, когда куб находится в собранном состоянии. Бело-зеленый (WG) куб имеет индекс 4 и занимает пересечение передней и правой (FR) граней.
С этой структурой также необходимо сохранять ориентацию каждого куба. Кромка может быть в одной из двух ориентаций, ориентирована или перевернута (o∈{0,1}), а угловая деталь может быть в трех разных ориентациях, ориентирована, повернута один раз или повернута дважды (o∈{0,1,2}). Более подробную информацию об ориентации частей можно найти в статье Конрада Райдера Edge Orientation Detection.
В этой модели поворот лица означает обновление индексов и ориентации. Это представление сложно запрограммировать, потому что человеку (по крайней мере, мне) трудно взглянуть на большой сгусток индексов и ориентировочных чисел и проверить их правильность. При этом эта модель значительно быстрее, чем динамическое вычисление индексов и ориентаций с использованием одной из других моделей, описанных выше, и поэтому она хорошо работает при использовании баз данных шаблонов.
Вы можете увидеть реализацию этой модели на моем GitHub.
Графическая структура
Моя программа также визуализирует куб, и я использовал другую структуру для этой части. Поскольку это не часть алгоритма решения, я лишь кратко коснусь этой структуры.
Я определил класс «куби», который состоит из шести квадратов с 1, 2 или 3 цветными гранями для центральной, краевой и угловой частей соответственно. Кубик Рубика состоит из 26 кубиков. Грани вращаются с использованием кватернионов и сферической линейной интерполяции (SLERP), и все это отображается в OpenGL.
Код кубиков и куба тоже есть у меня на GitHub.
Оптимальный алгоритм Корфа
Алгоритм Ричарда Корфа может собрать любой скремблированный куб за 20 ходов или меньше. Он работает путем поиска решений с использованием итеративного углубляющегося поиска в глубину в сочетании с A * (IDA *).
Итеративный поиск в глубину (IDDFS) - это алгоритм обхода дерева. Подобно поиску в ширину (BFS), IDDFS гарантированно найдет оптимальный путь от корневого узла дерева к целевому узлу, но он использует меньше памяти, чем BFS. Меньший объем памяти делает его применимым для поиска в деревьях с большим фактором ветвления, таких как кубик Рубика. Рассмотрим куб как корень дерева, т.е. глубину 0. Применение каждого возможного поворота куба (L, F, R и т. Д.) Переносит куб в новый узел на глубине 1, любой из которых может быть решенным состоянием. . В противном случае применение каждой комбинации из двух ходов (LF, LR, LU и т. Д.) Может собрать куб. Это продолжается до тех пор, пока не будет найдено решение.
Сама по себе IDDFS займет слишком много времени, чтобы решить большинство зашифрованных кубов. Есть 18 возможных скручиваний граней куба, большой фактор ветвления. После первого набора поворотов некоторые ходы можно обрезать. Например, двукратный поворот одной и той же грани является избыточным: FF совпадает с F2; FF ’означает отсутствие движения; FF2 совпадает с F ’; и так далее. Кроме того, некоторые ходы коммутативны: FB совпадает с BF; U2D совпадает с DU2; и т.д. Но даже после обрезки коэффициент ветвления превышает 13, поэтому поиск решения с сырой IDDFS на современном компьютере займет тысячи лет! Вот где пригодится A *.
A * - это алгоритм обхода графа, который используется для поиска оптимального пути от одного узла графа к другому, и, учитывая, что дерево является просто графом, его можно комбинировать с IDDFS. A * использует эвристику для поиска. Эвристика обеспечивает оценочное расстояние (количество поворотов) от одного узла (зашифрованное состояние) до другого (решенное состояние). Для правильной работы A * - в частности, для обеспечения оптимального пути - эвристика никогда не должна переоценивать расстояние. IDA * работает так же, как IDDFS, но вместо того, чтобы начинать поиск с глубины 0, он запрашивает эвристику для оценки расстояния до состояния цели и начинает с этой глубины. Если во время поиска предполагаемое расстояние через узел до решенного состояния превышает глубину поиска, узел удаляется из дерева. Другими словами, эвристика используется, чтобы увидеть, приближает ли куб к решенному состоянию или отдаляет ли он его от одного состояния куба к другому. Если поворот перемещает куб дальше от решенного состояния, то эту ветвь поиска можно обрезать.
Проще говоря, допустимая эвристика для кубика Рубика - это функция, которая принимает зашифрованный куб и оценивает или занижает количество ходов для сборки куба. Один из способов создания такой эвристической функции - создать базу данных всех возможных комбинаций подмножества кубов. Например, база данных, которая принимает индексы и ориентацию 8 угловых кубов и возвращает количество ходов для решения только углов. При такой базе данных, при условии, что зашифрованный куб потребует два хода, чтобы собрать угловые кубы, потребуется по крайней мере два хода, чтобы собрать весь куб. Скорее всего, это займет больше двух ходов из-за краевых кубов. На изображении ниже все углы решены, поэтому база данных шаблонов только для углов вернет оценку 0 переходов в решенное состояние. Это явно заниженная оценка, потому что ребра не решены, но это допустимая эвристика, потому что она никогда не переоценивает расстояние до решенного состояния. (Эта схватка находится на расстоянии 6 ходов от решенного.)
Базы данных шаблонов
Действительно, Ричард Корф предлагает использовать серию баз данных шаблонов в качестве эвристики для кубика Рубика, и в одной из баз данных хранится количество ходов, необходимых для решения угловых частей любой схватки. Есть 8 угловых кубиков, и каждый может занимать любую из 8 позиций, так что их 8! возможные перестановки. Каждую из угловых частей можно ориентировать 3 разными способами - любая из трех наклеек может быть обращена вверх - но ориентация 7 кубиков определяет ориентацию 8-го по законам куба. (Для математиков это связано с четностью куба, которая является четной для всего куба, но четной или нечетной, если рассматривать только углы или ребра.) Следовательно, существует 3⁷ возможных способа изменения углов. ориентированный. Всего их 8! * 3⁷ возможных способа шифрования углов куба, и эти 88 179 840 состояний можно повторять за разумный промежуток времени (30 минут или около того). Все угловые состояния могут быть достигнуты за 11 ходов или меньше, поэтому каждая запись в базе данных угловых шаблонов может быть сохранена в полубайте (4 бита). На диске база данных угловых шаблонов занимает около 42 МБ.
Корф предлагает две дополнительные базы данных: одну для 6 из 12 ребер, а другую для остальных 6 ребер. Учитывая, что в современных ящиках для разработчиков много оперативной памяти, я решил использовать две базы данных по 7 ребер в каждой. 7 ребер могут занимать 12 позиций, поэтому имеется 12P7 (12! / (12–7)!) Перестановок. Каждый угол можно сориентировать двумя способами, поэтому возможны 2⁷ возможных ориентации 7 краев. Опять же, это достаточно небольшое количество состояний куба для итерации, и все состояния могут быть достигнуты за 10 ходов или меньше. При хранении каждой записи в полубайте каждая из 7-ми краевых баз данных занимает около 244 МБ (12P7 * 2⁷ / 2 байта).
Наконец, я использовал одну дополнительную базу данных, в которой хранятся перестановки 12 ребер. Это занимает около 228 МБ (12! / 2 байта).
Использование более крупных пограничных баз данных и дополнительной базы данных перестановки краев приводит к огромному увеличению скорости. Более крупные базы данных приведут к еще большему увеличению производительности, но при этом легко использовать огромный объем памяти. Например, добавление еще одной граничной части к 7-граничной базе данных увеличивает размер каждой базы данных примерно до 2,4 ГБ.
Деталь реализации, которую Корф замалчивает в своем алгоритме, заключается в том, как создавать индексы в этих базах данных шаблонов. То есть, учитывая скремблированный куб, как создать идеальный хеш из индексов и ориентации краев или углов. Эта тема достаточно сложна, поэтому я решил посвятить ей еще одну статью, поэтому, если вас интересуют математические подробности, прочтите мою статью Последовательное индексирование перестановок: линейный алгоритм для вычисления лексикографического ранга.
Вкратце, индексация работает, сначала генерируя код Лемера перестановки кубического индекса, а затем преобразовывая код Лемера в ранг по основанию 10. (Код Лемера - это способ лексикографической нумерации перестановок). По 8 углам ранги будут.
Permutation Rank (0 1 2 3 4 5 6 7) 0 (0 1 2 3 4 5 7 6) 1 (0 1 2 3 4 6 5 7) 2 (0 1 2 3 4 6 7 5) 3 ... (4 0 1 2 3 5 6 7) 20160 ... (7 6 5 4 3 2 1 0) 40319
Затем аналогичным образом ранжируется перестановка ориентаций 7 угловых кубов. (Напомним, что ориентация 7 углов определяет ориентацию 8-го.)
Permutation Rank (0 0 0 0 0 0 0) 0 (0 0 0 0 0 0 1) 1 (0 0 0 0 0 0 2) 2 (0 0 0 0 0 1 0) 3 ... (1 0 0 0 0 0 0) 729 ... (2 0 0 0 0 0 0) 1458 ... (2 2 2 2 2 2 2) 2186
Наконец, эти два ранга объединяются вместе, чтобы сформировать индекс в базе данных.
index = rankWithoutReplacement(cornerIndexes) * 3^7 + rankWithReplacement(cornerOrientations)
Стоит отметить, что индексация в пограничных базах данных более сложна, поскольку она включает в себя создание рангов по частичным перестановкам (то есть 7 из 12 ребер). Ранжирование частичных перестановок также рассматривается в моей другой статье.
Поскольку алгоритм Корфа использует несколько баз данных шаблонов, предполагаемое количество переходов в решенное состояние, эвристика A *, является максимальным значением, возвращаемым из всех баз данных шаблонов. Более конкретно, учитывая состояние куба, в котором 8 угловых кубов находятся на 4 шага от решенного, 7 краевых кубов на 6 шагов от решенного, а остальные 7 краевых кубов 3 движутся дальше от решенного, нижние границы оценивают количество ходов до решенного. решенное состояние - max(4, 6, 3) = 6.
ИДА*
Имея структуру куба Рубика и базы данных шаблонов, алгоритм IDA * может быть закодирован. Я решил использовать нерекурсивную реализацию, которая в моем тестировании показала лучшие результаты, чем типичная рекурсивная версия. Он также использует оптимизацию, похожую на поиск лучшего первого, когда конечные узлы сортируются на основе их предполагаемого расстояния до решенного состояния. Таким образом, в первую очередь посещаются состояния куба, которые кажутся наиболее близкими к решенному.
Вот суть этого в псевдокоде, который примерно соответствует C ++.
Фактическая реализация доступна на моем GitHub.
Алгоритм Тистлтуэйта
Оптимальный решатель может занять много времени, чтобы собрать куб, особенно для схваток, для решения которых требуется 18+ ходов. Алгоритм Thistlethwaite значительно быстрее, решая кубики мгновенно. Его также можно реализовать без баз данных шаблонов с использованием дерева решений, которое медленнее, но проще в реализации. В версии 2.2.0 моей программы я использовал дерево решений для реализации алгоритма Тистлтуэйта, но с тех пор усовершенствовал программу для использования баз данных шаблонов. Небольшое предупреждение: реализовать алгоритм Тистлтуэйта с базами данных шаблонов довольно сложно.
Как и в алгоритме Корфа, алгоритм Тистлтуэйта использует IDDFS. Выше было упомянуто, что фактор ветвления кубика Рубика немного больше 13. Есть 18 поворотов, но некоторые пары ходов являются избыточными или коммутативными и могут быть сокращены. Алгоритм Тистлтуэйта работает, перемещая куб из одной «группы» в другую. Каждая последующая группа может быть решена только с помощью подмножества из 18 скручиваний, тем самым уменьшая коэффициент ветвления и количество возможных состояний куба, а также упрощая вычисление для решения.
Первоначальная группа, группа 0, представляет собой любой скремблированный куб. Помните, как было сказано ранее, что каждый кубик края может быть в одной из двух ориентаций. Что ж, оказывается, что кромочные элементы нельзя перевернуть, если не использовать четверть оборота передней и задней граней. (Передняя и задняя грани произвольны - то же самое верно для любых двух противоположных граней, например, левой и правой, передней и задней, или вверх и вниз.) Перемещая куб в состояние, в котором все 12 ребер ориентированы правильно, группа 1, куб может быть собран без использования четверть оборота передней или задней граней. Другими словами, кромочная деталь ориентирована правильно, если ее можно переместить в решенное положение без использования четверти оборота передней или задней граней. В группе 1 коэффициент ветвления уменьшается на 4, потому что куб может быть решен без F, F ’, B или B’ скручиваний.
Затем куб перемещается в состояние, при котором все углы ориентированы правильно. То есть, если куб ориентирован так, что красный центральный куб направлен вверх, то все 8 угловых кубов имеют красные или оранжевые наклейки на верхней или нижней гранях. Кроме того, четыре края перемещаются в правильный фрагмент: передний левый, передний правый, задний левый и задний правый края помещаются в E-фрагмент (слой между передней и задней гранями). Это группа 2. Как только группа 2 будет достигнута, куб может быть собран без четверти оборота левой или правой грани. Это снова снижает коэффициент ветвления на 4, потому что L, L ’, R и R’ больше не нужны.
Для группы 3 все углы перемещаются на правильную орбиту, что означает, что каждый угол может быть перемещен в исходное положение только с поворотом на 180 градусов. Кроме того, каждое ребро перемещается в свой домашний срез, M, E или S, которые являются слоями между левой и правой гранями, верхней и нижней гранями, а также передней и задней гранями соответственно. Из группы 3 куб можно собрать только поворотом на 180 градусов. И снова коэффициент ветвления уменьшается на 4 (U, U ’, D и D’ больше не нужны).
Наконец, достаточно всего 6 поворотов на 180 градусов, чтобы перейти из группы 3 в решенное состояние: U2, F2, L2, R2, B2 и D2. После этого мы воткнем в него вилку, и все будет готово.
Опять же, этот алгоритм может быть реализован с использованием деревьев решений. В этом случае IDDFS используется для перехода от одной группы к другой. При достижении новой группы подмножество из 18 поворотов исключается из поиска. В среднем этот подход занимает около минуты, чтобы собрать куб. В качестве альтернативы можно использовать ряд баз данных шаблонов с одной базой данных шаблонов на группу, где каждая база данных шаблонов предоставляет точное количество ходов для перехода от произвольного состояния куба к следующей группе. Такой подход может решить любую схватку за считанные миллисекунды, но его математика сложна.
Заключительные примечания
На моем GitHub есть таблица, которая показывает, сколько времени требуется для решения различных скремблирования с использованием моей реализации алгоритма Корфа. Моя программа значительно быстрее, чем другие, которые я нашел в Интернете, особенно из-за того, что я использую алгоритм линейного ранжирования. Однако поиск решения по-прежнему занимает довольно много времени.
Также есть таблица, которая показывает размер и максимальные расстояния в каждой группе, используемой в алгоритме Thistlethwaite. Обратите внимание, что моя реализация немного отличается от реализации Thistlethwaite в третьей фазе, и поэтому она решает кубики максимум за 46 поворотов вместо 52.
Большим улучшением было бы использование симметрии. Говоря абстрактно, каждый зашифрованный куб можно отразить несколькими способами. Использование симметрии фактически сжимает базы данных шаблонов и позволяет использовать базы данных с более крупными подмножествами кубов.
Но это темы для другого дня. Надеюсь, вам понравилась статья. Как всегда, если у вас есть какие-либо вопросы или комментарии по поводу статьи или кода, напишите мне, пожалуйста, ниже.
Ссылки и полезные ссылки
Ботто, Бен. Последовательная индексация перестановок: линейный алгоритм вычисления лексикографического ранга. Статья, описывающая ранжирование перестановок более подробно.
Браун, Эндрю. Решатель кубика Рубика. Используется для сравнения скорости. Также используется для проверки оптимальных решений.
Коппин, Бен. Освещенный искусственный интеллект. Разделы о поиске, играх и динамическом программировании особенно актуальны. Это отличная книга об ИИ в целом.
Хайсе, Райан. Теория кубика Рубика. Здесь есть более подробное обсуждение достижимых перестановок и ориентации кубов.
Корф, Ричард Э. Поиск оптимальных решений для кубика Рубика с использованием баз данных шаблонов. Это описывает алгоритм Корфа для решения куба.
Корф, Ричард Э. и др. al. Масштабный параллельный поиск в ширину. Он содержит краткий линейный алгоритм для создания последовательных индексов в базе данных шаблонов с использованием факториальной системы счисления.
Массачусетский технологический институт. Математика кубика Рубика. Статья, в которой рассматриваются некоторые аспекты математики и теории групп, связанных с кубом.
Райдер, Конрад. Обнаружение ориентации края. На этой странице представлен простой алгоритм определения ориентации кромочных элементов.
Rubiks.com. Как собрать кубик Рубика. Простой послойный подход к решению куба человеком.
Scherphuis, Яап. Тистлтуэйт, Морвен. 52-ходовой алгоритм Тистлтуэйта. У Яапа есть обзор алгоритма, а также отсканированное письмо из Тистлтуэйта.
Тейлор, Питер. Индексирование перестановок ребер кубика Рубика. Питер был достаточно любезен, чтобы помочь мне с созданием индексов для 7-краевых баз данных шаблонов, которые являются вариацией кода Лемера с использованием частичных перестановок.
Википедия. Алгоритм поиска *.
Википедия. Поиск лучшего первого.
Википедия. Итерационное углубление A *. Это рекурсивная реализация IDA *.
Википедия. Итеративное углубление в глубину.
Википедия. Код Лемера.
