Двухэтапный алгоритм Косенбы

Общедоступный номер: Rand_cs

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

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

Метафоры метафорами, а ведь абстракции, давайте посмотрим конкретно.

1. Обзор

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

Исходное состояние можно рассматривать какU，R，F，D，L，BЭти 6 основных вращений складываются, и группа, образованная этими 6 вращениями, записывается как $G=\langle U,R,F,D,L,B \rangle$ .

Целевое состояние, определенное Косенбой, определяется толькоU，D，L2，R2，F2，B2Эти 6 видов вращения складываются, и то же самое записывается как $G_1=\langle U,D,L2,R2,F2,B2 \rangle$ .

Ⅰ Свойства целевого состояния

Помните, как определялось направление при подсчете количества состояний в предыдущей статье? Пересматриваем и еще раз пересматриваем:

Ребро имеет 2 состояния, не перевернутое (перевернутое) представлено 0, перевернутое 1,ТолькоF，BВращение слоев может изменить направление.
Угловой блок имеет 3 состояния, нескрученный (скрученный) представлен 0, поворот по часовой стрелке представлен 1, поворот против часовой стрелки представлен 2,ТолькоU，Dвращение слоя不改变ориентация углового блока.

Целевое состояние задаетсяU，D，L2，R2，F2，B2Эти 6 вращений генерируются, и эти 6 вращений не вызывают изменений в направлении угловых и краевых блоков. так какНезависимо от того, как вы поворачиваете, слой U или D, принадлежащий угловому блоку, всегда находится в слое U или слое D, поэтому направление не меняется..Это не приведет к изменению направления граничного блока, потому что только вращение F и B вызовет изменение направления граничного блока, а непрерывное вращение, как F2 дважды, переворачивание и затем реверсирование граничного блока эквивалентно чтобы не переворачиваться, поэтому направление краевого блока не изменится.Эти 6 вращений не приведут средний блок к слою U или слою D, поэтому блок в среднем слое может быть только в среднем слое..

Таким образом, свойства целевого состояния можно резюмировать следующим образом:

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

Ⅱ Алгоритм поиска

Алгоритм поиска, используемый в двухэтапном алгоритме Козенбы, представляет собой алгоритм IDA*, который представляет собой итеративный алгоритм поиска с углублением, и оба этапа используют алгоритм IDA*..

Что касается IDA*, то есть еще один алгоритм A*, с которым вы, возможно, не знакомы, и в нем нет ничего загадочного, так что кратко о нем. A* — это широкий поиск с эвристической функцией. IDA* — это глубокий поиск с ограничением глубины поиска и эвристической функцией. До сих пор, пожалуйста, обратитесь к Baidu CSDN для подробного объяснения.

Как правило, широкий поиск может найти кратчайший путь, а глубокий — нет.Хотя IDA* использует глубокий поиск, он имеет ограничение по глубине и также может найти кратчайший путь.. Например, если я установил глубину поиска на 1, если я не нашел его, я устанавливаю на 2 для повторного поиска, и тогда я могу получить кратчайший путь.

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

ответ отрицательный,Поскольку оптимальное решение, полученное на втором этапе, относительно первого этапа,Например

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

Так как же ее решить, как получить лучшее или даже оптимальное решение? Также, как показано выше,Мы углубляем глубину поиска первого этапа.Хотя путь первого этапа становится длиннее, второй этап может найти более короткий путь, так что они могут быть лучше вместе.. Таким образом, шаг за шагом всегда можно найти оптимальное решение, т.Двухэтапный алгоритм Косенбы может не получить оптимальное решение за один поиск, но пока ему дается время, он точно сможет найти оптимальное решение. Однако алгоритм Косенбы не используется для поиска оптимального решения, цель состоит в том, чтобы найти множество относительно оптимальных решений за короткое время.

У вас должно быть очень интуитивное и базовое понимание двухэтапного алгоритма Косенба.Если непонятно, приведем очень яркий пример для волшебного друга. Формула сокращения CFOP, которую мы обычно используем, после F2L должна быть OLL, PLL, правильно, если мы обычно следуем формуле CFOP, оптимальное решение получается на этих этапах, и комбинация также лучше. Но если мы проведем еще несколько шагов в F2L, то можно перейти к O или даже к P, что сэкономит много последующих шагов поворота и даст лучшее решение.

Приведенный выше пример с кратчайшим отрезком между двумя точками — это всего лишь метафора, реальная ситуация немного отличается.Как было сказано ранее, двухэтапный алгоритм заключается в том, что катер плывет сначала в особую акваторию, а затем в пункт назначения, однако в некоторых случаях кратчайший путь может вообще не проходить через эту акваторию. сначала через специальную акваторию, естественно придется найти оптимальное решение. Значит, это противоречит вышесказанному? Ни,Состояние восстановления на самом деле является одним из целевых состоянийда такЕсли обнаружено, что после решения этапа 1 он восстановлен, а шаги, необходимые для этапа 2, сведены к 0, то это оптимальное решение.. Как и после прохождения F2L, я с удивлением обнаружил, что прыжок O и P восстановлены.

Вышеприведенное представляет собой обзор двухэтапного алгоритма Косенбы, который должен быть прост для понимания. Далее подробно алгоритм, их довольно много, заинтересованные друзья могут посмотреть, этого наверное достаточно для понимания этого шага, если вам не интересен кубик Рубика.

Однако, если вы изучаете компьютер, алгоритм сокращения кубика Рубика все же стоит посмотреть. Я не знаю, решали ли вы когда-нибудь восьмизначную задачу.Решение кубика Рубика по сути тоже самое, что и решение восьмизначного числа.Слово головоломка также используется в английском языке, но количество состояний кубика Рубика намного больше, чем у восьмизначного числа, и у квадрата кубика Рубика есть много специальных свойств, которые можно использовать для оптимизации алгоритма, давайте рассмотрим его подробно:

2. Дайте определение кубику Рубика

Иерархия блоков

Чтобы определить кубик Рубика, мы должны сначала пометить основные элементы диагонального блока и реберного блока, которые можно пометить следующим образом:

Код представлен следующим образом:

typedef enum {URF,UFL,ULB,UBR,DFR,DLF,DBL,DRB} Corner;
typedef enum {UR,UF,UL,UB,DR,DF,DL,DB,FR,FL,BL,BR} Edge;

После маркировки диагональных ребер кубик Рубика можно определить с точки зрения блока:

struct corner_o
{	Corner c;    //角块
	char o;      //方向
};
struct edge_o
{	Edge e;      //棱块，也就是边
	char o;      //棱块方向
};
struct CubieCube   //一个魔方状态
{	
	struct corner_o co[8];   //8个棱块
	struct edge_o eo[12];    //12个角块
};

Как сохранить состояние куба? Например $co[URF] = \{URF,0\}$ Указывает блок URF, хранящийся в местоположении URF, с направлением 0. $co[URF] = \{UFL,1\}$ Указывает блок UFL, хранящийся в местоположении URF, с направлением 0 .

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

Ⅱ Уровень координат (индекс)

Название является дословным переводом с английского имени,Этот уровень просто заключается в том, что нам нужно закодировать/хешировать состояние куба и присвоить уникальный номер различным состояниям для идентификации, в основном используемым в качестве индекса таблицы преобразования и таблицы обрезки.. Конечно, на самом деле невозможно закодировать различные полные состояния кубика Рубика, слишком много состояний, чтобы быть реалистичными. ноКодирование части состояния кубика Рубика, полное состояние кубика Рубика состоит из 8 угловых блоков, 12 краевых блоков и их направлений, и алгоритм состоит в том, чтобы разделить их, например, положение некоторых краевых блоков, положение угловых блоков, направление угла блоки, направление краевых блоков и т. д., кодируют их хэши, поэтому число намного меньше.

Следовательно, он предназначен в основном для кодирования двух индикаторов положения и направления, а метод кодирования в основном использует следующие три:

① Направление

Направление делится на направление углового блока и направление краевого блока. Они похожи. Здесь в качестве примера используется направление углового блока. Если есть расположение углового блока с направлением, как показано ниже:

Первая строка представляет позицию, а вторая строка представляет угловой блок, хранящийся в этой позиции, и его ориентацию, закодированную с использованием следующего метода:

$2\times3^6+0\times3^5+0\times3^4+1\times3^3+1\times3^2+0\times3^1+0\times3^0$

Он должен быть интуитивно понятным и простым для понимания, поскольку при определении направления 7 угловых блоков также определяется направление последнего углового блока, поэтому нет необходимости кодировать направление последнего углового блока. код показывает, как показано ниже:

short int idx_co = 0;    //corner orientation index，角块方向编码
for (Corner c = URF; c < DRB; c++) 
    idx_co = 3 * idx_co + co[c].o;

② Упорядочить

Количество перестановок часто используется для изменения положения.В течение этого периода мы можем использовать различные схемы, такие как расположение 8 угловых блоков, расположение 6 сторон и т. д. Это представления состояния кубика Рубика. куб, и нам нужно их закодировать.Метод кодирования имеет имя, называемоеРасширение Кантора, также непосредственно посмотрите на пример, иллюстрирующий метод кодирования расширения Кантора, если 8 угловых блоков расположены следующим образом:

Первая строка представляет позицию, а вторая строка представляет собой угловой блок, размещенный в соответствующей позиции.Из метки мы знаем, что наши блоки имеют разные размеры: $URF<UFL<ULB<UBR<DFR<DLF<DBL<DRB$ Итак, третья строка говоритБлок слева имеет несколько блоков больше, чем он сам, например, блок URF (посмотрите на вторую строку, первая строка представляет позицию, а вторая строка — блок, хранящийся в этой позиции) слева 3 блока, все они больше самих себя, поэтому значение третьей строки равно 3; блок UBR, 7 блоков слева и 4 блока больше, чем он сам, поэтому значение равно 4. Блок DFR находится в первой позиции, а слева блоков больше нет, поэтому первый блок при кодировании не учитывается.

Конкретная кодировка:

$1\times1!+1\times2!+3\times3!+0\times4!+1\times5!+1\times6!+4\times7!$

Эта формула соответствует третьей строке выше, ее следует хорошо понимать и объяснять не буду, код описывается следующим образом:

int idx_cp = 0;   //corner position index 角块位置编码
for (int i = DRB; i > URF; i--){
    int s = 0;
	for (int j = i - 1; i >= DRF; j--)
        if(co[j] > co[i]) s++;
    idx_cp = (idx_cp + s) * i;
}

③ Комбинация

Количество комбинаций иногда используется для изменения положения, и количество комбинаций необходимо закодировать.На этапе 1 мы будем использовать количество комбинаций для четырех краевых блоков в среднем слое.Целевое состояние этапа 1 требует, чтобы граничные блоки, изначально находившиеся в среднем слое, находились в среднем слое, поэтому для вычисления состояния положения граничного блока на этапе 1 нам нужно учитывать только 4 края среднего уровня, есть $12\times11\times10\times9 = 11880$ состояние, но между 4 краями среднего слоя нет требований к положению, поэтому оно также разделено по их собственному позиционному расположению $4!=24$ , всего 495 состояний, и это комбинаторное число $C^4_{12}$ , мы хотим закодировать эти 495 состояний:

Первая строка представляет местоположение, а вторая строка представляет сохраненный блок.Учитывается только расположение 4 блоков в среднем слое. $FR\ FL\ BL\ BR$ 4 ребра, потому что 4 ребра среднего слоя не имеют требований к расположению, поэтому они заменены на X, указывая на то, что они одинаковы. В третьей строке указано количество комбинаций, соответствующих X, а во втором примере показано, как кодировать:

$C_{11}^4+C_{10}^3+C_9^2+C_8^1$

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

int idx_slice = 0, x = 0   //中间层 4 个棱块状态的编码
for(int i = BR; i >= UR; i--)   //从后往前
    if(edge[i] >= FR && edge[i] <= BR)   //判断是否是中间层 4 条棱边   
        idx_slice += c_nk(11 - j, x + 1) //c_nk为，n选k的组合数值
        x += 1     //x加1，x就是上图括号里面第二个值

Значение номера комбинации используется напрямую, поэтому напишите функцию для нахождения номера комбинации заранее, n выберите k, если $k>n$ Требование равно 0, и при написании функции можно судить о следующем. Приведенный выше код также может быть представлен другими комбинированными числами 8. Если вам интересно, вы можете попробовать это сами.

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

В-третьих, определите вращение

Ⅰ Смена позиции

Смотрим на первое упомянутое $\{0,1,2,3\}$ Проблема перестановки , если есть две перестановки, программа представлена массивом следующим образом:

