fenyou.cs

用广度优先搜索算法解决两个小孩的分油问题.盲目搜索算法.

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;


namespace FenYou
{
    class FenYou
    {
        static void Main(string[] args)
        {
         

            Queue N = new Queue();  // 要访问的结点
            ArrayList  NPass = new ArrayList(); //已经访问过的结点

            CurrentState IinitialN = new CurrentState();//初始状态
            N.Enqueue(IinitialN);  


            Console.WriteLine("初始状态：(" + IinitialN.CA/10 + "," + (double)IinitialN.CB7/10 + "," + (double)IinitialN.CB3/10 + ")\n");

            string output1, output2, answer; //output1输出当前已访问节点，output2输出即将访问节点，answer为分油成功的步骤。

            CurrentState firstnote = IinitialN;

            while (firstnote.CA != 5&& firstnote.CB7 != 5)
            {
                //检查节点是否已经访问过？
                foreach (CurrentState i in NPass)
                {
                    if (firstnote.CA == i.CA && firstnote.CB7 == i.CB7 && firstnote.CB3 == i.CB3)
                    {
                        firstnote = (CurrentState)N.Dequeue();
                        if (N.Count == 0)
                            return;
                    }

                }

               

             
                for (int k = 1; k < 7; k++)  //节点展开
                {

                    CurrentState m1 = null;

                    switch (k)
                    {
                        case 1:
                            if (firstnote.CA > 0) //用一斤瓶灌满7两瓶
                            {
                                CurrentState m = new CurrentState(firstnote.CA + firstnote.CB7 - 7, 7, firstnote.CB3, firstnote);
                                m1 = m;
                            }

                            break;

                        case 2:
                            if (firstnote.CA > 0) //用一斤瓶灌满3两瓶
                            {
                                CurrentState m = new CurrentState(firstnote.CA + firstnote.CB3 - 3, firstnote.CB7, 3, firstnote);
                                m1 = m;
 
                            }
                            break;

                        case 3:
                            if (firstnote.CB3 > 0) //用3两瓶灌入一斤瓶
                            {
                                CurrentState m = new CurrentState(firstnote.CA + firstnote.CB3, firstnote.CB7, 0, firstnote);
                                m1 = m;
                            }
                            break;

                        case 4:
                            if (firstnote.CB7 > 0) //用7两瓶灌入一斤瓶
                            {
                                CurrentState m = new CurrentState(firstnote.CA + firstnote.CB7, 0, firstnote.CB3, firstnote);
                                m1 = m;
                            }
                            break;

                        case 5:
                            if (firstnote.CB7 > 0 && firstnote.CB3 < 3) //用7两瓶灌入3两瓶
                            {
                                if ((firstnote.CB3 + firstnote.CB7) > 3)
                                {
                                    CurrentState m = new CurrentState(firstnote.CA, firstnote.CB7 + firstnote.CB3 - 3, 3, firstnote);
                                    m1 = m;
                                }
                                else
                                {
                                    CurrentState m = new CurrentState(firstnote.CA, 0, firstnote.CB7+firstnote.CB3, firstnote);
                                    m1 = m;
                                }
                           
                            }
                            break;
                        
                        case 6:
                            if (firstnote.CB7 < 7 && firstnote.CB3 > 0) //用3两瓶灌入7两瓶
                            {
                                if ((firstnote.CB3 + firstnote.CB7) > 7)
                                {
                                    CurrentState m = new CurrentState(firstnote.CA, 7, firstnote.CB3 + firstnote.CB7 - 7, firstnote);
                                    m1 = m;
                                }
                                else
                                {
                                    CurrentState m = new CurrentState(firstnote.CA, firstnote.CB3 + firstnote.CB7, 0, firstnote);
                                    m1 = m;
                                }
                            }
                           break;

                    }


                    if (m1 != null)  //判断是否出现答案，如果有，输出结果。
                    {
                        N.Enqueue(m1);
                        if (m1.CA == 5 && m1.CB7 == 5)
                        {
                            answer = "Success:\n";
                            while (m1 != null)
                            {
                                answer +="("+(double)m1.CA/10+","+(double)m1.CB7/10+","+(double)m1.CB3/10+")\n";
                                //Console.WriteLine( answer);
                                m1 = m1.Father;
                            }
                            Console.WriteLine("分油答案:\n"+answer);


                            //distime.Stop();
                            //distime.ToString();

                            return;
                        }

   

                    }
                }

                CurrentState newnote = null;
                newnote = firstnote;
                NPass.Add(newnote);

                firstnote = (CurrentState)N.Dequeue();


            }

        }   
    }
}