chessalg.cs

8数码难题 深、广、a*

using System;
using System.Collections;

namespace chessAlg
{
	/// <summary>
	/// Summary description for Class1.
	/// </summary>
	public class ChessAlg
	{
		private int[][] array;
		private String arrayNodeString;
		private String arrayNodeString1;
		private String arrayNodeString2;
		private ArrayList Open;
		private ArrayList Closed;
		public ArrayList Result;
		private Node Last;
		private Node startNode;

		
		public ChessAlg(int[][] a1,int[][] a2)//构造函数
		{
			Open=new ArrayList();
			Closed=new ArrayList();
			Result=new ArrayList();

			arrayNodeString="";
			arrayNodeString1=Array2String(a1);
			arrayNodeString2=Array2String(a2);
			startNode=new Node(null,arrayNodeString1,arrayNodeString1,arrayNodeString2,0);
		}
		public ChessAlg()
		{

		}
		public bool Run(String s)//运行入口
		{
			bool re=true;

			if(s=="宽度优先")
			{
				if((re=BreadthFirst())==true)
				{
					Node r=Last;
					while(r.father!=null)
					{
						Result.Add(r);
						r=r.father;
					}
				}
				else re=false;
			}
			if(s=="深度优先")
			{
				if((re=DepthFirst())==true)
				{
					Node r=Last;
					while(r.father!=null)
					{
						Result.Add(r);
						r=r.father;
					}
				}
				else re=false;
			}
			if(s=="A*算法")
			{
				if((re=AStar())==true)
				{
					Node r=Last;
					while(r.father!=null)
					{
						Result.Add(r);
						r=r.father;
					}
				}
				else re=false;
			}
			return re;

		}
		

		private bool BreadthFirst()//宽度优先
		{
			int DEPTH=25;
			if(startNode.arrayNodeString1==startNode.arrayNodeString2)
			{
				Last=startNode;
				return true;
			}
			else
			{
				Open.Add(startNode);
				bool c=true;
				bool re=true;
				while(c)
				{
					if(Open.Count==0)
					{
						re=false;
						break;
					}
					else
					{
						Closed.Add(Open[0]);
						if(((Node)Open[0]).depth!=DEPTH)
						{
							Node[] n=((Node)Open[0]).GetChildNodes(Closed);
							Open.RemoveAt(0);
							for(int i=0;i<n.Length;i++)
							{
								Open.Add(n[i]);
								if(n[i].arrayNodeString==arrayNodeString2)
								{
									Last=n[i];
									re=true;
									c=false;
									break;
								}
							}
						}
						else 
						{
							Open.RemoveAt(0);
						}
					}
					
				}
				return re;
			}
			
			
		}
	
		public bool DepthFirst()//深度优先
		{
			int DEPTH=25;
			if(startNode.arrayNodeString1==startNode.arrayNodeString2)
			{
				Last=startNode;
				return true;
			}
			else
			{
				Open.Add(startNode);
				bool c=true;
				bool re=true;
				while(c)
				{
					if(Open.Count==0)
					{
						re=false;
						break;
					}
					else
					{
						Closed.Add(Open[0]);
						if(((Node)Open[0]).depth!=DEPTH)
						{
							Node[] n=((Node)Open[0]).GetChildNodes(Closed);
							Open.RemoveAt(0);
							for(int i=0;i<n.Length;i++)
							{
								Open.Insert(0,n[i]);
								if(n[i].arrayNodeString==arrayNodeString2)
								{
									Last=n[i];
									re=true;
									c=false;
									break;
								}
							}
						}
						else 
						{
							Open.RemoveAt(0);
						}
					}
					
				}
				return re;
			}
		}

		public bool AStar()//A*算法
		{
			int DEPTH=25;
			if(startNode.arrayNodeString1==startNode.arrayNodeString2)//是否初始节点满足条件
			{
				Last=startNode;
				return true;
			}
			else
			{
				Open.Add(startNode);//初始节点放入open
				bool c=true;
				bool re=true;
				while(c)
				{
					if(Open.Count==0)//open表为空
					{
						re=false;
						break;
					}
					else
					{
						int ss=Sort(Open);//排序

						if(((Node)Open[ss]).depth<=DEPTH)
						{
							Closed.Add(Open[ss]);
							Node temp=(Node)Open[ss];
							Open.RemoveAt(ss);
							Node[] n=temp.GetChildNodes_AStar(Open,Closed);//取扩展节点
							if(n.Length!=0)
							{
								for(int i=0;i<n.Length;i++)
								{
									Open.Add(n[i]);
									if(n[i].arrayNodeString==arrayNodeString2)
									{
										Last=n[i];
										re=true;
										c=false;
										break;
									}
								}
							}
						}
						else 
						{
							Open.RemoveAt(ss);
						}
					}
					
				}
				return re;
			}
		}

		private int Sort(ArrayList n)//排序，取得最优f的node
		{
			int k=0;
			for(int i=1;i<=n.Count-1;i++)
			{
				if(((Node)n[i]).va<((Node)n[i-1]).va) k=i;
			}
			return k;
		}

		private String Array2String(int[][] ar)//数组转字符串
		{
			String s="";
			for(int i=0;i<=2;i++)
				for(int j=0;j<=2;j++)
					s+=ar[i][j].ToString();
			return s;
		}
	}
}