int a[4] = {0, 1, 2, 3};
int b[4] = {1, 2, 3, 0};
int c[4] = {};

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

b Что представляет этот массив? Конечно, он может представлять собой расположение: 1 в бите 0, 2 в бите 1, 3 в бите 2 и 0 в бите 3.

Это просто общее понимание, что еще оно означает?Он может представлять само преобразование, что означает, что элемент в позиции 0 заменяется элементом в позиции 1, элемент в позиции 1 заменяется элементом в позиции 2, элемент в позиции 2 заменяется элементом в позиции 3, а элемент в позиции 3 заменяется элементом в позиции 3. заменяется битовым элементом 0. Использование этого альтернативного угла для описания преобразования имеет очень интуитивное отношение равенства.Например, элемент в позиции 0 заменяется элементом в позиции 1, что можно записать как $a[0]=a[1]$ .

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

В частности, если количество элементов, то есть диапазон значений нижнего индекса, равен диапазону значений элемента, мы можем легко определить на нем замкнутое преобразование.. Например, количество элементов в приведенном выше расположении равно 4, поэтому диапазон значений нижнего индекса равен 0.~~3, а значение самого элемента тоже 0~~3 Эти 4 числа. В этом случае очень удобно определить операции изменения, такие как выполнение преобразования b над перестановкой a, а полученный результат сохраняется в перестановке c, и выполняются следующие операции:

for(int i = 0; i < 4; i++)
    c[i] = a[b[i]];

Подводя итог, если дано расположение, если оно рассматривается как преобразование, то не только нижний индекс указывает на положение, но и его элементы также указывают на положение. Например, b[2] = 3 означает, что элемент в позиции 2 заменен элементом в позиции 3..

После понимания вышеизложенного определение вращения кубика Рубика легко решается. Никакой новой структуры данных не требуется. Состояние кубика Рубика, определенное в предыдущем разделе, можно преобразовать за один шаг, но мы интерпретируем его по-разному для разных нужд.

Ⅱ Изменение направления

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

Например, выполните операцию F в состоянии a. Как упоминалось ранее, операцию вращения также можно рассматривать как состояние. Мы записываем операцию F как b, а полученный результат как ab, взяв положение URF в качестве примера для проиллюстрировать.

F поворачивается так, что элементы слота URF заменяются элементами слота UFL, что можно записать как

$ab.co[URF].c = a.co[UFL].c = a.co[F(URF)].c = a.co[b.co[URF]].c$

Но значение направления не может быть представлено замещением, т. е. $ab.co[URF].o \neq a.co[UFL].o$ , F поворачивается вниз,Элемент в положении UFL перемещается в положение URF и поворачивается по часовой стрелке., поэтому для вращения F направление должно измениться следующим образом:

$ab.co[URF].o = (a.co[UFL].o + 1)\ mod \ 3 = (a.co[UFL].o + b.co[URF].o)\ mod \ 3=(a.co[b.co[URF]].o + b.co[URF].o)\ mod \ 3$

Направление здесь немного закруглено. Вы можете найти кубик Рубика и перевернуть его, чтобы смоделировать его. Физическая сущность должна быть хорошо понята, главным образом потому, что она немного закруглена, когда выражается на языке программирования.

Ⅲ Базовая ротация

Таким образом, мы должны быть в состоянии легко написать определение базового вращения, давайте возьмем пример F :

const cubieCube basicMoveF = {{{UFL,1},   //URF槽的元素被UFL槽的元素替代，且顺时针扭转，方向加1
    {DLF,2},{ULB,0},{UBR,0},{URF,2},{DFR,1},{DBL,0},{DRB,0}},
	  {{UR,0},{FL,1},{UL,0},{UB,0},{DR,0},{FR,1},
	  {DL,0},{DB,0},{UF,1},{DF,1},{BL,0},{BR,0}}};

Ⅳ Функция вращения

Вращение делится на вращение углового блока и вращение краевого блока, поэтому код выглядит следующим образом:

CubieCube cubeMove(CubieCube cc, int m){ //cc 上应用转动m
	  CubieCube ccRet;
	  cornerMultiply(&cc, &basicMove[m], &ccRet); //basicMove是基本转动数组，元素如上小节的基本转动
	  edgeMultiply(&cc, &basicMove[m], &ccRet);
	  return ccRet;
};

Эта функция представляет собой инкапсуляцию функций вращения углового блока и вращения краевого блока.В качестве примера возьмем функцию вращения углового блока:

void cornerMultiply(const CubieCube *a, const CubieCube *b, CubieCube *ab){
	  for (Corner crn = URF; crn <= DRB; crn++){
		    ab->co[crn].c = a->co[b->co[crn].c].c;       //角块
		    ab->co[crn].o = (a->co[b->co[crn].c].o + b->co[crn].o) % 3   //角块方向
        /*********************/
    }
}

В отличие от исходной программы Coxianba, исходная программа также имеет дело с зеркалированием и другими ситуациями.Описанный выше угол должен рассматривать a как состояние кубика Рубика, а b как преобразование, но также может рассматривать a как преобразование, тогда ab эквивалентно сложной операции, по той же причине, но понимание угла отличается просто.

Ⅴ Поворотный стол

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

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

unsigned short int twistMove[Ntwist][Nmove];   //Ntwist=3^7-1, Nmove=18

Здесь используется уровень координат, определяемый состоянием кубика Рубика, и он используется в качестве индекса. Приведите пример, иллюстрирующий смысл приведенного выше двумерного массива, если есть $twistMove[a][U] = b$ , что указывает на то, что в состоянии a выполняется операция U для получения состояния b. a, b — два числа, которые однозначно определяют направление угловых блоков кубика Рубика.

Инициализация этого двумерного массива также очень проста, просто посмотрите на код:

void initTwistMoveTable(){    //初始化角块方向转动表
    CubieCube a, b;
    int i,j,m;
    for (int i = 0;i < NTWIST; i++){     //枚举方向状态
        CubieCube a = twist2cube(i);     //坐标层次->块层次
        for (int j = U; j <= B; j++){    //6种基本转动
            for(int k = 0; k < 3; k++){  //基本转动的3种方向，如U,U2,U'，分别对应90°，180°，270°
                cornerMultiply(&a, &basicCubeMove[j], &b);
                twistMoveTable[i][j * 3 + k] = get_twist(b);   //变化后的状态从块层次->坐标层次
            }
            cornerMultiply(&a, &basicCubeMove[j], &b); //再转一次，返回原状态
        }
    }
}

