#c# #depth-first-search #graph-traversal #rubiks-cube
#c# #поиск в глубину #обход графика #кубик-рубикс
Вопрос:
private bool DLS(RubiksCube start, RubiksCube cube, int depth, int maxDepth, string t, bool end, int d)
{
switch (t[0])
{
default:
current = Rotations;
break;
case 'R':
current = R1;
break;
case 'L':
current = L1;
break;
case 'F':
current = F1;
break;
case 'B':
current = B1;
break;
case 'U':
current = U1;
break;
case 'D':
current = D1;
break;
}
if (Found(cube))
{
return true;
}
if (depth <= 0)
{
return false;
}
for(int a = 0; a < current.Length; a )
{
count ;
RotateCube(ref cube, current[a], false);
if (DLS(start, cube, depth - 1, maxDepth, current[a], end, d 1))
{
sequence = " " current[a];
return true;
}
else
{
RotateCube(ref cube, current[a], true);
}
}
return false;
}
private void RotateCube(ref RubiksCube cube, string turn, bool reverse)
{
if (reverse)
{
switch (turn)
{
case "R":
cube.RP();
break;
case "L":
cube.LP();
break;
case "U":
cube.UP();
break;
case "D":
cube.DP();
break;
case "F":
cube.FP();
break;
case "B":
cube.BP();
break;
case "R'":
cube.R();
break;
case "L'":
cube.L();
break;
case "U'":
cube.U();
break;
case "D'":
cube.D();
break;
case "F'":
cube.F();
break;
case "B'":
cube.B();
break;
case "R2":
cube.RP();
cube.RP();
break;
case "L2":
cube.LP();
cube.LP();
break;
case "U2":
cube.UP();
cube.UP();
break;
case "D2":
cube.DP();
cube.DP();
break;
case "F2":
cube.FP();
cube.FP();
break;
case "B2":
cube.BP();
cube.BP();
break;
}
}
else
{
cube.LastMove = turn;
switch (turn)
{
case "R":
cube.R();
break;
case "L":
cube.L();
break;
case "U":
cube.U();
break;
case "D":
cube.D();
break;
case "F":
cube.F();
break;
case "B":
cube.B();
break;
case "R'":
cube.RP();
break;
case "L'":
cube.LP();
break;
case "U'":
cube.UP();
break;
case "D'":
cube.DP();
break;
case "F'":
cube.FP();
break;
case "B'":
cube.BP();
break;
case "R2":
cube.R();
cube.R();
break;
case "L2":
cube.L();
cube.L();
break;
case "U2":
cube.U();
cube.U();
break;
case "D2":
cube.D();
cube.D();
break;
case "F2":
cube.F();
cube.F();
break;
case "B2":
cube.B();
cube.B();
break;
}
}
}
//Executes a Rubiks cube R movement - Singmaster notation
public void R()
{
UInt64 temp = matrix[5] amp; 1099511562240;
matrix[3] = matrix[3] << 16 | matrix[3] >> 48;
UInt64 temp1 = (matrix[2] amp; 18446462598732841215) << 32 | (matrix[2] amp; 18446462598732841215) >> 32;
matrix[5] = temp1 (matrix[5] amp; 18446742974197989375);
temp1 = matrix[4] amp; 1099511562240;
matrix[4] = temp (matrix[4] amp; 18446742974197989375);
temp = (matrix[0] amp; 1099511562240) >> 32 | (matrix[0] amp; 1099511562240) << 32;
matrix[0] = temp1 (matrix[0] amp; 18446742974197989375);
matrix[2] = temp (matrix[2] amp; 140737488355200);
}
private bool Found(RubiksCube cube)
{
switch (Group)
{
//Group 1 detects whether the edges are oriented correctly
case 1:
UInt64 bitmask = 65280;
if (!Check((cube.Matrix[0] amp; bitmask) >> 8, (cube.Matrix[2] amp; 65280) >> 8)) { return false; }
if (!Check((cube.Matrix[0] amp; (bitmask <<= 16)) >> 24, (cube.Matrix[3] amp; 65280) >> 8)) { return false; }
if (!Check((cube.Matrix[0] amp; (bitmask <<= 16)) >> 40, (cube.Matrix[4] amp; 65280) >> 8)) { return false; }
if (!Check((cube.Matrix[0] amp; (bitmask <<= 16)) >> 56, (cube.Matrix[1] amp; 65280) >> 8)) { return false; }
bitmask = 65280;
if (!Check((cube.Matrix[5] amp; bitmask) >> 8, (cube.Matrix[4] amp; 280375465082880) >> 40)) { return false; }
if (!Check((cube.Matrix[5] amp; (bitmask <<= 16)) >> 24, (cube.Matrix[3] amp; 280375465082880) >> 40)) { return false; }
if (!Check((cube.Matrix[5] amp; (bitmask <<= 16)) >> 40, (cube.Matrix[2] amp; 280375465082880) >> 40)) { return false; }
if (!Check((cube.Matrix[5] amp; (bitmask <<= 16)) >> 56, (cube.Matrix[1] amp; 280375465082880) >> 40)) { return false; }
if (!Check((cube.Matrix[4] amp; 2139095040) >> 24, (cube.Matrix[3] amp; 18374686479671623680) >> 56)) { return false; }
if (!Check((cube.Matrix[4] amp; 18374686479671623680) >> 56, (cube.Matrix[1] amp; 2139095040) >> 24)) { return false; }
if (!Check((cube.Matrix[2] amp; 2139095040) >> 24, (cube.Matrix[1] amp; 18374686479671623680) >> 56)) { return false; }
if (!Check((cube.Matrix[2] amp; 18374686479671623680) >> 56, (cube.Matrix[3] amp; 2139095040) >> 24)) { return false; }
return true;
case 2:
bitmask = 255;
for(int x = 0; x < 4; x )
{
if (((cube.Matrix[0] amp; bitmask) >> (16 * x) != 6) amp;amp; ((cube.Matrix[0] amp; bitmask) >> (16 * x) != 1)) { return false; }
if (((cube.Matrix[5] amp; bitmask) >> (16 * x) != 6) amp;amp; ((cube.Matrix[5] amp; bitmask) >> (16 * x) != 1)) { return false; }
bitmask <<= 16;
}
for (int x = 0; x < 5; x = 2)
{
if (!((cube.Matrix[x] amp; 65280) >> 8 == 5 || (cube.Matrix[x] amp; 65280) >> 8 == 1 || (cube.Matrix[x] amp; 65280) >> 8 == 6 || (cube.Matrix[x] amp; 65280) >> 8 == 3))
{
return false;
}
if (!((cube.Matrix[x] amp; 0xFF0000000000) >> 40 == 5 || (cube.Matrix[x] amp; 0xFF0000000000) >> 40 == 1 || (cube.Matrix[x] amp; 0xFF0000000000) >> 40 == 6 || (cube.Matrix[x] amp; 0xFF0000000000) >> 40 == 3))
{
return false;
}
}
if (!((cube.Matrix[5] amp; 65280) >> 8 == 5 || (cube.Matrix[5] amp; 65280) >> 8 == 1 || (cube.Matrix[5] amp; 65280) >> 8 == 6 || (cube.Matrix[5] amp; 65280) >> 8 == 3))
{
return false;
}
if (!((cube.Matrix[5] amp; 0xFF0000000000) >> 40 == 5 || (cube.Matrix[5] amp; 0xFF0000000000) >> 40 == 1 || (cube.Matrix[5] amp; 0xFF0000000000) >> 40 == 6 || (cube.Matrix[5] amp; 0xFF0000000000) >> 40 == 3))
{
return false;
}
return true;
case 3:
if (!Group3(cube.Matrix[0], 1, 6)) { return false; }
if (!Group3(cube.Matrix[1], 2, 4)) { return false; }
if (!Group3(cube.Matrix[2], 3, 5)) { return false; }
return true;
case 4:
if(cube.Matrix[0] != solution.Matrix[0]) { return false; }
if(cube.Matrix[1] != solution.Matrix[1]) { return false; }
if(cube.Matrix[2] != solution.Matrix[2]) { return false; }
return true;
}
return false;
Этот код, похоже, недостаточно быстр для поиска решения кубика Рубика, несмотря на сокращение и уменьшение коэффициента ветвления с помощью алгоритма Тислтуэйта. Я попытался удалить метод Found(), чтобы проверить, не замедляет ли это выполнение, однако это привело к незначительному изменению производительности.
Редактировать: добавлены все методы
Комментарии:
1. Первое, что вам нужно сделать (если вы еще этого не сделали), это загрузить инструмент бенчмаркинга, такой как BenchmarkDotNet. Во-вторых, используется
ReadOnlySpan
там, где это возможно. Однако проблема, скорее всего, кроется в алгоритме, о котором я ничего не знаю2. Предоставленный код не содержит достаточно подробностей, чтобы сделать обоснованное предположение о потенциальных проблемах. Я бы подозревал
RotateCube
, поскольку он вызывается в цикле. Также похоже, что вы управляете своим состоянием как строкой, и любая операция со строкой может быть дорогостоящей. Я бы порекомендовал хороший профилировщик.