Facebook示例拼图:河内塔楼

Question

以下是Facebook招聘样本测试中的一个问题。

有K根钉。当从下到上观察时，每个钉可以按半径的递减顺序持有盘。有N个圆盘，其半径为1到N；给定支柱的初始配置和支柱的最终配置，输出从初始配置到最终配置所需的移动。您需要以最少的移动次数进行转换。

移动包括挑选任何一个钉的最上面的阀瓣，并将它放在任何其他钉的顶部。在任何时间点，都必须保持所有支柱的减小半径特性。

制约因素：

1<= N<=8

3<= K<=5

输入格式：

氮钾

第2行包含N个整数。每个整数都在1到K的范围内，其中第一个整数表示初始配置中存在半径i的盘所指向的挂钩。

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

输出格式：

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

下面的M行描述了一个移动，由一个要选择的盯住数和一个要放置的钉住数来描述。如果有多个解决方案，就足以输出其中的任何一个解决方案。您可以假设，总有一个解决方案的移动少于7和初始确认将不相同的最后一个。

示例输入#00：

2 3

1 1

2 2

样本输出#00：

3.

1 3

1 2

3 2

样本输入#01：

6 4

4 2 4 3 1

1 1 1

样本输出#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;
    }
}

Answer 2

在java中找到了这个解决方案。基本上，它将所有可能的移动映射到树中并执行BFS。

Answer 3

利用递归3.html解决河内塔问题的优秀资源