4. Симметрия

Кубик Рубика — очень симметричный объект, и мы можем использовать симметрию, чтобы уменьшить накладные расходы во времени и пространстве.

Симметричная форма имеет 4 основных состояния, исходное состояние, только изменение цвета, только изменение положения, зеркальное отображение.

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

Давайте посмотрим на пример разных цветов в одной и той же позиции и посмотрим на эквивалентное состояние, полученное после изменения исходного состояния:

Если выполнить операцию А (последовательность вращения) над кубиком Рубика в восстановленном состоянии, то получится следующее состояние:

Мы хотим получить его эквивалентное состояние и выполнить следующие операции: состояние восстановления сначала поворачивается на 90° против часовой стрелки вокруг оси UD, затем выполняется операция A и, наконец, поворачивается на 90° по часовой стрелке вокруг оси UD.

来源科先巴的个人网站

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

Ⅰ Преобразование симметрии

① Базовая трансформация

Некоторые из приведенных выше эквивалентных форм получаются с помощью симметричного преобразования. Существует 48 форм преобразования для каждого состояния плюс само себя. Вообще говоря, каждое состояние также имеет 48 эквивалентных форм, и все они состоят из 4-х "Базовая симметрия" состоит из:

S_U4: Поворот на 90° вокруг оси UD, 4 типа
S_F2: Поворот на 180° вокруг оси FD, 2 типа
S_URF3: Повернуть на 120° вокруг URF углового блока, 3 типа
S_LR2: Зеркало о слое LR, 2 типа

вместе $4\times2\times3\times2=48$ своего рода

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

const CubieCube basicSymCube[4] =
{
	{{{URF,1},{DFR,2},{DLF,1},{UFL,2},{UBR,2},{DRB,1},{DBL,2},{ULB,1}},
	{{UF,1},{FR,0},{DF,1},{FL,0},{UB,1},{BR,0},
	{DB,1},{BL,0},{UR,1},{DR,1},{DL,1},{UL,1}}},//S_URF3
	{{{DLF,0},{DFR,0},{DRB,0},{DBL,0},{UFL,0},{URF,0},{UBR,0},{ULB,0}},
	{{DL,0},{DF,0},{DR,0},{DB,0},{UL,0},{UF,0},
	{UR,0},{UB,0},{FL,0},{FR,0},{BR,0},{BL,0}}},//S_F2
	{{{UBR,0},{URF,0},{UFL,0},{ULB,0},{DRB,0},{DFR,0},{DLF,0},{DBL,0}},
	{{UB,0},{UR,0},{UF,0},{UL,0},{DB,0},{DR,0},
	{DF,0},{DL,0},{BR,1},{FR,1},{FL,1},{BL,1}}},//S_U4
	{{{UFL,3},{URF,3},{UBR,3},{ULB,3},{DLF,3},{DFR,3},{DRB,3},{DBL,3}},
	{{UL,0},{UF,0},{UR,0},{UB,0},{DL,0},{DF,0},
	{DR,0},{DB,0},{FL,0},{FR,0},{BR,0},{BL,0}}} //S_LR2
};

Инициализация 48 операций симметричного преобразования также очень проста.Четыре цикла for используются для вызова функции умножения для выполнения составных операций, а полученные результаты заносятся в массив symCube[48].Повторяющиеся операции здесь не повторяются.

Обратите внимание на приведенное выше зеркальное преобразование и добавьте 3 ко всем определенным изменениям направления углового блока, то есть значение зеркального направления углового блока равно $[3,5]$ .

② Обратное преобразование

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

Как получить соответствующее обратное преобразование? В теории групп составная операция двух элементов, обратных друг другу, равна унитарному элементу, что эквивалентно умножению двух чисел, обратных друг другу при умножении, на 1, а в кубике Рубика восстановление состояние состоит в том, что унитарный элемент - это 1 . Таким образом, нам нужно всего лишь выполнить составные операции два на два над 48 преобразованиями, чтобы увидеть, достигает ли результат восстановленного состояния.

init inv_idx[48] -1;  //初始化为-1，表示每种对称变换的逆变换
for(i = 0; i < 48; i++){
    for(j = 0; j < 48; j++){
        CubieCube cc = multiply(symCube[i], symCube[j]);  //两种变换相乘
        if (cc == identity)    //如果结果等于幺元还原状态
            inv_idx[i] = j;    //填数组，对称变换i的逆变换是j
    }
}

II Эквивалент

Для приведенных выше 48 операций симметричного преобразования мы записываем как $S[48]$ , представляющий собой массив symCube[48],Если есть два состояния, А и В, если есть $A=S[i]BS[i]^{-1}$ , это, $S[i]^{-1}AS[i]=B$ , мы считаем A и B эквивалентными. Является ли этот способ записи точно таким же, как и аналогичное преобразование матриц?Они по сути одинаковы, так что вам действительно нужно изучать математику.

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

$\begin{array}{1} 0&A0&A1&A2&... \\ 1&B0&B1&B2&... \\ 2&C0&C1&C2&... \\...&...&...&...&... \end{array}$

Поэтому для каждого состояния нам нужно только записать, к какому набору (номер строки) оно принадлежит и используемое симметричное преобразование (номер столбца).Такой набор называется классом эквивалентности. Таким образом, можно сэкономить много места и времени, поскольку сохраняется меньше информации и выполняется поиск в меньшем пространстве состояний. В двухэтапном алгоритме Косенбы ось UD остается неизменной, поэтому используются только 16 преобразований симметрии.

Добавьте состояние, принадлежащее классу эквивалентности y, используя преобразование симметрии i, тогда мы можем использовать новые координаты $y\times16 + i$ для описания исходного состояния. Но не каждый класс эквивалентности имеет 16 различных состояний, то есть не каждое состояние имеет 16 различных симметричных состояний. Например, существуют классы эквивалентности y и симметричные преобразования i, j, $y\times16+i$ и $y\times16+j$ Можно описать одно и то же состояние.

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

init idx2class[Nindex] -1   //初始化为-1，idx属于哪一个等价类
init idx2sym[Nindex] -1     //初始化为-1，idx使用的哪一种对称变换
init class2rep[NCLASS] -1   //初始化为-1，该等价类的代表
    
