A*算法【拼图游戏】
2024-09-02 13:51:47
数据结构
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks; namespace 拼图
{ /// <summary>
/// 空格移动的方向
/// </summary>
enum Direction
{
None,
Up,
Left,
Right,
Down
} /// <summary>
/// 解答
/// </summary>
enum Answer
{
/// <summary>
/// 不存在解答
/// </summary>
NotExist,
/// <summary>
/// 存在解答
/// </summary>
Exist,
/// <summary>
/// 在当前指定的搜索深度内不存在解答（需要扩大深度）
/// </summary>
NotExistInDepth
} /// <summary>
/// 局面状态信息
/// </summary>
class StateMsg
{
private int depth;
private Direction dir;
public int Depth
{
get { return depth; }
}
public Direction Dir
{
get { return dir; }
} public StateMsg(int depth, Direction dir)
{
this.depth = depth;
this.dir = dir;
}
} /// <summary>
/// 局面状态
/// </summary>
class State : StateMsg
{
private long code; /// <summary>
/// 棋盘的编码
/// </summary>
public long Code
{
get { return code; }
set { code = value; }
} public State(long code, int depth, Direction dir)
: base(depth, dir)
{
this.code = code;
}
}
}
Astar类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks; namespace 拼图
{
class AStar
{ /// <summary>
/// ten[i]代表10的i次方
/// </summary>
private static readonly long[] tens = { , , , , , , , , , }; /// <summary>
/// 不是合理的编码
/// </summary>
private const int OutOfCode = -; /// <summary>
/// 标志是否找到目标状态的编码
/// </summary>
public const int WinnerCode = ; private Direction[][] dirs; private int startBoard;
private static int endBoard;
private static int[] endBoardArray; private int MaxDepth; private SortedList<long, StateMsg> openList;
private Dictionary<long, StateMsg> boardtable; private const long maxNodes = ; //至多搜索的结点数＝最大局面状态数量：（9!）=362880； private long nodes;
private int same;
private float time;
private Direction[] result; /// <summary>
/// 已经访问的结点数量
/// </summary>
public long Nodes
{
get { return nodes; }
} /// <summary>
/// 重复访问相同结点的数量
/// </summary>
public int Same
{
get { return same; }
} public float Time
{
get { return time; }
} public static int N; /// <summary>
/// 最终结果
/// </summary>
public Direction[] Result
{
get { return result; }
} public AStar(int n)
{
N = n;
dirs = new Direction[n*n][];
if(n==)
{
dirs[] = new Direction[] { Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
dirs[] = new Direction[] { Direction.Up, Direction.Left };
}
else
{
dirs[] = new Direction[] { Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down }; dirs[] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
dirs[] = new Direction[] { Direction.Up, Direction.Right };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
dirs[] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
dirs[] = new Direction[] { Direction.Up, Direction.Left };
} } /// <summary>
/// 求与目标位置不同的个数（不计空格，因此返回值0～8）
/// </summary>
/// <param name="curboard"></param>
/// <returns></returns>
public static int Different(int curboard)
{
int t_start = curboard;
int emp_start = curboard % ;
int ev = ;
//写2个for是为了减少9个if
for (int i = N*N; i > emp_start; i--)
{
t_start /= ;
if (t_start % != endBoardArray[i])
ev++;
}
for (int i = emp_start - ; i >= ; i--)
{
t_start /= ;
if (t_start % != endBoardArray[i])
ev++;
}
return ev;
} public static int getBoard(long code)
{
return (int)(code % tens[]);
} private static int getEval(long code)
{
return (int)(code / tens[]);
} private static int getEmpIndex(long code)
{
return (int)(code % );
} private static long combinCode(int board, int eval)
{
long codehead = eval * tens[];
return codehead + board;
} /// <summary>
/// 改变局面(移动空格)
/// </summary>
/// <param name="code"></param>
/// <param name="dir"></param>
public static long change(long code, Direction dir)
{
int newboard;
int eval;
int num;
int t0;
long t1;
long t2;
switch (dir)
{
case Direction.Left:
newboard = getBoard(code) - ;
if (newboard == endBoard)
return WinnerCode;
eval = Different(newboard);
return combinCode(newboard, eval);
case Direction.Right:
newboard = getBoard(code) + ;
if (newboard == endBoard)
return WinnerCode;
eval = Different(newboard);
return combinCode(newboard, eval);
case Direction.Up:
num = getBoard(code);
t0 = N*N - num % + ;
t1 = num / tens[t0];
t2 = t1 % ;
t1 = t1 - t2 + (t2 % ) * + t2 / ;
t1 *= tens[t0];
newboard = (int)(t1 + ((num % tens[t0]) - N));
if (newboard == endBoard)
return WinnerCode;
eval = Different(newboard);
return combinCode(newboard, eval);
case Direction.Down:
num = getBoard(code);
t0 = N*N - num % + - N;//跟Up不同的地方
t1 = num / tens[t0];
t2 = t1 % ;
t1 = t1 - t2 + (t2 % ) * + t2 / ;//跟Up不同的地方
t1 *= tens[t0];
newboard = (int)(t1 + ((num % tens[t0]) + N));//跟Up不同的地方
if (newboard == endBoard)
return WinnerCode;
eval = Different(newboard);
return combinCode(newboard, eval);
}
return OutOfCode;
} /// <summary>
/// 恢复上一步的局面
/// </summary>
/// <param name="code"></param>
/// <param name="dir"></param>
public long unchange(long code, Direction dir)
{
return change(code, (Direction)( - dir));
} /// <summary>
/// 当找到目标时，从哈希表里找原来的路径
/// </summary>
/// <param name="endCode"></param>
/// <param name="depth"></param>
private void setResult(long endCode, Direction curDir, Direction lastDir, int depth)
{
long lastCode = endCode;
result = new Direction[depth];
result[depth - ] = curDir;
for (int i = depth - ; i >= ; i--)
{
if (boardtable.ContainsKey(lastCode))
{
result[i] = boardtable[lastCode].Dir;
lastCode = unchange(lastCode, result[i]);
}
else
return;
}
} //本算法的核心部分
#region 带Open表和HashTable的最好优先搜索(每次扩展Open表后都对Open表排序） /// <summary>
/// 扩展Open表
/// </summary>
/// <param name="board"></param>
/// <param name="depth"></param>
private bool extentOpenList(long code, Direction lastDir, int depth)
{
int empIndex = (int)(code % - );
int len_moves = dirs[empIndex].Length;
long newcode;
Direction dir = - lastDir;
for (int i = ; i < len_moves; i++)
if (dirs[empIndex][i] != dir)
{
newcode = change(code, dirs[empIndex][i]); //跟目标匹配,结束
if (newcode == WinnerCode)
{
setResult(code, dirs[empIndex][i], lastDir, depth);
return true;
}
if (newcode <= tens[])
throw new Exception("棋盘码修改错误！ ");
if (newcode != OutOfCode)
{
if (!openList.ContainsKey(newcode))
{
if (!boardtable.ContainsKey(newcode))
openList.Add(newcode, new StateMsg(depth, dirs[empIndex][i]));
else
{
same++;
if (depth < boardtable[newcode].Depth)
{
boardtable.Remove(newcode);
openList.Add(newcode, new StateMsg(depth, dirs[empIndex][i]));
}
}
}
else
{
same++;
if (depth < openList[newcode].Depth)
openList[newcode] = new StateMsg(depth, dirs[empIndex][i]);
}
}
}
return false;
} /// <summary>
/// 带Open表和HashTable的最好优先搜索(每次扩展Open表后都对Open表排序）
/// </summary>
/// <returns></returns>
private int BestFirstSearch()
{
int depth = ;
Direction[] moves;
int board;
long newCode = combinCode(this.startBoard, );
int empIndex = getEmpIndex(newCode); moves = dirs[empIndex - ];
StateMsg data;
if (extentOpenList(newCode, Direction.None, depth))
return WinnerCode;
while (openList.Count > )
{
lock (this)
{
nodes++;
if (nodes >= maxNodes)
return -;
newCode = openList.Keys[];
board = getBoard(newCode);
data = openList[newCode];
if (data.Depth != )
{
depth = data.Depth;
if (board == endBoard)
{
return WinnerCode;
}
boardtable.Add(newCode, new StateMsg(depth, data.Dir));
openList.RemoveAt();
if (depth < MaxDepth)
if (extentOpenList(newCode, data.Dir, depth + ))
return WinnerCode;
}
}
}
return -;
} #endregion /// <summary>
/// 把一维数组的局面编码成一个整数的表示形式
/// </summary>
/// <param name="genBoard"></param>
/// <returns></returns>
public int ToIntBoard(int[] genBoard)
{
int board = ;
int emp = ;
for (int i = ; i < genBoard.Length; i++)
{
if (genBoard[i] != )
board = * board + genBoard[i];
else
emp = i + ;
}
return * board + emp;
} /// <summary>
/// 判断是否可以从初始状态到达目标状态（计算两个状态的逆序列，奇偶性相同的返回true）
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <returns></returns>
private bool ExistAns(int[] start, int[] end)
{
int sequence_start = , sequence_end = ;
for (int i = ; i < start.Length; i++)
{
if (start[i] != )
for (int j = i + ; j < start.Length; j++)
{
if (start[j] != && start[j] < start[i])
sequence_start++;
}
if (end[i] != )
for (int j = i + ; j < start.Length; j++)
{
if (end[j] != && end[j] < end[i])
sequence_end++;
}
}
return (sequence_start + sequence_end) % == ;
} /// <summary>
/// 初始化求解
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <param name="maxDepth"></param>
private void InitComp(int[] start, int[] end, int maxDepth)
{
nodes = ;
same = ;
MaxDepth = maxDepth;
result = null;
boardtable = new Dictionary<long, StateMsg>();
openList = new SortedList<long, StateMsg>();
//openStack = new Stack<State>();
//openQueue = new Queue<State>(); this.startBoard = ToIntBoard(start);
endBoard = ToIntBoard(end);
int t_end = endBoard;
int emp_end = endBoard % ;
endBoardArray = new int[N*N+];
endBoardArray[] = emp_end;
endBoardArray[emp_end] = ;
for (int i = N*N; i > emp_end; i--)
{
t_end /= ;
endBoardArray[i] = t_end % ;
}
for (int i = emp_end - ; i >= ; i--)
{
t_end /= ;
endBoardArray[i] = t_end % ;
}
} /// <summary>
/// 求解8数码问题
/// </summary>
/// <param name="start"></param>
/// <param name="end"></param>
/// <param name="maxDepth"></param>
/// <returns></returns>
public Answer Compute(int[] start, int[] end, int maxDepth)
{
if (!ExistAns(start, end))
return Answer.NotExist;
InitComp(start, end, maxDepth);
if (startBoard == endBoard)
return Answer.Exist;
long oldtime = System.DateTime.Now.Ticks;
int eval = ;
eval = BestFirstSearch();
time = (System.DateTime.Now.Ticks - oldtime) / 10000000.0f;
if (eval == WinnerCode)
return Answer.Exist;
return Answer.NotExistInDepth;
} }
}
最新文章
- 简单的c#winform象棋游戏(附带源码)
- LeetCode之389. Find the Difference
- KnockoutJS 3.X API 第五章 高级应用(2) 控制后代绑定
- JQuery官方学习资料（译）：使用JQuery的.index()方法
- 【转】解决svn Authorization failed错误
- English word
- 常用的MyEclipse快捷键
- winform 子窗体数据改变刷新父窗体 分类： WinForm 2014-05-06 18:30 246人阅读 评论(0) 收藏
- C++实现base64编码
- 转载：C# 中的委托
- MySQL如何利用索引优化ORDER BY排序语句 【转载】
- Xamarin 安装教程 支持Visual Studio 2013
- WSHPSRS-匹克选择列表生成器-SRS（R12.2.3）
- 【BZOJ1001】狼抓兔子（网络流）
- JavaScript和DOM
- c语言static关键字的理解
- JSP/JSF从web.xml中取出context-param的配置信息
- Linux：系统文件目录
- Oracle 用户，角色，权限等
- 通过cgroup给docker的CPU和内存资源做限制