Есть ли способ улучшить скорость этого итеративного поиска с углубленным углублением в глубину? В настоящее время он проходит 1 млн узлов в секунду

#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 , поскольку он вызывается в цикле. Также похоже, что вы управляете своим состоянием как строкой, и любая операция со строкой может быть дорогостоящей. Я бы порекомендовал хороший профилировщик.