classidx = 0;               //等价类标号
CubieCube cc = get_cube();  //获取魔方初始状态的块层次表示

for(idx = 0; idx < Nindex; i++){    //魔方部分状态的坐标层次表示，比如说角块方向Nindex = Ntwist = 2187
    if(idx2class[idx] == -1){       //还没填充
		idx2class[idx] = classidx;   //填
        idx2sym[idx] = 0;            //等价类里面的第一个元素，使用的对称变换为第一种0
        class2rep[classidx] = idx;   //等价类里面的代表，idx最小的那个作为代表
    }
    else 
        continue;     //已填，跳过        
    
    /**上面是处理等价类中的第一个元素，这里直接应用16种对称变换来处理其他元素**/
    for(sym = 0; sym < 16; sym++){  
        idx_new = idxSymTable[idx][sym];    //对称变换表，在idx上应用对称变换sym得到新坐标idx_new
        if(idx2class[idx_new] == -1){
            idx2class[idx_new] = classidx;
            idx2sym[idx_new] = sym;
        }
    }
    classidx++;   //填完当前等价类，加一准备填下一个
}

Ⅲ Таблица преобразования симметрии

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

int moveSymTable[NMOVE][16];       //对每一种转动m做 S[i]*m*S[i]^-1
int twistSymTable[NTWIST][16];     //对角块方向twist做 S[i]*twist*S[i]^-1

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

void initTwistConjugate(){
    CubieCube cc,ccSym,ccTmp;
    int i,j;
    for (int i = 0;i < NTWIST; i++){
        cc = twist2cube(i);     //坐标层次转块边层次
        for (int j = 0;j < 16; j++){
            cornerMultiply(&symCube[i], &cc, &ccTmp);    //S[i]*cc
			cornerMultiply(&ccTmp, &symCube[inv_idx[i]], &ccSym);	//S[i]*cc*S[i]^-1
            twistSymTable[i][j] = get_twist(ccSym);   //结果转为坐标层次
        }	
    }	
}

В названии исходной программы используется слово conjugate. Conjugate, здесь я использую Sym непосредственно для иллюстрации, я подумал, что это может быть более интуитивно понятным.

5. Обрезка

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

Для двух этапов может быть несколько таблиц сокращения, и каждый этап должен выбрать наибольшее число в качестве минимального количества шагов, необходимых для достижения целевого состояния/состояния восстановления., например, таблица 1 сообщает мне, что текущему состоянию требуется не менее 5 шагов для достижения целевого состояния, а таблица 2 сообщает мне, что необходимо не менее 6 шагов, тогда 6 принимается за минимально необходимое количество шагов. Это все еще хорошо понятно, Таблица 1 и Таблица 2 описывают часть состояния кубика Рубика соответственно, и каждая часть состояния достигает целевого состояния до достижения целевого состояния, поэтому следует выбирать наибольшее из них.это тоже ИДАв алгоритме $h(n)$ эта функция*.

Ⅰ Создайте таблицу обрезки

Минимальное количество шагов, которое может пройти таблица обрезки до целевого состояния? Разве это не удивительно, в этом нет ничего удивительного,Это результат насильственного поиска. Установите глубину целевого состояния на 0, а затем выполните 18 операций поворота целевого состояния, чтобы получить глубину узла состояния первого слоя равной 1, а затем поверните каждое состояние первого слоя, чтобы получить узел состояния второго слой, глубина равна 2.... Подробности см. в следующем псевдокоде:

init pruneTable1[Nindex] -1  //初始化所有元素为 -1
depth = 0                    //初始深度为 0
pruneTable[0] = 0;           //本就是目标状态，所以深度/所需步数为0
done = 1;                    //已填了一个初始状态
while done < Nindex:         //表还没填完
    for i = 0 to Nindex - 1
        if pruneTable[i] == depth   
            for each m in Nmove    //对每个状态进行18种转动操作
                index = moveTable[i][m]  //根据转动表得出转动后的状态坐标值
                if pruneTable[index] != -1    //如果还没填表，填
                    pruneTable[index] = depth + 1  //深度加 1，表下一层
                    done++          
    depth++    //填完一层结点，深度加 1

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

Ⅱ Навыки хранения

Если известно, насколько далеко начальное состояние от целевого состояния, а затем выполняется каждый шаг, расстояние от целевого состояния либо увеличивается на 1, не изменяется, либо уменьшается на 1. В этих трех случаях мы можем вычислить состояние после поворота Расстояние от цели Как далеко находится состояние. Так что на самом деле нам нужно всего 2 бита в таблице обрезки, чтобы сохранить значение фактического расстояния по модулю 3. В соответствии с расстоянием текущего состояния и значением mod3, найденным в таблице обрезки, можно рассчитать расстояние от повернутого состояния до целевого состояния. Это значительно сокращает использование пространства.

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

int get_depth_phase1(CubieCube cc){
    index = get_index(cc);      //得到初始状态的坐标值
    depth_mod3 = pruneTable[index];  //初始状态到目标状态的mod3距离
    depth = 0;                  //初始化0
    while index != SOLVED:      //若没到目标状态，循环
        if(depth_mod3 == 0) depth_mod3 = 3;   //mod3为0，表3倍数，设为3
        for each m in Nmove             //对于每个转动
            index_new = moveTable[index][m];
        	if (pruneTable[index1] == depth_mod3 - 1) //如果转动后距离更近
                depth++;          //实际距离加 1 
    			index = index1;   //更新坐标索引值
                depth_mod3--;     //mod3距离减 1
    			break;            //找到一个举例目标转动更近的转动，跳出循环
    return depth;
}

По псевдокоду должно быть видно приблизительное значение.Поскольку то, что мы нашли из таблицы сокращения, является расстоянием по модулю 3, расстояние по модулю 3 циклически уменьшается с 3 до 0, а фактическое расстояние увеличивается с 0 до тех пор, пока не достигнет целевого состояния. Поскольку каждый раз, когда мы обновляем два значения расстояния, нам нужно поворачиваться ближе к целевому состоянию, поэтому окончательная фактическая глубина расстояния должна быть минимальным шагом, требуемым от начального состояния до целевого состояния.. Это вроде бы решило кубик Рубика, но это не так, потому что индекс — это только индекс координат состояния кубика Рубика, поэтому значение, вычисляемое этой функцией, используется только как начальный показатель.

