Facebook 示例拼图 : Towers of Hanoi

Question

这是来自 Facebook 招聘样本测试的问题。

有K个钉子。当从钉子的底部到顶部看时，每个钉子可以按半径递减的顺序固定圆盘。有 N 个圆盘，半径为 1 到 N；给定钉子的初始配置和钉子的最终配置，输出从初始配置转换为最终配置所需的移动。您需要以最少的移动次数完成转换。

移动包括拾取任何一个桩子的最上面的圆盘并将其放在任何其他桩子的顶部。在任何时候，都必须保持所有钉子的递减半径特性。

Constraints:

1<=N<=8

3<= K<=5

Input Format:

NK

第二行包含 N 个整数。每个整数都在 1 到 K 的范围内，其中第 i 个整数表示初始配置中半径为 i 的圆盘所在的桩。

第三行以类似于初始配置的格式表示最终配置。

Output Format:

第一行包含 M - 完成转换所需的最少移动数。

接下来的 M 行描述了一个移动，通过一个要从中选择的 Hook 编号和一个要放置的 Hook 编号。如果有多个解决方案，输出其中任何一个就足够了。您可以假设，总有一个少于 7 步的解决方案，并且初始配置不会与最终配置相同。

Sample Input #00:

2 3

1 1

2 2

Sample Output #00:

3

1 3

1 2

3 2

Sample Input #01:

6 4

4 2 4 3 1 1

1 1 1 1 1 1

Sample Output #01:

5

3 1

4 3

4 1

2 1

3 1

讨论这个问题的解决方案没有什么坏处，因为它是一个示例问题。

经典的汉诺塔问题的解决方案非常易于编写代码:

void hanoi(char s, char i, char d, int n)
{
     if(n>0)
     {
            hanoi(s, d, i, n-1);
            cout<<s<<":"<<d<<endl;
            hanoi(i, s, d, n-1);
     }        
}

以上内容也可以扩展到河内的一般“k”钉塔。但是，事实证明，这些知识对于设计这个示例难题的解决方案毫无用处。对于将来如何处理此类问题和类似问题有什么建议吗？

Answer 1

这是我的动态规划解决方案，最多可在 O(K^N) 步中找到最佳移动顺序，它在 K = 5、N = 8 的情况下运行不到一秒。由于懒惰，我对输入数据进行了硬编码.

它是一个通过状态空间的 BFS，永远不会访问同一个状态两次。然后通过从头到头回溯得到实际路径(这部分与最优序列的长度成线性关系)。基本上，它是“通过迷宫的最短路径”算法，但“迷宫”是问题的状态空间，起始“位置”是初始状态，结束“位置”是期望状态。

许多类似的问题都可以通过这种方式解决，只要您可以定义一个有限状态空间，您的目标是最小化两个状态之间的“距离”，以及一种计算可以从状态移动到哪些状态的方法当前状态。

例如，任意数量的“传教士和食人者”问题都可以用相同的算法解决。

此外，如果您需要“所有最优解”而不是“任何最优解”，则很容易修改算法以提供它们。

class Program
{
    static int N = 8;
    static int K = 5;
    static List<int> StartState = new List<int> { 3, 3, 2, 1, 4, 1, 5, 2 };
    static List<int> EndState = new List<int> { 1, 4, 2, 2, 3, 4, 4, 3 };

    static LinkedList<int> StateQueue = new LinkedList<int>();
    static int[] MovesToState = new int[(int)Math.Pow(K, N)];


    static void Main(string[] args)
    {
        for (int i = 0; i < StartState.Count; i++)
        {
            StartState[i]--;
            EndState[i]--;
        }

        int startStateIndex = StateToNum(StartState);
        int endStateIndex = StateToNum(EndState);

        for (int i = 0; i < MovesToState.Length; i++)
            MovesToState[i] = -1;

        MovesToState[startStateIndex] = 0;

        StateQueue.AddFirst(startStateIndex);
        while (StateQueue.Count > 0 && MovesToState[endStateIndex] == -1)
        {
            var legalMoves = LegalMoves(StateQueue.Last.Value);
            foreach (var newStateIndex in legalMoves)
            {
                int currMoves = MovesToState[StateQueue.Last.Value];
                if (MovesToState[newStateIndex] == -1)
                {
                    MovesToState[newStateIndex] = currMoves + 1;
                    StateQueue.AddFirst(newStateIndex);
                }
            }
            StateQueue.RemoveLast();
        }

        var currStateIndex = endStateIndex;
        var moves = new List<Tuple<int, int>>();
        while (currStateIndex != startStateIndex)
        {
            var legalMoves = LegalMoves(currStateIndex);
            int currMoves = MovesToState[currStateIndex];
            foreach (var prevStateIndex in legalMoves)
            {
                if (MovesToState[prevStateIndex] == MovesToState[currStateIndex] - 1)
                {
                    var currState = NumToState(currStateIndex);
                    var prevState = NumToState(prevStateIndex);
                    for (int i = 0; i < N; i++)
                    {
                        if (currState[i] != prevState[i])
                        {
                            moves.Add(new Tuple<int, int>(prevState[i] + 1, currState[i] + 1));
                            currStateIndex = prevStateIndex;
                            break;
                        }
                    }
                }
            }
        }
        Console.WriteLine(MovesToState[endStateIndex]);
        moves.Reverse();
        foreach (var move in moves)
        {
            Console.WriteLine("{0} {1}", move.Item1, move.Item2);
        }

        Console.Read();
    }

    static List<int> LegalMoves(int stateIndex)
    {
        var legalMoves = new List<int>();

        var state = NumToState(stateIndex);

        int[] minOnPeg = new int[K];
        for (int i = 0; i < minOnPeg.Length; i++)
            minOnPeg[i] = N;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < K; j++)
                if (state[i] == j && i < minOnPeg[j])
                    minOnPeg[j] = i;

        bool[] isTop = new bool[N];
        for (int i = 0; i < isTop.Length; i++)
            isTop[i] = false;
        for (int i = 0; i < K; i++)
            if (minOnPeg[i] < N)
                isTop[minOnPeg[i]] = true;

        for (int i = 0; i < N; i++)
        {
            if (!isTop[i])
                continue;

            for (int j = 0; j < K; j++)
            {
                if (minOnPeg[j] <= i)
                    continue;

                var tmp = state[i];
                state[i] = j;
                var newStateIndex = StateToNum(state);
                legalMoves.Add(newStateIndex);
                state[i] = tmp;
            }
        }
        return legalMoves;
    }

    static int StateToNum(List<int> state)
    {
        int r = 0;
        int f = 1;
        foreach (var peg in state)
        {
            r += f * peg;
            f *= K;
        }
        return r;
    }

    static List<int> NumToState(int num)
    {
        var r = new List<int>();
        for (int i = 0; i < N; i++)
        {
            r.Add(num % K);
            num = num / K;
        }
        return r;
    }
}