Facebook样本拼图:河内的塔

Question

以下是Facebook招聘样本测试的问题.

有K钉.当从挂钉的底部到顶部观察时,每个挂钉可以以半径的递减顺序保持圆盘.有N个半径为1到N的圆盘; 给定栓钉的初始配置和栓钉的最终配置,输出从初始配置转换为最终配置所需的移动.您需要以最少的移动次数进行转换.

移动包括挑选任何一个钉子的最顶部圆盘并将其放置在任何其他钉子的顶部.在任何时候,必须保持所有栓钉的半径减小性能.

约束:

1 <= N <= 8

3 <= K <= 5

输入格式:

NK

第二行包含N个整数.每个整数在1到K的范围内,其中第i个整数表示在初始配置中存在半径为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 1 1 1 1

样本输出#01:

五

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;
    }
}