6. Этап 1

Ⅰ Используемые координаты

На первом этапе используются три координаты:

twist, направление углового блока, диапазон значений $[0,2186]$
flip, направление края, диапазон значений $[0,2047]$
slice, состояние выбора 4 краев среднего слоя, диапазон значений $[0,494]$

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

Ⅱ Оптимизация координат

Но на самом деле Coxianba выполнил оптимизацию и на самом деле определяет не срез, а координату slice_sorted. Эта координата является расширенной версией среза. Разве срез не учитывает положение четырех краев среднего слоя? Если вы хотите рассмотреть это slice_sorted. Диапазон значений $[0,11879]$ . Но, конечно, когда мы на самом деле его используем, мы по-прежнему используем slice, а slice — это индикатор нашего первого этапа, то есть делим slice_sorted на 24 и используем снова. Почему так сложно не определять срез напрямую? Поскольку второй этап также использует эту координату slice_sorted, она обрабатывается так для удобства унификации, но, конечно, до тех пор, пока вы будете ясны и не запутаетесь, независимо от того, какую из них вы используете, или даже другие координаты.

Эта координата не является ни номером комбинации, ни номером перестановки, как ее закодировать?Хотя две координаты разные, они похожи. $12\times11\times10\times9=\frac{A^{12}_{12}}{C^4_{12}}$ , поэтому эту координату также можно представить методом кодирования перестановки и комбинации.

Ⅲ Расчет слияния/индекса координат

flip и slice объединяются в координату flipslice, $flipslice=2048 \times slice + flip$ , Диапазоны $[0,(2048\times495-1)]$ .

Однако из-за симметричного характера flipslice может быть заменен classidx и sym, диапазоны значений которых $[0, 64429]$ , $[0,15]$ . $64430\times16 > 2048 \times 495$ , который показывает, что не каждый класс эквивалентности имеет 16 различных симметричных состояний.

classidx, sym объединяются с поворотом, чтобы сформировать координату, временно называемую sym_flipslice_twist, диапазон значений $[0,64430\times2187-1]$ Эта координата является индексом таблицы обрезки этапа 1..

$sym\_flipslice\_twist = 2187\times classidx + twistSymTable[twist][sym]$ Зачем так считать? Нет причин, Косенба рассчитал так, или можно рассчитать по-другому, это индексное значение, хеш-значение, главное, чтобы его можно было отличить одно за другим.

IV Алгоритм поиска

Было сказано, что алгоритм поиска использует IDA*, нечего сказать, просто посмотрите на псевдокод:

main:       //主线程
	CubieCube cc = get_cube();   //得到输入的魔方
	dist = get_depth_phase1(cc); //获取阶段1需要的最少步数
	twist = get_twist(cc);       //获取坐标twist
	flip = get_flip(cc);         //获取坐标flip
	slice_sorted = get_slice_sorted(cc);    //获取坐标slice_sorted
	for(togo1 = dist; togo1 <= 20; i++)    //IDA* 限制搜索深度体现点，深度不能超过togo1
        search1(twist, flip, slice_sorted, dist, togo1); //阶段一搜索

void search1(twist, flip, slice_sorted, dist, togo1){  //深搜
	if(togo1 == 0)   //阶段一已解决
    /**省略后面讲,大概就是满足一定条件后search2()**/
    else{
        for each permitted m in MOVE{    //对每个允许的转动
        	flip_new = flipMoveTable[flip][m];     //获取新flip
            twist_new = twistMoveTable[twist][m];  //获取新twist
            slice_sorted_new = sliceSortedMoveTable[slice_sorted][m];  //获取新slice_sorted
            
            flipslice = 2048 * slice_sorted_new / 24 + flip_new;  //计算flipslice，slice_sorted除以24再用
            classidx = flipslice2class[flipslice]; //flipslice属于哪个等价类
            sym = flipslice2sym[flipslice];   //记录使用的哪种对称变换
            
            sym_flipslice_twist = 2187 * classidx + twistSymTable[twist][sym];  //计算索引
            
            dist_new_mod3 = get_flipslice_twist_depth3(sym_flipslice_twist);  //查阶段一剪枝表，获取mod3距离
            dist_new = get_real_dist(dist_new_mod3);   //mod3距离转实际距离
            
            if (dist_new > togo1)   //最少需要步数大于允许步数，剪枝
                continue;
            
            maneuver1.append(m);   //做选择，m加进解法的转动序列
            search1(twist_new, flip_new, slice_new, dist_new, togo1 - 1);  //下一层搜索
            maneuver1.pop();       //撤销选择，尝试兄弟结点或回溯
        }
    } 	
}

Семь, второй этап

Ⅰ Используемые координаты

corners, расположение угловых блоков, 8, диапазон значений $[0,40319]$
ud_edges, расположение краев слоя U и слоя D, 8, диапазон значений $[0,40319]$
slice_sorted, расположение краев среднего слоя, 4, диапазон значений $[0,23]$

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

Ⅱ Индекс объединения/вычисления координат

конусы, диапазон значений $[0, 40319]$ , который можно заменить на classidx и sym из-за симметрии, а диапазоны значений соответственно $[0, 2767]$ , $[0,15]$ , 2768 классов эквивалентности, а также потому, что не каждый класс эквивалентности имеет 16 различных состояний, поэтому $2768\times16>40320$

classidx, sym, ud_edges объединяются в одну координату, временно называемую sym_corners_ud_edges, диапазон значений $[0,40320\times2768-1]$ Эта координата является индексом таблицы сокращения этапа 2.. $sym\_corners\_ud\_edges = 40320\times classidx + ud\_edgesSymTable[ud\_edges][sym]$

углов, slice_sorted объединяется с другой координатой, временно называемой angles_slice_sorted, диапазон значений $[0,40320\times24-1]$ ,ЭтотКоордината — это индекс другой таблицы обрезки на втором этапе.. $corners\_slice\_sorted = 24\times corners+slice\_sorted$

Ⅲ Алгоритм поиска

