之前写了一篇《趣味迷宫一解:深度优先递归解法》。不过觉得意犹未尽,对程序稍加改造,即输入值仍为2011,而输出值从2012至2020的计算结果如下所示:

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2012
ComputableNodeCount: 72,967
ElapsedMilliseconds: 153ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393×3>1179-5>1174÷2>587+7>594÷2>297+7>304-5>299×3>897-5>892×3>2676÷2>1338+7>1345-5>1340×3>4020÷2>2010+7>2017-5>2012

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2013
ComputableNodeCount: 472,358
ElapsedMilliseconds: 1,506ms
NodeDepth: 1
ExpressionPath: 2011+7>2018-5>2013

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2014
ComputableNodeCount: 9,176
ElapsedMilliseconds: 12ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159+7>1166÷2>583+7>590÷2>295+7>302÷2>151×3>453-5>448÷2>224+7>231-5>226×3>678-5>673×3>2019-5>2014

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2015
ComputableNodeCount: 30,265
ElapsedMilliseconds: 104ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540÷2>770+7>777×3>2331-5>2326÷2>1163+7>1170÷2>585+7>592÷2>296+7>303-5>298×3>894÷2>447+7>454-5>449×3>1347-5>1342×3>4026÷2>2013+7>2020-5>2015

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2016
ComputableNodeCount: 13,084
ElapsedMilliseconds: 18ms
NodeDepth: 25
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159-5>1154×3>3462÷2>1731+7>1738÷2>869+7>876÷2>438+7>445×3>1335-5>1330÷2>665+7>672×3>2016

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2017
ComputableNodeCount: 72,932
ElapsedMilliseconds: 198ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393×3>1179-5>1174÷2>587+7>594÷2>297+7>304-5>299×3>897-5>892×3>2676÷2>1338+7>1345×3>4035-5>4030÷2>2015+7>2022-5>2017

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2018
ComputableNodeCount: 77,178
ElapsedMilliseconds: 204ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393-5>388×3>1164÷2>582+7>589×3>1767-5>1762÷2>881+7>888÷2>444+7>451×3>1353-5>1348×3>4044-5>4039+7>4046÷2>2023-5>2018

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2019
ComputableNodeCount: 8,970
ElapsedMilliseconds: 29ms
NodeDepth: 25
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159+7>1166÷2>583+7>590÷2>295+7>302÷2>151-5>146×3>438÷2>219+7>226×3>678-5>673×3>2019

Summary: TryDepthFirstSearchExitNode
DesiredValue: 2020
ComputableNodeCount: 761,702
ElapsedMilliseconds: 2,328ms
Not found any exit node within depth 30.

以上输出结果中最离谱的是,在使用深度优先搜索的情况下,输出值为2013时的可计算节点合计竟然是472,358,耗时1,506msI 服了 U!

因此俺决定将程序改造为广度优先搜索,做个对比实验看一看 :D

长话短说,添加了广度优先搜索方法后,计算结果如下:

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2012
ComputableNodeCount: 169,128
ElapsedMilliseconds: 472ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393×3>1179-5>1174÷2>587+7>594÷2>297+7>304-5>299×3>897-5>892×3>2676÷2>1338+7>1345-5>1340×3>4020÷2>2010+7>2017-5>2012

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2013
ComputableNodeCount: 4
ElapsedMilliseconds: 0ms
NodeDepth: 1
ExpressionPath: 2011+7>2018-5>2013

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2014
ComputableNodeCount: 160,518
ElapsedMilliseconds: 571ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159+7>1166÷2>583+7>590÷2>295+7>302÷2>151×3>453-5>448÷2>224+7>231-5>226×3>678-5>673×3>2019-5>2014

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2015
ComputableNodeCount: 163,370
ElapsedMilliseconds: 528ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540÷2>770+7>777×3>2331-5>2326÷2>1163+7>1170÷2>585+7>592÷2>296+7>303-5>298×3>894÷2>447+7>454-5>449×3>1347-5>1342×3>4026÷2>2013+7>2020-5>2015

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2016
ComputableNodeCount: 73,696
ElapsedMilliseconds: 281ms
NodeDepth: 25
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159-5>1154×3>3462÷2>1731+7>1738÷2>869+7>876÷2>438+7>445×3>1335-5>1330÷2>665+7>672×3>2016

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2017
ComputableNodeCount: 169,124
ElapsedMilliseconds: 636ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393×3>1179-5>1174÷2>587+7>594÷2>297+7>304-5>299×3>897-5>892×3>2676÷2>1338+7>1345×3>4035-5>4030÷2>2015+7>2022-5>2017

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2018
ComputableNodeCount: 169,698
ElapsedMilliseconds: 623ms
NodeDepth: 27
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393-5>388×3>1164÷2>582+7>589×3>1767-5>1762÷2>881+7>888÷2>444+7>451×3>1353-5>1348×3>4044-5>4039+7>4046÷2>2023-5>2018

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2019
ComputableNodeCount: 73,439
ElapsedMilliseconds: 260ms
NodeDepth: 25
ExpressionPath: 2011+7>2018÷2>1009+7>1016÷2>508+7>515×3>1545-5>1540×3>4620-5>4615+7>4622÷2>2311+7>2318÷2>1159+7>1166÷2>583+7>590÷2>295+7>302÷2>151-5>146×3>438÷2>219+7>226×3>678-5>673×3>2019

