depthfirstsearch.cs

c#实现的传教士野人过算法。这是一个框架

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Windows.Forms;

namespace AIShow
{
    class DepthFirstSearch
    {
        private ArrayList open;//open 表
        private ArrayList closed;//closed表
        private Graph g;//搜索图
        public State sourceState;//原始状态
        public State targetState;//目标状态
        public int result;//结果success=1，fail=0
        public TextBox textDisplay;
        
        public Graph getGraph()//返回搜索图
        {
            return g;
        }
        public void search()//求解
        {
            g = new Graph();
            GraphNode gs = new GraphNode();
            gs.nodeValue = sourceState;
            gs.pre = null;
            g.head = gs; 
            g.current=gs;
            open = new ArrayList();
            open.Add(gs);
            closed = new ArrayList();
            GraphNode n;
            while (true)
            {
                if (open.Count == 0)
                {
                    result = 0;
                    break;
 
                }
                n = (GraphNode)open[0];//获取第一个元素
                //输出过程,先换行是为了和后面配合
                if (n.pre != null)
                    textDisplay.Text +="\r\n"+ n.pre.nodeValue.description + "->";
                textDisplay.Text += n.nodeValue.description2  ;
                //找到目标节点
                if (n.nodeValue.isEqual(targetState))
                {
                    result = 1;
                    break;
                }
                open.Remove(n);
                closed.Add(n);
                //扩展n,并增加到图g中;
                ArrayList nodes=g.add(n,n.nodeValue.expandChild());
                //删除上一级节点，以防止往复运动，这个在MCState中实现 
                if (nodes.Count == 0)
                    textDisplay.Text += "*";//无法继续扩展的节点，或者目标
                //深度优先
                open.InsertRange(0,nodes);
                //宽度优先
                //open.AddRange(0,nodes);
                
            }
            
            

        }
        
        
    }
}