void search2(corners, ud_edges, slice_sorted, dist, togo2){  //深搜框架
    if(togo2 == 0)     //阶段二已解决
        maneuver = maneuver1 + maneuver2;   //合并两阶段的解法
    	if(len(maneuver) < shortest)
            shortest = len(maneuver)      //记录最短解法的长度
    else{
        for each permitted m in MOVE{     //对每个允许的转动
            corners_new = cornersMoveTable[corners][m];     //获取转动后的corners
            ud_edges_new = ud_edgesMoveTable[ud_edges][m];  //获取转动后的ud_edges
            slice_sorted_new = sliceSortedMoveTable[slice_sorted][m]; //获取转动后的slice_sorted
            
            classidx = corner2classidx[corners_new];    //获取corners的代表
            sym = corner2sym[corners_new];              //获取使用的对称变换
            
            sym_corners_ud_edges = 40320 * classidx + ud_edgesSymTable[ud_edges][sym]; //计算索引
            corners_slice_sorted = 24 * corners + slice_sorted;   //计算索引
            
            dist_new_mod3 = get_corners_ud_edges_depth3(sym_flipslice_twist);  //查剪枝表，获取转动后的mod3距离
            dist_new = get_real_dist(dist_new_mod3);    //mod3距离转成实际距离
            another_dist = corners_slice_sorted_pruneTable[corners_slice_sorted]  //查另一个剪枝表，查表，获取距离
                
            if(max(dist_new, another_dist) >= togo2) //两个距离指标，如果最大的那个大于允许的步数，剪枝
                continue;
            
            maneuver.append(m);      //做选择，m加进阶段二的解法
            seach2(corners_new, ud_edges_new, slice2_new, dist_new, togo2 - 1);  //搜索下层结点
            maneuver.pop();          //撤销选择，尝试兄弟结点或回溯
        }
    }
}

Восемь, идеальное дополнение

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

Ⅰ Стадия совершенства 1

void search1(twist, flip, slice, dist, togo1){  //深搜
	if(togo1 == 0){   //阶段一已解决
        /***计算阶段二需要的参数***/
        corners = get_corners(cc);    //获取初始状态的corners坐标
        for m in maneuver1            //根据阶段一的解法，转动更新corners
            corners = cornersMoveTable[corners][m];
        
        //计算阶段二最多允许的步数，目前的最优解法的长度减去当前阶段一已花的步数，且阶段二用的步数不能超过11-1=10步
        //阶段二的步数下降的很快，通常不超过9步
        togo2_limit = min(shortest - len(maneuver1), 10);   
        corners_slice_sorted = 24 * corners + slice_sorted;   //计算索引
        if(corner_slice_sorted_pruneTable[corners_slice_sorted] >= togo2_limit) //查表剪枝
            return
        
        ud_edges = get_ud_edges(cc);  //获取初始状态的ud_edges坐标
        for m in maneuver1            //根据阶段一的解法，转动更新ud_edges
            ud_edges = ud_edgesMoveTable[ud_edges][m];
        
        dist2 = get_depth_phase2(corners, ud_edges);  
        for(togo2 = dist2; togo2 <= togo2_limit; togo2++)      //限制步数的深搜，IDA*
            search2(corners, ud_edges, slice, dist2, togo2)
    }

Ⅱ Допустимое вращение

Во многих предыдущих кодах написано, что в операции вращения разрешены все 18 оборотов, что это значит? Чтобы проиллюстрировать пример,Например, если я использую L на этом шаге, его не следует использовать в следующем вращении. $\{L, L2,L3\}$ , потому что вместо этого всегда можно использовать более короткие последовательности вращения, например $LL = L2,\ LL2 = L3,\ LL3 = 0,\ L2L3=L$ . так $\{L, L2,L3\}$ не следует использовать позже $\{L, L2,L3\}$ .

Общие шаги вращения кубика Рубика удовлетворяют коммутативному закону, например $FR\neq RF$ , но относительное вращение двух слоев удовлетворяет коммутативному закону, такому как $LR=RL$ , поэтому, если за вращением L-типа может следовать вращение R-типа, то за вращением R-типа не может следовать вращение L-типа.

Кроме того, каждая стадия имеет ограниченное вращение, особенно на стадии 2, которую можно использовать только $\{U,D,L2,R2,F2,B2\}$

И на первом этапе, если $dist = 0 \ \ AND \ \ togo1 \neq 0$ , что указывает на то, что необходимо найти субоптимальное решение за один этап, чтобы получить в целом лучшее решение. В настоящее время, даже на первом этапе, мы запрещаем использование $\{U1,U2,U3,D1,D2,D3,L2,R2,F2,B2\}$ , который используется на втором этапе, но мы запрещаем его использование. Зачем?Например, последовательность вращения М может привести начальное состояние к целевому состоянию, тогда MU, MR2 и другие последовательности вращения также могут привести начальное состояние к целевому состоянию, но субоптимальное решение этого этапа 1 не позволяет найти лучшее решение.

III Обратное состояние/преобразование

Я действительно не знаю, как это назвать, поэтому я просто использую терминологию в математике.Мы просили обратное преобразование симметричного преобразования ранее.Здесь мы запрашиваем обратный элемент состояния кубика Рубика или обратное преобразование обычная трансформация. Реализация здесь отличается от попарной проверки симметричного преобразования, посмотрим непосредственно на код:

CubieCube inverse_cubiecube(CubieCube cc){
    CubieCube inv;
	for (Edge edg = UR;edg <= BR; edg++) 		  //棱边位置
        inv.eo[cc.eo[edg].e].e = edg;
	for (Edge edg = UR;edg <= BR; edg++)          //棱边方向
        inv.eo[edg].o = cc.eo[inv.eo[edg].e].o;

	for (Corner crn = URF;crn <= DRB; crn++)      //角块位置
        inv.co[cc.co[crn].c].c = crn;
	for (Corner crn = URF; crn <= DRB;crn++)      //角块方向
        inv.co[crn].o = (3 - cc.co[ccInv.co[crn].c].o) % 3   //角块方向要发生变化
}

Внутри есть еще немного, не запутайтесь, должно быть легко понять, как имитировать изменения. Скажите, почему направление ребра не меняется, а направление углового блока должно измениться.Причина связана с тремя направлениями углового блока и определением края блока.Для углового блока, если мы посмотрим только на скрученный и нескрученный углы, направление углового блока не изменилось., вы можете попробовать несколько простых алгебраических чисел, последняя формула просто заменяет 1 на 2, 2 на 1, 0 или 0. Если вы все еще не уверены, вы можете выполнить обратную операцию над кубиком Рубика, а затем пронаблюдать, как меняется направление ребра блока в соответствии с определением направления.

Ⅳ Ориентация углового блока при сложном преобразовании/повороте

В связи с добавлением зеркального преобразования направление диагонального блока переопределяется, а диапазон значений направления зеркала $[3,5]$ . Здесь крутка по часовой стрелке становится 5, а крутка против часовой стрелки становится 4. Я не вижу здесь соответствующих отечественных и зарубежных материалов.Согласно фактической работе кода, результат моделирования вращения кубика Рубика должен быть таким.

Функция angle_multiply - это функция для изменения положения и направления углового блока во время преобразования.Выше мы имеем дело только с нормальным состоянием, и после добавления зеркального отображения будут некоторые изменения.Здесь это идеально, или посмотрите на код напрямую:

void cornerMultiply(const CubieCube *a, const CubieCube *b, CubieCube *ab){ 
	for (Corner crn = URF; crn <= DRB; crn++){
		ab->co[crn].c = a->co[b->co[crn].c].c;     //角块位置变化
		char oriA = a->co[b->co[crn].c].o;         //原本方向
        char oriB = b->co[crn].o);                 //方向怎么变化
        /***根据普通还是镜像分别讨论***/
        if (oriA < 3 && oriB < 3){            //a, b都处于普通状态
            ori = oriA + oriB;      
            if (ori >= 3) ori -= 3;           //结果普通状态
	    }else if (oriA < 3 && oriB >= 3){     //b处于镜像状态
            ori = oriA + oriB;
            if (ori >= 6) ori-=3;	          //结果镜像状态
		}else if (oriA >= 3 && oriB < 3){     //a处于镜像状态
            ori = oriA - oriB;
            if (ori < 3) ori += 3;		      //结果镜像状态
		}else if (oriA >= 3 && oriB >= 3){    //a，b都处于镜像状态
            ori = oriA - oriB;
            if (ori < 0) ori += 3;		      //结果普通状态
		}
    }
}

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

