如何在 O(0) 内比较 3 维数组？

Question

因此，我尝试为使用 3 维数组的魔方制定求解算法，但是由于 3 维数组的值无法与另一个数组的值进行比较，因此我的 if 语句始终返回 False。

我的代码目前是这样的，但是调试部分总是返回 false，因为它无法正确比较。这也将运行大约 2*27^10 次，因此比较必须很快。使用列表和 for 循环对此来说速度不够快。

当前代码：

public void Solving(int[,,] Tbs) // 3d array cube that has to be solved
{
    bool found = false;


   List<char> movements = new() {'F','U','L', 'R','D', 'B' };
    Queue<int[,,]> activeFromSramble = new();
    Queue<int[,,]> activeFromSolved = new();

    if (DefaultCube() == DefaultCube()) // for debug purposes defaultcube has all have the same values inside
        Console.WriteLine("Works");
    else
    {

        Console.WriteLine("Broken");
    }
    Dictionary<object, object> fromSC = new();
    Dictionary<int[,,], int[,,]> fromSOL = new();
    activeFromSramble.Enqueue(Tbs);
    activeFromSolved.Enqueue(DefaultCube());
    fromSC.Add(Tbs, Tbs);
    fromSOL.Add(DefaultCube(),DefaultCube());
    while (found == false)
    {
        Console.WriteLine("It");
        int[,,] oldCube = activeFromSramble.Dequeue();
        if (fromSOL.ContainsKey(oldCube))
        {
            found = true;
                        
            Console.WriteLine("FOUND");
            
        }
        foreach (char c in movements)
        {
            
                for (int i = 1; i < 4; i++)
                {
                    int[,,] newCube = PermCube(oldCube, c, i);
                    if (fromSC.ContainsKey(newCube)) // of hij in eigen lijst staat met key
                        continue;

                fromSC.Add(newCube, oldCube); 
                    activeFromSramble.Enqueue(newCube);
                   
                }
        }
        
        oldCube = activeFromSolved.Dequeue();
        if (fromSC.ContainsKey(oldCube))
        {
            found = true;
            Console.WriteLine("FOUND");
                        
        }
        foreach (char c in movements)
        {
            for (int i = 1; i < 4; i++)
            {

                    int[,,] newCube = PermCube(oldCube, c, i);
                    if (fromSOL.ContainsKey(newCube))
                    {
                        continue;
                    }
                    
                    {
                        activeFromSolved.Enqueue(newCube);
                        fromSOL.Add(newCube, oldCube);
                    }
            }
        }

    }


    
}

Answer 1

您无法在恒定时间内比较可变大小数组中的数据。一些可能的方法：

1. 使用哈希。这使您可以通过多次比较来分摊生成哈希的时间。使用冲突可能性可以忽略不计的强哈希。考虑使用不可变的数据结构来确保哈希始终与数据匹配。
2. 使用另一种数据表示形式。计算出您实际需要的最少位数，并尽可能紧凑地存储它们。这应该尽可能减少比较时间。
3. 使用快速哈希，但如果哈希匹配，则回退到检查实际数据。