fengartai.cs

本代码是为了应付人工智能的实验而编写的

                        depth = data.Depth;
                        if (board == endBoard)
                        {
                            return WinnerCode;
                        }
                        boardtable.Add(newCode, new StateMsg(depth, data.Dir));
                        openList.RemoveAt(0);
                        if (depth < MaxDepth)
                            if (extentOpenList(newCode, data.Dir, depth + 1))
                                return WinnerCode;
                    }
                }
            }
            return -1;
        }

        #endregion

        #region 带Open表和HashTable的深度优先搜索（排序后才插入Open表）

        /// <summary>
        ///  扩展OpenStack
        /// </summary>
        /// <param name="board"></param>
        /// <param name="depth"></param>
        private bool extentOpenStack(long code, Direction lastDir, int depth)
        {
            int empIndex = (int)(code % 10 - 1);
            int len_moves = dirs[empIndex].Length;
            long newcode ;
            SortedList<long, Direction> sort = new SortedList<long, Direction>(4);
            Direction dir = 5 - lastDir;
            Direction curdir;

            for (int i = 0; i < len_moves; i++)
            {
                curdir = dirs[empIndex][i];
                if (curdir != dir)
                {
                    newcode = change(code, curdir);

                    //跟目标匹配,结束
                    if (newcode == WinnerCode)
                    {
                        setResult(code, dirs[empIndex][i], lastDir, depth);
                        return true;
                    }
                    if (newcode <= tens[8])
                        throw new Exception("棋盘码修改错误！ ");
                    if (newcode != OutOfCode)
                    {
                        if (!boardtable.ContainsKey(newcode))
                            sort.Add(-newcode, curdir);
                        else
                        {
                            same++;
                            if (depth < boardtable[newcode].Depth)
                            {
                                boardtable.Remove(newcode);
                                sort.Add(-newcode, curdir);
                            }
                        }
                    }
                }
            }
            IEnumerator<KeyValuePair<long,Direction>> en = sort.GetEnumerator();
            while (en.MoveNext())
            {
                openStack.Push(new State(-en.Current.Key, depth, en.Current.Value));
            }
            return false;
        }

        /// <summary>
        /// 带Open表和HashTable的深度优先搜索（排序后才插入Open表）
        /// </summary>
        /// <returns></returns>
        private int DepthFirstSearch()
        {
            lock (this)
            {
                int depth = 1;
                Direction[] moves;
                int board;
                long newCode = combinCode(this.startBoard, 0);
                int empIndex = getEmpIndex(newCode);

                moves = dirs[empIndex - 1];
                State data;
                if (extentOpenStack(newCode, Direction.None, depth))
                    return WinnerCode;
                while (openStack.Count > 0)
                {
                    lock (this)
                    {
                        nodes++;
                        if (nodes >= maxNodes)
                            return -1;
                        data = openStack.Pop();

                        if (data != null)
                        {
                            newCode = data.Code;
                            board = getBoard(newCode);
                            depth = data.Depth;
                            if (board == endBoard)
                            {
                                return WinnerCode;
                            }
                            if (boardtable.ContainsKey(newCode))
                            {
                                same++;
                                if (depth < boardtable[newCode].Depth)
                                {
                                    boardtable[newCode] = new StateMsg(depth, data.Dir);
                                }
                                else
                                    continue;
                            }
                            else
                            {
                                boardtable.Add(newCode, new StateMsg(depth, data.Dir));
                            }
                            if (depth < MaxDepth)
                                if (extentOpenStack(newCode, data.Dir, depth + 1))
                                    return WinnerCode;
                        }
                    }
                }
                return -1;
            }
        }

        #endregion

        #region 带Open表和HashTable的广度优先搜索（排序后才插入Open表）

        /// <summary>
        ///  扩展OpenQueue
        /// </summary>
        /// <param name="board"></param>
        /// <param name="depth"></param>
        private bool extentOpenQueue(long code, Direction lastDir, int depth)
        {
            int empIndex = (int)(code % 10 - 1);
            int len_moves = dirs[empIndex].Length;
            long newcode;
            SortedList<long, Direction> sort = new SortedList<long, Direction>(4);
            Direction dir = 5 - lastDir;
            Direction curdir;
            for (int i = 0; i < len_moves; i++)
            {
                curdir = dirs[empIndex][i];
                if (curdir != dir)
                {
                    newcode = change(code, curdir);

                    //跟目标匹配,结束
                    if (newcode == WinnerCode)
                    {
                        setResult(code, dirs[empIndex][i], lastDir, depth);
                        return true;
                    }
                    if (newcode <= tens[8])
                        throw new Exception("棋盘码修改错误！ ");
                    if (newcode != OutOfCode)
                    {
                        if (!boardtable.ContainsKey(newcode))
                            sort.Add(newcode, curdir);
                        else
                        {
                            same++;
                            if (depth < boardtable[newcode].Depth)
                            {
                                boardtable.Remove(newcode);
                                sort.Add(newcode, curdir);
                            }
                        }
                    }
                }
            }
            IEnumerator<KeyValuePair<long, Direction>> en = sort.GetEnumerator();
            while (en.MoveNext())
            {
                openQueue.Enqueue(new State(en.Current.Key, depth, en.Current.Value));
            }
            return false;
        }

        /// <summary>
        /// 带Open表和HashTable的广度优先搜索（排序后才插入Open表）
        /// </summary>
        /// <returns></returns>
        private int BreadthFirstSearch()
        {
            int depth = 1;
            Direction[] moves;
            int board;
            long newCode = combinCode(this.startBoard, 0);
            int empIndex = getEmpIndex(newCode);

            moves = dirs[empIndex - 1];
            State data;
            if (extentOpenQueue(newCode, Direction.None, depth))// Mask!
                return WinnerCode;
            while (openQueue.Count > 0)  // Mask!
            {
                lock (this)
                {
                    nodes++;
                    if (nodes >= maxNodes)
                        return -1;
                    data = openQueue.Dequeue();// Mask!

                    if (data != null)
                    {
                        newCode = data.Code;
                        board = getBoard(newCode);
                        depth = data.Depth;
                        if (board == endBoard)
                        {
                            return WinnerCode;
                        }
                        if (boardtable.ContainsKey(newCode))
                        {
                            same++;
                            if (depth < boardtable[newCode].Depth)
                            {
                                boardtable[newCode] = new StateMsg(depth, data.Dir);
                            }
                            else
                                continue;
                        }
                        else
                        {
                            boardtable.Add(newCode, new StateMsg(depth, data.Dir));
                        }
                        if (depth < MaxDepth)
                            if (extentOpenQueue(newCode, data.Dir, depth + 1))
                                return WinnerCode;
                    }
                }
            }
            return -1;
        }

        #endregion

        /// <summary>
        /// 把一维数组的局面编码成一个整数的表示形式
        /// </summary>
        /// <param name="genBoard"></param>
        /// <returns></returns>
        public int ToIntBoard(int[] genBoard)
        {
            int board = 0;
            int emp = 0;
            for (int i = 0; i < genBoard.Length; i++)
            {
                if (genBoard[i] != 0)
                    board = 10 * board + genBoard[i];
                else
                    emp = i + 1;
            }
            return 10 * board + emp;
        }

        /// <summary>
        /// 判断是否可以从初始状态到达目标状态（计算两个状态的逆序列，奇偶性相同的返回true）
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        private bool ExistAns(int[] start, int[] end)
        {
            int sequence_start = 0, sequence_end = 0;
            for (int i = 0; i < start.Length; i++)
            {
                if (start[i] != 0)
                    for (int j = i + 1; j < start.Length; j++)
                    {
                        if (start[j] != 0 && start[j] < start[i])
                            sequence_start++;
                    }
                if (end[i] != 0)
                    for (int j = i + 1; j < start.Length; j++)
                    {
                        if (end[j] != 0 && end[j] < end[i])
                            sequence_end++;
                    }
            }
            return (sequence_start + sequence_end) % 2 == 0;
        }

        /// <summary>
        /// 初始化求解
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <param name="maxDepth"></param>
        private void InitComp(int[] start, int[] end, int maxDepth)
        {
            nodes = 0;
            same = 0;
            MaxDepth = maxDepth;
            result = null;
            boardtable = new Dictionary<long, StateMsg>();
            openList = new  SortedList<long,StateMsg>();
            openStack = new Stack<State>();
            openQueue = new Queue<State>();

            this.startBoard = ToIntBoard(start);
            endBoard = ToIntBoard(end);
            int t_end = endBoard;
            int emp_end = endBoard % 10;
            endBoardArray = new int[10];
            endBoardArray[0] = emp_end;
            endBoardArray[emp_end] = 0;
            for (int i = 9; i > emp_end; i--)
            {
                t_end /= 10;
                endBoardArray[i] = t_end % 10;
            }
            for (int i = emp_end - 1; i >= 1; i--)
            {
                t_end /= 10;
                endBoardArray[i] = t_end % 10;
            }
        }

        /// <summary>
        /// 求解8数码问题
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        public Answer Compute(int[] start, int[] end, int maxDepth, int mode)
        {
            if (!ExistAns(start, end))
                return Answer.NotExist;
            InitComp(start, end, maxDepth);
            if (startBoard == endBoard)
                return Answer.Exist;
            long oldtime = System.DateTime.Now.Ticks;
            int eval = 0;
            switch (mode)
            {
                case 0:
                    eval = DepthFirstSearch();
                    break;
                case 1:
                    eval = BreadthFirstSearch();
                    break;
                case 2:
                    eval = BestFirstSearch();
                    break;
                default:
                    eval = BestFirstSearch();
                    break;
            }
            time = (System.DateTime.Now.Ticks - oldtime) / 10000000.0f;
            if (eval == WinnerCode)
                return Answer.Exist;
            return Answer.NotExistInDepth;
        }

    }
}