问题描述:
有一个3×3的棋盘,其中有0~8九个数字,0表示空格,其他的数字可以和0交换位置。求由初始状态到达目标状态步数最少的解。
解决八数码问题的常用方法为图搜索法,可用广度优先、深度优先和A*算法实现,其中A*算法又因估价函数的不同而有着不同的搜索时间。
用A算法可以得到较好的搜索策略,普通的宽度优先搜索在这个例子中生成了27个状态,有效地搜索状态仅为5个。用A算法,加入了估价函数,中间的生成状态仅为5个,对于这个例子可能有点特殊。但是说明了A算法的效率优势。
这个算法对前一算法进行了部分的该进,主要是增加了A算法的实现,优化了函数主题部分(49-78行),去掉了多余的累赘代码,在86-170行代码。用的估价函数为:状态的深度和状态不在位的节点数之和。
程序说明:
在本程序中,A算法、实现了八数码问题, 初始状态默认为: 目标状态为:
2 8 3 1 2 3
1 0 4 7 8 4
7 6 5 0 6 5
程序实现:
Node n = new Node();
n.ID = 1;
n.Metrix = new int[,] { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
ArrayCopy( n.Metrix ,SourceMetrix);
n.PID=1;
open.Add(n);
int i = 1;
while (open.Count >= 1)
{
Node current = open[0];
open.RemoveAt(0);
colse.Add(current);
if (IsEnd(current, TargetMetrix) == 1)
{
PrintPath(colse);
break;
}
Node parent = new Node();
foreach (Node nn in colse)
{
if (current.PID == nn.ID)
{
parent = nn;
break ;
}
}
if (IsMove(current, parent, Move.Left) == 1)
{
i++;
Node tNode = CreateNewNode(i, current.ID, current.Metrix, Move.Left);
open.Add(tNode);
EnableAAgroithms();
}
if (IsMove(current, parent, Move.Top) == 1)
{
i++;
Node tNode = CreateNewNode(i, current.ID, current.Metrix, Move.Top);
open.Add(tNode);
EnableAAgroithms();
}
if (IsMove(current, parent, Move.Right) == 1)
{
i++;
Node tNode = CreateNewNode(i, current.ID, current.Metrix, Move.Right);
open.Add(tNode);
EnableAAgroithms();
}
if (IsMove(current, parent, Move.Bottom) == 1)
{
i++;
Node tNode = CreateNewNode(i, current.ID, current.Metrix, Move.Bottom);
open.Add(tNode);
EnableAAgroithms();
}
}
}
/// <summary>
/// 启用A算法
/// </summary>
/// <returns></returns>
private static int EnableAAgroithms()
{
List<Node> tmp = new List<Node>();
foreach (Node n in open)
{
Node t = n;
t.Fs = GetEFunction(t);
if (tmp.Count >= 1)
{
int index = 0;
for (int i = 0; i < tmp.Count; i++)
{
if (t.Fs > tmp[i].Fs)
{
index++;
}
}
tmp.Insert(index ,t);
}
else
{
tmp.Add(t);
}
}
open = tmp;
return 1;
}
/// <summary>
/// 取的当前节点的估计函数值
/// </summary>
/// <param name="curr"></param>
/// <returns></returns>
private static int GetEFunction(Node curr)
{
int depth = GetStateDepth(curr);
int offet = GetOffsetEles(curr.Metrix);
return (depth + offet)>0?(depth + offet):0;
}
/// <summary>
/// 取的不在位的元素值
/// </summary>
/// <param name="source"></param>
/// <param name="target"></param>
/// <returns></returns>
private static int GetOffsetEles(int[,] source)
{
int val=0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (source[i, j] != TargetMetrix[i, j])
{
val++;
}
}
}
return val;
}
/// <summary>
/// 取的扩展状态深度
/// </summary>
/// <param name="curr"></param>
/// <returns></returns>
private static int GetStateDepth(Node curr)
{
int i=colse .Count-1;
int depth = 0;
Node tmp = curr;
if (i >= 0)
{
for (; i >= 0; i--)
{
if (colse[i].ID == tmp.PID)
{
depth++;
tmp = colse[i];
}
}
}
return depth;
}
private static Node CreateNewNode(int id,int pid,int[,]metrix,Move move)
{
Node tmp = new Node();
tmp.ID = id;
tmp.PID = pid;
int[,] t = new int[,] { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
ArrayCopy(t, metrix);
tmp.Metrix = MetrixMove(t, move);
return tmp;
}
private static int[,] ArrayCopy(int [,] s,int [,] t)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
s[i,j] = t[i,j];
}
}
return s;
}
/// <summary>
/// 移动状态
/// </summary>
/// <param name="array"></param>
/// <param name="move"></param>
/// <returns></returns>
private static int[,] MetrixMove(int [,] array, Move move)
{
int[,] tmp = { {0,0,0},{0,0,0},{0,0,0}};
ArrayCopy(tmp,array);
int row = -1;
int col = -1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (tmp[i,j] == 0)
{
row = i;
col = j;
break;
}
}
if ((row != -1) && (col != -1))
{
break;
}
}
if ((row >= 0 || row <= 2) && (col >= 0 || col <= 2))
{
int i = row;
int j = col;
//Move m = move;
switch (move)
{
case Move.Left:
j--;
// m = Move.Right;
break;
case Move.Top:
i--;
//m = Move.Bottom;
break;
case Move.Right:
j++;
//m = Move.Left;
break;
case Move.Bottom:
i++;
//m = Move.Top;
break;
default:
break;
}
if ((i >= 0 && i <= 2) && (j >= 0 && j <= 2))
{
//int[][] mt = MetrixMove(tmp, row, col, m);
return MetrixMove(tmp,row,col,move);
}
}
return tmp;
}
/// <summary>
/// 移动状态
/// </summary>
/// <param name="m">状态矩阵</param>
/// <param name="row"></param>
/// <param name="col"></param>
/// <param name="move"></param>
/// <returns></returns>
private static int[,] MetrixMove(int[,] m, int row, int col, Move move)
{
int[,] tmp = { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
ArrayCopy(tmp, m);
if ((m != null) && (row >= 0 && row <= 2) && (col >= 0 && col <= 2))
{
int i = row;
int j = col;
switch (move)
{
case Move .Left:
j--;
break;
case Move .Top :
i--;
break;
case Move .Right :
j++;
break;
case Move .Bottom :
i++;
break;
default :
i = -1;
j = -1;
break;
}
if ((i >= 0 && i <= 2) && (j >= 0 && j <= 2))
{
int val = tmp[i,j];
tmp[i,j] = tmp[row,col];
tmp[row,col] = val;
}
else
{
return null;
}
}
else
{
return null;
}
return tmp;
}
/// <summary>
/// 判断当前状态是否可以移动操作
/// </summary>
/// <param name="n"></param>
/// <param name="p"></param>
/// <param name="move"></param>
/// <returns></returns>
private static int IsMove(Node n, Node p, Move move)
{
if (n.PID == n.ID)
{
return 1;
}
int row = -1;
int col = -1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (n.Metrix[i,j] == 0)
{
row = i;
col = j;
break;
}
}
if ((row != -1) && (col != -1))
{
break;
}
}
if ((row >= 0 || row <= 2) && (col >= 0 || col <= 2))
{
int i = row;
int j = col;
Move m = move;
switch (move)
{
case Move.Left:
j--;
break;
case Move.Top:
i--;
break;
case Move.Right:
j++;
break;
case Move.Bottom:
i++;
break;
default:
break;
}
if ((i >= 0 && i <= 2) && (j >= 0 && j <= 2))
{
int[,] mt = MetrixMove(n.Metrix ,row,col,m);
if ((mt != null))
{
if (IsTheSameMetrix(mt, p.Metrix) == 0)
{
return 1;
}
}
}
}
return 0;
}
/// <summary>
/// 判断连个矩阵元素是否相同
/// </summary>
/// <param name="m1"></param>
/// <param name="m2"></param>
/// <returns>0 否,1 是</returns>
private static int IsTheSameMetrix(int[,] m1, int[,] m2)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (m1[i,j] !=m2[i,j])
{
return 0;
}
}
}
return 1;
}
/// <summary>
/// 判断当前状态是否是目标状态
/// </summary>
/// <param name="node">状态节点</param>
/// <param name="target">目标矩阵值</param>
/// <returns></returns>
private static int IsEnd(Node node, int [,]target)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (node.Metrix[i,j] != target[i,j])
{
return 0;
}
}
}
return 1;
}
/// <summary>
/// 输出搜索路径
/// </summary>
/// <param name="list"></param>
private static void PrintPath(List<Node> list)
{
if (null == list)
{
return;
}
Console.WriteLine("Generate {0} states.Path is :",list.Count);
List<Node> tmp = new List<Node>();
int pid = list[list.Count - 1].PID;
tmp.Add(list[list.Count - 1]);
for (int i = list.Count - 2; i >= 0; i--)
{
if (list[i].ID == pid)
{
tmp.Add(list[i]);
pid = list[i].PID;
}
}
for (int j = tmp.Count - 1; j >= 0; j--)
{
PrintMetrix(tmp[j].Metrix);
}
}
/// <summary>
/// 输出一个矩阵
/// </summary>
/// <param name="m"></param>
private static void PrintMetrix(int[,] m)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
Console.Write("{0}/t", m[i, j]);
}
Console.WriteLine();
}
Console.WriteLine("**************************");
}
}
/// <summary>
/// 状态空间数据结构
/// </summary>
struct Node
{
public int ID;
public int [,] Metrix ;
public int PID;
public int Fs;
}
}