{
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
digitalPos[matrix[i][j]].x = i; digitalPos[matrix[i][j]].y = j; } }
return digitalPos; }
private int cost; public int Cost {
get {
return cost; } set {
cost = value; } }
// 4*4二维数组用于存储十五数码当前节点状态 public int[][] matrix = new int[4][];
// 存储当前的父节点的引用，若当前节点为头节点，则其值设为null public _15DigitalNode parentNode; ///
/// 存储当前节点的层数 /// private int level; public int Level {
get {
return level; } }
///
/// 计算十五数码的总代价，搜索深度与不在原位置数码个数的和 ///
///
public void caculateCost(digitalPosition[] objectDigitalPos) {
cost = level;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (matrix[i][j] != 0) {
cost += matrix[i][j] == 4 * i + j + 1 ? 0 : 1; } } } }
// 扩展当前节点，扩展后的子节点，以ArrayList类型返回
public ArrayList extendChildNode(digitalPosition[] objectDigitalPos) {
ArrayList childNodes = new ArrayList(); this.findDigitalPosition(); //将零数码向下移动
if (digitalPos[0].x < 3 && this.mode != 1) {
_15DigitalNode childNode = new _15DigitalNode(this.matrix, this, this.level + 1, 2);
swap(ref childNode.matrix[digitalPos[0].x][digitalPos[0].y], ref childNode.matrix[digitalPos[0].x + 1][digitalPos[0].y]); childNode.caculateCost(objectDigitalPos); childNodes.Add(childNode); }
//将零数码向上移动
if (digitalPos[0].x > 0 && this.mode != 2) {
_15DigitalNode childNode = new _15DigitalNode(this.matrix, this, this.level + 1, 1);
swap(ref childNode.matrix[digitalPos[0].x][digitalPos[0].y], ref childNode.matrix[digitalPos[0].x - 1][digitalPos[0].y]); childNode.caculateCost(objectDigitalPos); childNodes.Add(childNode); }
//将零数码向右移动
if (digitalPos[0].y < 3 && this.mode != 3) {
_15DigitalNode childNode = new _15DigitalNode(this.matrix, this, this.level + 1, 4);
swap(ref childNode.matrix[digitalPos[0].x][digitalPos[0].y], ref childNode.matrix[digitalPos[0].x][digitalPos[0].y + 1]);
childNode.caculateCost(objectDigitalPos); childNodes.Add(childNode); }
//将零数码向左移动
if (digitalPos[0].y > 0 && this.mode != 4) {
_15DigitalNode childNode = new _15DigitalNode(this.matrix, this, this.level + 1, 3);
swap(ref childNode.matrix[digitalPos[0].x][digitalPos[0].y], ref childNode.matrix[digitalPos[0].x][digitalPos[0].y - 1]); childNode.caculateCost(objectDigitalPos); childNodes.Add(childNode); }
return childNodes; }
//交换0数码与其他数码的位置 private void swap(ref int a, ref int b) {
int c = a; a = b; b = c; }
// 构造函数，初始化一个状态节点
public _15DigitalNode(int[][] matr, _15DigitalNode parent, int l, int mod) {
//初始化矩阵
for (int i = 0; i < 4; i++) {
matrix[i] = new int[4]; for (int j = 0; j < 4; j++) {
matrix[i][j] = matr[i][j]; } }
//将要初始化节点的父节点 parentNode = parent;
//将要初始化节点的深度 level = l; mode = mod; } }
class _15Digital {
private _15DigitalNode initialNode; // 初始节点
private _15DigitalNode objectNode; // 目标节点
private ArrayList openList = new ArrayList(); // Open表 private ArrayList closedList = new ArrayList(); // Closed表 public _15Digital(int[][] initialMatrix, int[][] objectMatrix) {
initialNode = new _15DigitalNode(initialMatrix, null, 0, 0); objectNode = new _15DigitalNode(objectMatrix, null, 0, 0); //将初始状态节点放入open表中 openList.Add(initialNode); }
public bool searchObject() {
int step = 0;
digitalPosition[] objectDigitalPos = objectNode.findDigitalPosition(); while (openList.Count != 0) {
step++;
_15DigitalNode currentNode = (_15DigitalNode)openList[0]; closedList.Add(currentNode); openList.RemoveAt(0);
currentNode.caculateCost(objectDigitalPos); if (currentNode.Cost - currentNode.Level == 0) return true; else {
ArrayList temp = currentNode.extendChildNode(objectDigitalPos); openList.AddRange(temp); sortOpenList(); } }
return false; }
//重排OPEN表
private void sortOpenList() {
int min = 0;
for (int i = 1; i < openList.Count; i++) {
if (((_15DigitalNode)openList[min]).Cost > ((_15DigitalNode)openList[i]).Cost)
min = i; }
object temp = openList[min]; openList[min] = openList[0];
openList[0] = temp; }
//找到目标状态
public ArrayList findResult() {
ArrayList result = new ArrayList();
result.Add(closedList[closedList.Count - 1]);
while (((_15DigitalNode)result[result.Count - 1]).Level != 0) {
} } }
result.Add(((_15DigitalNode)result[result.Count - 1]).parentNode); }
result.Reverse(); return result;