Основная причина в том, что операции сложения и вычитания oriA и oriB в разных ситуациях, а также то, добавляет ли ori окончательного результата 3 или вычитает 3, могут сбивать с толку, эй, очень запутанно, но я не буду вдаваться в подробности, в основном потому, что вопрос об этом направлении действительно не слишком много Хорошее выражение, лучший способ выяснить это смоделировать обычное преобразование на основе простого зеркального преобразования, а затем взять физический кубик Рубика в качестве эталона, чтобы увидеть, так ли это . Если вы хотите подробно рассказать об операции симуляции, большая часть содержания — это операция смещения внутри дискрета, которая является повторяющейся и скучной, поэтому я не буду говорить об этом.Если вам интересно, вы можете смоделировать ее самостоятельно.

Ⅴ Многопоточный и многонаправленный поиск для повышения эффективности

Можно использовать многопоточный параллельный поиск.Параллельный поиск — это не поиск одной и той же ситуации в одном и том же направлении несколько раз, а поиск в разных направлениях. Например, поиск другой оси, поиск обратного состояния.Поиск другой оси означает выполнение преобразования симметрии S_URF3 на кубике Рубика перед поиском (не обязательно поворот вокруг угла URF3, другие тоже подойдут) Точно так же поиск инверсного состояния означает сначала обратное преобразование кубика Рубика..

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

Девять, конец ссылки

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

Материалы на иностранном языке, упомянутые в этой статье, если вам интересно, вы можете перейти к просмотру оригинальных материалов.

kociemba.org/cube.htm, Коциемба...Для версии на Python все части очень понятны.

www.jaapsch.net/puzzles/, за границей…

www.cube20.org, заявляет, что число БогаСайт 20,там же исходник про двухэтапный алгоритм и соответствующее объяснение в pdf.Прочитав и разобравшись,должен стать богом.Я настаивал,что после прочтения почти не читал.Если вы заинтересованы и хотите стать сильнее, вы можете попробовать. .

En. Wikipedia.org/wiki/optima…

Woohoo.speedsolving.com/wiki/index. …

Если нет IX.com/he и — как ручка заводится —…Это также очень хороший веб-сайт, на котором есть различные теории, онлайн-программы и т. д.

«Диаметр группы кубика Рубика — двадцать», одна из самых влиятельных статей о кубике Рубика, пришла к выводу, что число Бога равно 20, и его стоит прочитать.

Есть еще некоторые, которые я не буду перечислять. Выше приведены некоторые ресурсы веб-сайтов, которые я лично считаю лучшими. Если вы хотите увидеть исходное теоретическое объяснение, вы можете пойти и посмотреть их. Все они на английском языке. почти нет.Я не талантлив, и я надеюсь сделать все возможное.Если есть какие-либо ошибки таким же образом, пожалуйста, критикуйте и исправьте меня. На некоторых веб-сайтах все еще есть ресурсы, которым нужны лестницы.Те, у кого их нет, могут ответить на кубик Рубика в фоновом режиме.Я помещаю в него некоторые из вышеупомянутых исходных кодов и программ для удобства загрузки.

Эта статья о двухэтапном алгоритме Coxianba. Алгоритм Coxianba вообще не может получить оптимальное решение. Есть ли какой-либо алгоритм, который может получить оптимальное решение каждый раз? Ответ - да, это первая статья Алгоритм Бога, Алгоритм Крофа , о котором я тоже упоминал в свое время, не является загадочным.Он реализован на основе двухэтапного алгоритма Косенба.После понимания двухэтапного алгоритма его следует хорошо понять.Мы подробно опишем его в следующей статье .

Наконец, давайте поговорим о небольшом отступлении.Давайте прочувствуем двухэтапный алгоритм.На самом деле двухэтапный алгоритм может не только вдохновить нас в области компьютерных кубов, но и помочь нам в повседневной жизни и обучении. Поставьте маленькую цель и решайте ее шаг за шагом. Помните обложку статьи, ту яркую метафору о двухстадийном алгоритме? Бесцельно идти на другой берег далеко, лучше идти в определенную акваторию, чтобы выполнить каждую цель, и, наконец, успешно добраться до другого берега. Хотя это может быть и не лучшее решение, кто может идти по прямой линии на этом жизненном пути? Пока вы усердно работаете и стремитесь получить соответствующее оптимальное решение на каждом этапе своей жизни, также очень хорошо вместе найти лучшее решение, верно?