Summary: TryBreadthFirstSearchExitNode
DesiredValue: 2020
ComputableNodeCount: 761,702
ElapsedMilliseconds: 2,042ms
Not found any exit node within depth 30.

输出结果很有趣,除了输出值为2013时,可计算节点合计是4,耗时0ms有大幅下降之外,其他输出值的计算耗时均有不同程度的上升,且节点深度与耗时成正比关系,即节点越深,耗时越多。而之前的深度优先搜索的耗时与子节点的排序有直接关系,即与路径的选择顺序有关。

不过,仔细想想便知,在目标节点深度未知的情况下,使用广度优先搜索可利用有限的内存尽量地找出结果,而使用深度优先搜索则很可能在尚未找到结果前就已经内存溢出了(上一篇中已讨论过最大深度的设置问题)。

包括深度优先搜素及广度优先搜索的完整C#代码如下:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConApp
{
    /// <summary>
    /// 运算迷宫。
    /// </summary>
    class MazeOfOperations
    {
        static void Main()
        {
            //Execute_TryDepthFirstSearchExitNode();
            //Execute_TryDepthFirstSearchExitNode(fromDesiredValue: 2012, toDesiredValue: 2020);

            //Execute_TryBreadthFirstSearchExitNode();
            Execute_TryBreadthFirstSearchExitNode(fromDesiredValue: 2012, toDesiredValue: 2020);

            Console.Read();
        }

        private static void Execute_TryBreadthFirstSearchExitNode(int fromDesiredValue = 2012, int toDesiredValue = 2012)
        {
            for (PuzzleFrame.DesiredValue = fromDesiredValue; PuzzleFrame.DesiredValue <= toDesiredValue; PuzzleFrame.DesiredValue++)
            {
                Stopwatch stopwatch = Stopwatch.StartNew();
                List<CommonComputeNode> siblingNodes = new List<CommonComputeNode>();
                siblingNodes.Add(PuzzleFrame.GetOrigin());
                CommonComputeNode exitNode = PuzzleFrame.TryBreadthFirstSearchExitNode(siblingNodes);
                stopwatch.Stop();

                ShowResultForSingleNode(summary: "TryBreadthFirstSearchExitNode"
                    , elapsedMilliseconds: stopwatch.ElapsedMilliseconds
                    , exitNode: exitNode);
            }
        }

        private static void Execute_TryDepthFirstSearchExitNode(int fromDesiredValue = 2012, int toDesiredValue = 2012)
        {
            for (PuzzleFrame.DesiredValue = fromDesiredValue; PuzzleFrame.DesiredValue <= toDesiredValue; PuzzleFrame.DesiredValue++)
            {
                Stopwatch stopwatch = Stopwatch.StartNew();
                CommonComputeNode exitNode = PuzzleFrame.TryDepthFirstSearchExitNode(PuzzleFrame.GetOrigin());
                stopwatch.Stop();

                ShowResultForSingleNode(summary: "TryDepthFirstSearchExitNode"
                    , elapsedMilliseconds: stopwatch.ElapsedMilliseconds
                    , exitNode: exitNode);
            }
        }

        private static void ShowResultForSingleNode(string summary, long elapsedMilliseconds, CommonComputeNode exitNode)
        {
            string nodeInfo = string.Empty;
            if (exitNode != null)
            {
                nodeInfo = string.Format(@"NodeDepth: {0}
ExpressionPath: {1}>{2}"
                    , exitNode.Depth, exitNode.GetExpressionPathString(), PuzzleFrame.DesiredValue);
            }
            else
            {
                nodeInfo = string.Format("Not found any exit node within depth {0}.", PuzzleFrame.MaxDepth);
            }
            string resultInfo = string.Format(
@"Summary: {0}
DesiredValue: {1}
ComputableNodeCount: {2:N0}
ElapsedMilliseconds: {3:N0}ms
{4}
", summary, PuzzleFrame.DesiredValue, PuzzleFrame.ComputableNodeCount, elapsedMilliseconds, nodeInfo);

            Console.WriteLine(resultInfo);
        }

    }

    #region PuzzleGame.

    internal static class PuzzleFrame
    {
        internal static int OriginalValue = 2011;
        internal static int DesiredValue = 2012;
        internal static int MaxDepth = 30;
        internal static int ComputableNodeCount = 0;
        internal static List<CommonComputeNode> ExitNodes = new List<CommonComputeNode>();

        internal static CommonComputeNode GetOrigin(ClockRotationDirection clockDirection = ClockRotationDirection.Clockwise)
        {
            ComputableNodeCount = 0;
            ExitNodes.Clear();

            switch (clockDirection)
            {
                case ClockRotationDirection.Counterclockwise:
                    return ComputeNodeFactory.GetDividedBy2(OriginalValue, clockDirection);
                case ClockRotationDirection.Clockwise:
                default:
                    return ComputeNodeFactory.GetPlus7(OriginalValue, clockDirection);
            }
        }

        #region Breadth First Search.

        internal static CommonComputeNode TryBreadthFirstSearchExitNode(List<CommonComputeNode> siblingNodes)
        {
            if (siblingNodes.Count.Equals(0))
                return null;

            bool isLessThanMaxDepth = (siblingNodes[0].Depth < MaxDepth);
            List<CommonComputeNode> nextSiblingNodes = new List<CommonComputeNode>();
            foreach (CommonComputeNode siblingNode in siblingNodes)
            {
                if (!siblingNode.IsComputable)
                    continue;

                siblingNode.Compute();
                ComputableNodeCount++;

                if (siblingNode.IsExitNode())
                    return siblingNode;

                if (isLessThanMaxDepth)
                {
                    siblingNode.AppendChildNodes();
                    nextSiblingNodes.AddRange(siblingNode.ChildNodes);
                }
            }

            return TryBreadthFirstSearchExitNode(nextSiblingNodes);
        }

        #endregion

        #region Depth First search.

        internal static CommonComputeNode TryDepthFirstSearchExitNode(CommonComputeNode node)
        {
            if (!node.IsComputable
                || IsExceededMaxDepath(node.Depth))
                return null;

            node.Compute();
            ComputableNodeCount++;

            if (node.IsExitNode())
                return node;

            CommonComputeNode returnNode = null;
            node.AppendChildNodes();
            foreach (CommonComputeNode childNode in node.ChildNodes)
            {
                returnNode = TryDepthFirstSearchExitNode(childNode);
                if (returnNode != null)
                    break;
            }
            return returnNode;
        }

        #endregion

        private static bool IsExceededMaxDepath(int nodeDepth)
        {
            return nodeDepth > MaxDepth;
        }

        private static bool IsExitNode(this CommonComputeNode node)
        {
            return DesiredValue.Equals(node.Result) && node.CanQuit();
        }
        private static bool CanQuit(this CommonComputeNode node)
        {
            return IsClockwiseMultipliedBy3(node) || IsCounterclockwiseMinus5(node);
        }
        private static bool IsCounterclockwiseMinus5(CommonComputeNode node)
        {
            return (node.OperatorWithRightOperandSign.Equals("-5") && node.RotationDirection.Equals(ClockRotationDirection.Counterclockwise));
        }
        private static bool IsClockwiseMultipliedBy3(CommonComputeNode node)
        {
            return (node.OperatorWithRightOperandSign.Equals("×3") && node.RotationDirection.Equals(ClockRotationDirection.Clockwise));
        }
    }
    internal static class ComputeNodeFactory
    {
        internal static CommonComputeNode GetPlus7(int inputValue, ClockRotationDirection direction)
        {
            return new Plus7(inputValue, direction);
        }
        internal static CommonComputeNode GetDividedBy2(int inputValue, ClockRotationDirection direction)
        {
            return new DividedBy2(inputValue, direction);
        }

        internal static void AppendChildNodes(this CommonComputeNode node)
        {
            switch (node.OperatorWithRightOperandSign)
            {
                case "+7":
                    AppendPlus7ChildNodes(node);
                    break;
                case "÷2":
                    AppendDividedBy2ChildNodes(node);
                    break;
                case "×3":
                    AppendMultipliedBy3ChildNodes(node);
                    break;
                case "-5":
                    AppendMinus5ChildNodes(node);
                    break;
            }
        }
        private static void AppendMinus5ChildNodes(CommonComputeNode node)
        {
            switch (node.RotationDirection)
            {
                case ClockRotationDirection.Clockwise:
                    node.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise))
                        .AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise))
                        .AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise));
                    break;
                case ClockRotationDirection.Counterclockwise:
                    node.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Counterclockwise));
                    break;
            }
        }
        private static void AppendMultipliedBy3ChildNodes(CommonComputeNode node)
        {
            switch (node.RotationDirection)
            {
                case ClockRotationDirection.Clockwise:
                    node.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Clockwise));
                    break;
                case ClockRotationDirection.Counterclockwise:
                    node.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise))
                        .AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise))
                        .AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise));
                    break;
            }
        }
        private static void AppendDividedBy2ChildNodes(CommonComputeNode node)
        {
            switch (node.RotationDirection)
            {
                case ClockRotationDirection.Clockwise:
                    node.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Clockwise));
                    break;
                case ClockRotationDirection.Counterclockwise:
                    node.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise))
                        .AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise))
                        .AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise));
                    break;
            }
        }
        private static void AppendPlus7ChildNodes(CommonComputeNode node)
        {
            switch (node.RotationDirection)
            {
                case ClockRotationDirection.Clockwise:
                    node.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise))
                        .AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise))
                        .AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise));
                    break;
                case ClockRotationDirection.Counterclockwise:
                    node.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Counterclockwise));
                    break;
            }
        }
    }
    public abstract class CommonComputeNode
    {
        public abstract string OperatorWithRightOperandSign { get; }
        public abstract int Compute();

        public int LeftOperand { get; private set; }
        public int Depth { get; private set; }

        public virtual bool IsComputable
        {
            get { return true; }
        }
        public string Expression
        {
            get { return string.Format("{0}{1}", LeftOperand, OperatorWithRightOperandSign); }
        }
        public ClockRotationDirection RotationDirection { get; private set; }
        public int? Result { get; protected set; }
        public CommonComputeNode ParentNode { get; private set; }
        public List<CommonComputeNode> ChildNodes { get; private set; }

        protected CommonComputeNode(int leftOperandValue, ClockRotationDirection clockDirection)
        {
            LeftOperand = leftOperandValue;
            RotationDirection = clockDirection;
            ChildNodes = new List<CommonComputeNode>();
        }

        public CommonComputeNode AddChildNode(CommonComputeNode childNode)
        {
            ChildNodes.Add(childNode);
            childNode.ParentNode = this;
            childNode.Depth = Depth + 1;

            return this;
        }
        public List<CommonComputeNode> GetPath()
        {
            List<CommonComputeNode> path = new List<CommonComputeNode>();

            CommonComputeNode node = this;
            do
            {
                path.Add(node);
                node = node.ParentNode;
            } while (node != null);
            path.Reverse();

            return path;
        }
        public string GetExpressionPathString(string separator = ">")
        {
            return string.Join(separator
                , GetPath()
                    .Select<CommonComputeNode, string>(node => node.Expression)
                    .ToList()
                    .ToArray());
        }
    }
    public class Plus7 : CommonComputeNode
    {
        public override string OperatorWithRightOperandSign
        {
            get { return "+7"; }
        }

        public Plus7(int inputValue, ClockRotationDirection direction)
            : base(inputValue, direction) { }

        public override int Compute()
        {
            Result = LeftOperand + 7;
            return Result.Value;
        }
    }
    public class DividedBy2 : CommonComputeNode
    {
        public override string OperatorWithRightOperandSign
        {
            get { return "÷2"; }
        }

        public DividedBy2(int inputValue, ClockRotationDirection direction)
            : base(inputValue, direction) { }

        public override int Compute()
        {
            Result = LeftOperand / 2;
            return Result.Value;
        }

        public override bool IsComputable
        {
            get { return IsDivisibleBy2(); }
        }
        private bool IsDivisibleBy2()
        {
            return (LeftOperand % 2).Equals(0);
        }
    }
    public class MultipliedBy3 : CommonComputeNode
    {
        public override string OperatorWithRightOperandSign
        {
            get { return "×3"; }
        }

        public MultipliedBy3(int inputValue, ClockRotationDirection direction)
            : base(inputValue, direction) { }

        public override int Compute()
        {
            Result = LeftOperand * 3;
            return Result.Value;
        }
    }
    public class Minus5 : CommonComputeNode
    {
        public override string OperatorWithRightOperandSign
        {
            get { return "-5"; }
        }

        public Minus5(int inputValue, ClockRotationDirection direction)
            : base(inputValue, direction) { }

        public override int Compute()
        {
            Result = LeftOperand - 5;
            return Result.Value;
        }
    }

    public enum ClockRotationDirection
    {
        Clockwise = 0,
        Counterclockwise = 1
    }

    #endregion
}