📄 node.cs
字号:
using System;
using System.Collections;
namespace chessAlg
{
/// <summary>
/// Summary description for node.
/// </summary>
public class Node
{
public String name;//名字，备用
public Node father;//父节点引用
public String arrayNodeString;//当前状态字符串，按array[0]-->array[8]顺序排列
public String arrayNodeString1;//初始字符串
public String arrayNodeString2;//目标字符串
public int depth;//深度
public int va;//启发函数值
public Node(Node f,String s,String s1,String s2,int d)//构造函数
{
father=f;
arrayNodeString=s;
arrayNodeString1=s1;
arrayNodeString2=s2;
depth=d;
va=Value();//算f值
}
private int Value()//算f值
{
//int re=ValueP()+3*ValueS()+depth;
//int re=depth;
int re=ValueP()+depth;
return re;
}
private int Value(String ss)//同上
{
int re=ValueP(ss)+3*ValueS(ss)+depth;
return re;
}
private int ValueP()//算P值
{
int p=0;
for(int i=0;i<=8;i++)
{
p+=Distance(int.Parse(arrayNodeString[i].ToString()),arrayNodeString2.IndexOf(arrayNodeString[i].ToString()));
}
return p;
}
private int ValueP(String ss)//同上
{
int p=0;
for(int i=0;i<=8;i++)
{
p+=Distance(int.Parse(ss[i].ToString()),arrayNodeString2.IndexOf(ss[i].ToString()));
}
return p;
}
private int Distance(int i,int j)//算距离
{
int d=0;
switch(i)
{
case 0:
switch(j)
{
case 0:
d=0;
break;
case 1:
d=1;
break;
case 2:
d=2;
break;
case 3:
d=1;
break;
case 4:
d=2;
break;
case 5:
d=3;
break;
case 6:
d=2;
break;
case 7:
d=3;
break;
case 8:
d=4;
break;
}
break;
case 1:
switch(j)
{
case 0:
d=1;
break;
case 1:
d=0;
break;
case 2:
d=1;
break;
case 3:
d=2;
break;
case 4:
d=1;
break;
case 5:
d=2;
break;
case 6:
d=3;
break;
case 7:
d=2;
break;
case 8:
d=3;
break;
}//
break;
case 2:
switch(j)
{
case 0:
d=2;
break;
case 1:
d=1;
break;
case 2:
d=0;
break;
case 3:
d=3;
break;
case 4:
d=2;
break;
case 5:
d=1;
break;
case 6:
d=4;
break;
case 7:
d=3;
break;
case 8:
d=2;
break;
}
break;
case 3:
switch(j)
{
case 0:
d=1;
break;
case 1:
d=2;
break;
case 2:
d=3;
break;
case 3:
d=0;
break;
case 4:
d=1;
break;
case 5:
d=2;
break;
case 6:
d=1;
break;
case 7:
d=2;
break;
case 8:
d=3;
break;
}
break;
case 4:
switch(j)
{
case 0:
d=2;
break;
case 1:
d=1;
break;
case 2:
d=2;
break;
case 3:
d=1;
break;
case 4:
d=0;
break;
case 5:
d=1;
break;
case 6:
d=2;
break;
case 7:
d=1;
break;
case 8:
d=2;
break;
}
break;
case 5://
switch(j)
{
case 0:
d=3;
break;
case 1:
d=2;
break;
case 2:
d=1;
break;
case 3:
d=2;
break;
case 4:
d=1;
break;
case 5:
d=0;
break;
case 6:
d=3;
break;
case 7:
d=2;
break;
case 8:
d=1;
break;
}
break;
case 6:
switch(j)
{
case 0:
d=2;
break;
case 1:
d=3;
break;
case 2:
d=4;
break;
case 3:
d=1;
break;
case 4:
d=2;
break;
case 5:
d=3;
break;
case 6:
d=0;
break;
case 7:
d=1;
break;
case 8:
d=2;
break;
}
break;
case 7:
switch(j)
{
case 0:
d=3;
break;
case 1:
d=2;
break;
case 2:
d=3;
break;
case 3:
d=2;
break;
case 4:
d=1;
break;
case 5:
d=2;
break;
case 6:
d=1;
break;
case 7:
d=0;
break;
case 8:
d=1;
break;
}
break;
case 8:
switch(j)
{
case 0:
d=4;
break;
case 1:
d=3;
break;
case 2:
d=2;
break;
case 3:
d=3;
break;
case 4:
d=2;
break;
case 5:
d=1;
break;
case 6:
d=2;
break;
case 7:
d=1;
break;
case 8:
d=0;
break;
}
break;
}
return d;
}
private int ValueS()//算S值
{
int s=0;
if(arrayNodeString[4]=='0') s+=1;
if(!IsClockWise(arrayNodeString[0],arrayNodeString[1])) s+=2;
if(!IsClockWise(arrayNodeString[1],arrayNodeString[2])) s+=2;
if(!IsClockWise(arrayNodeString[2],arrayNodeString[5])) s+=2;
if(!IsClockWise(arrayNodeString[5],arrayNodeString[8])) s+=2;
if(!IsClockWise(arrayNodeString[8],arrayNodeString[6])) s+=2;
if(!IsClockWise(arrayNodeString[6],arrayNodeString[3])) s+=2;
if(!IsClockWise(arrayNodeString[3],arrayNodeString[0])) s+=2;
return s;
}
private int ValueS(String ss)//同上
{
int s=0;
if(ss[4]=='0') s+=1;
if(!IsClockWise(ss[0],ss[1])) s+=2;
if(!IsClockWise(ss[1],ss[2])) s+=2;
if(!IsClockWise(ss[2],ss[5])) s+=2;
if(!IsClockWise(ss[5],ss[8])) s+=2;
if(!IsClockWise(ss[8],ss[6])) s+=2;
if(!IsClockWise(ss[6],ss[3])) s+=2;
if(!IsClockWise(ss[3],ss[0])) s+=2;
return s;
}
private bool IsClockWise(char a,char b)//判断是否顺时针
{
bool re=true;
String s="0125863";
int pos1=arrayNodeString2.IndexOf(a);
int pos2=arrayNodeString2.IndexOf(b);
if(pos1==4||pos2==4)
re=false;
else if(s.IndexOf(pos1.ToString())>s.IndexOf(pos2.ToString()))
re=false;
return re;
}
public Node()
{
}
public bool IsEqual(String s)//判断字符串是否相等
{
if(arrayNodeString==s)
return true;
else return false;
}
public Node[] GetChildNodes(ArrayList nodeList)//取得扩展节点集（已扩展节点集）
{
int pos=arrayNodeString.IndexOf("0");
ArrayList list=new ArrayList();
int[] p;
switch(pos)
{
case 0:
p=new int[2];
p[0]=1;
p[1]=3;
Do(list,p,arrayNodeString);
break;
case 1:
p=new int[2];
p[0]=0;
p[1]=2;
Do(list,p,arrayNodeString);
break;
case 2:
p=new int[2];
p[0]=1;
p[1]=5;
Do(list,p,arrayNodeString);
break;
case 3:
p=new int[3];
p[0]=0;
p[1]=4;
p[2]=6;
Do(list,p,arrayNodeString);
break;
case 4:
p=new int[4];
p[0]=1;
p[1]=3;
p[2]=5;
p[3]=7;
Do(list,p,arrayNodeString);
break;
case 5:
p=new int[3];
p[0]=2;
p[1]=4;
p[2]=8;
Do(list,p,arrayNodeString);
break;
case 6:
p=new int[2];
p[0]=3;
p[1]=7;
Do(list,p,arrayNodeString);
break;
case 7:
p=new int[3];
p[0]=4;
p[1]=6;
p[2]=8;
Do(list,p,arrayNodeString);
break;
case 8:
p=new int[2];
p[0]=5;
p[1]=7;
Do(list,p,arrayNodeString);
break;
}
CompareList(list,nodeList);//对list作处理，取出重复状态
return ArrayList2NodeArray(this,list);//转Node数组
}
public Node[] GetChildNodes_AStar(ArrayList nodeList1,ArrayList nodeList2)//A*算法的取得扩展子节点
{
int pos=arrayNodeString.IndexOf("0");
ArrayList list=new ArrayList();
int[] p;
switch(pos)
{
case 0:
p=new int[2];
p[0]=1;
p[1]=3;
Do(list,p,arrayNodeString);
break;
case 1:
p=new int[2];
p[0]=0;
p[1]=2;
Do(list,p,arrayNodeString);
break;
case 2:
p=new int[2];
p[0]=1;
p[1]=5;
Do(list,p,arrayNodeString);
break;
case 3:
p=new int[3];
p[0]=0;
p[1]=4;
p[2]=6;
Do(list,p,arrayNodeString);
break;
case 4:
p=new int[4];
p[0]=1;
p[1]=3;
p[2]=5;
p[3]=7;
Do(list,p,arrayNodeString);
break;
case 5:
p=new int[3];
p[0]=2;
p[1]=4;
p[2]=8;
Do(list,p,arrayNodeString);
break;
case 6:
p=new int[2];
p[0]=3;
p[1]=7;
Do(list,p,arrayNodeString);
break;
case 7:
p=new int[3];
p[0]=4;
p[1]=6;
p[2]=8;
Do(list,p,arrayNodeString);
break;
case 8:
p=new int[2];
p[0]=5;
p[1]=7;
Do(list,p,arrayNodeString);
break;
}
CompareList_AStar(list,nodeList1,nodeList2);
return ArrayList2NodeArray(this,list);
}
private void Do(ArrayList list,int[] pos,String ss)
{
String s;
for(int i=0;i<pos.Length;i++)
{
s=ss;
int m=pos[i];
s=ChangePos(s,"0",s[m].ToString());
list.Add(s);
}
}
private String ChangePos(String s,String a,String b)//a,b作交换
{
int pos1=s.IndexOf(a);
int pos2=s.IndexOf(b);
s=s.Replace(a,"c");
s=s.Replace(b,"d");
s=s.Replace("c",b);
s=s.Replace("d",a);
return s;
}
private void CompareList(ArrayList StringList,ArrayList nodeList)//比较是否存在
{
for(int i=0;i<StringList.Count;i++)
{
for(int j=0;j<nodeList.Count;j++)
{
if((String) StringList[i]==((Node) nodeList[j]).arrayNodeString)
{
StringList.RemoveAt(i);
i--;
break;
}
}
}
}
private void CompareList_AStar(ArrayList StringList,ArrayList nodeList1,ArrayList nodeList2)//A*算法的扩展节点处理
{
for(int i=0;i<StringList.Count;i++)//查open
{
int flag=0;
for(int j=0;j<nodeList1.Count;j++)
{
if((String) StringList[i]==((Node) nodeList1[j]).arrayNodeString)//open已有
{
int c1=this.depth+1;
int c2=((Node) nodeList1[j]).depth;
if(c1<c2) //f更好
{
((Node) nodeList1[j]).va=((Node) nodeList1[j]).va-((Node) nodeList1[j]).depth+this.depth+1;//改f
((Node) nodeList1[j]).depth=this.depth+1;//改深度
((Node) nodeList1[j]).father=this;//改指针
}
flag=1;
break;
}
}
if(flag==0)
{
for(int j=0;j<nodeList2.Count;j++)
{
if((String) StringList[i]==((Node) nodeList2[j]).arrayNodeString)
{
int c1=this.depth+1;
int c2=((Node) nodeList2[j]).depth;
if(c1<c2)
{
((Node) nodeList2[j]).va=((Node) nodeList2[j]).va-((Node) nodeList2[j]).depth+this.depth+1;
((Node) nodeList2[j]).depth=this.depth+1;
((Node) nodeList2[j]).father=this;
nodeList1.Add((Node) nodeList2[j]);
nodeList2.RemoveAt(j);
//j--;
}
flag=2;
break;
}
}
}
if(flag!=0)
{
StringList.RemoveAt(i);
i--;
}
}
}
private Node[] ArrayList2NodeArray(Node father,ArrayList list)//转node数组
{
Node[] n=new Node[list.Count];
for(int i=0;i<list.Count;i++)
{
n[i]=new Node(this,(String) list[i],arrayNodeString1,arrayNodeString2,this.depth+1);
}
return n;
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -