seeker.java

八数码拼图程序源码,可以实现初始8个数码顺序到目标8个数码顺序的自动拼图

package com.will.eightnums;

import java.util.*;

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: </p>
 *
 * @author Will Wang
 * @version 1.0
 */
public class Seeker {
  private Node start, end;
  private Vector array_open = new Vector(); //用于存放搜索过程中尚未展开的节点
  private Vector array_closed = new Vector();//用于存储已经搜索过的节点
  private int depth, maxdepth;
  private int type;
  private Node newnode;

  public Seeker(Node start, Node end) {
    this.start = start;
    this.end = end;
  }

  public Seeker() {
  }

  public void setNodes(Node start, Node end) {
    this.start = start;
    this.end = end;
  }

  public void setMaxDepth(int depth) {
    this.maxdepth = depth;
  }

  public void setType(int type) {
    this.type = type;
  }

  public void seek() {
    array_open.clear();
    array_closed.clear();
    array_open.add(start);
    depth = 0;
    if (start.equals(end)) {
      return;
    }
    if (type == 1||type == 2)
      breadthSeek(); //广度优先搜索，如果type==2,则调用启发函数
    else
      depthSeek(start); //深度优先搜索，如果type==4 则调用启发函数
    return;
  }

  private void breadthSeek() { //非递归算法
    if (start.equals(end)) {
      return;
    }
    Node current = start;
    current.setf(end);
    for (; ; ) {
      if ( (current.y > 0) && (current.flag != 3)) { //可以左移
        Node newnode = new Node();
        newnode.leftCopy(current);
        if (newnode.equals(end)) {
          array_open.add(newnode);
          return;
        }
        if (!isExist(newnode)) {
          array_open.add(newnode);
        }
      }
      if ( (current.x > 0) && (current.flag != 4)) { //可以上移
        Node newnode = new Node();
        newnode.upCopy(current);
        if (newnode.equals(end)) {
          array_open.add(newnode);
          return;
        }
        if (!isExist(newnode)) {
          array_open.add(newnode);
        }
      }
      if ( (current.y < 2) && (current.flag != 1)) { //可以右移
        Node newnode = new Node();
        newnode.rightCopy(current);
        if (newnode.equals(end)) {
          array_open.add(newnode);
          return;
        }
        if (!isExist(newnode)) {
          array_open.add(newnode);
        }
      }
      if ( (current.x < 2) && (current.flag != 2)) { //可以下移
        Node newnode = new Node();
        newnode.downCopy(current);
        if (newnode.equals(end)) {
          array_open.add(newnode);
          return;
        }
        if (!isExist(newnode)) {
          array_open.add(newnode);
        }
      }
      //展开一个节点后，再展开该层下一个节点
      //首先将已经展开的节点写入array_closed中
      array_closed.add(current);
      array_open.remove(0);//肯定是第一个
      if(!array_open.isEmpty()){
        if(type==2){//启发式搜索，必须计算子节点的f值，然后重新排序
          sort_open(current);
        }
        current = (Node) array_open.get(0);
      }
      else
        return;
    }
  }

  public void depthSeek(Node s) { //非递归算法
    //按约定顺序搜索下级节点，插入队列，将队列最后一个节点作为当前节点向下搜索
    //当向下搜索没结果时，删除当前节点，再从最后一个节点开始。
    //如果一直退回到起始节点，则表示按当前设置无法完成任务。
    Node u, v;
    v = s;
    for (; ; ) {
      u = begin(v); //按约定顺序获得一个下级节点
      if (u == null) { //到达目标节点
        return;
      }
      if (1 == array_open.size()) {
        return;
      }
      v = u; //继续搜索
    }
  }

  Node begin(Node current) {
    Node temp[] = new Node[4]; //最多4个下级节点(其实只有起始点空格在中间时才是4个，其余最多3个)
    int sons = 0;
    int h1[] = new int[4];
    if ( (current.y > 0) && (current.flag != 3) && (depth < maxdepth)) { //可以左移
      newnode = new Node();
      newnode.leftCopy(current);
      if (newnode.equals(end)) {
        array_open.add(newnode);
        return null;
      }
      if (!isExist(newnode)) {
        temp[sons++] = newnode;
      }
    }
    if ( (current.x > 0) && (current.flag != 4) && (depth < maxdepth)) { //可以上移
      newnode = new Node();
      newnode.upCopy(current);
      if (newnode.equals(end)) {
        array_open.add(newnode);
        return null;
      }
      if (!isExist(newnode)) {
        temp[sons++] = newnode;
      }
    }
    if ( (current.y < 2) && (current.flag != 1) && (depth < maxdepth)) { //可以右移
      newnode = new Node();
      newnode.rightCopy(current);
      if (newnode.equals(end)) {
        array_open.add(newnode);
        return null;
      }
      if (!isExist(newnode)) {
        temp[sons++] = newnode;
      }
    }
    if ( (current.x < 2) && (current.flag != 2) && (depth < maxdepth)) { //可以下移
      newnode = new Node();
      newnode.downCopy(current);
      if (newnode.equals(end)) {
        array_open.add(newnode);
        return null;
      }
      if (!isExist(newnode)) {
        temp[sons++] = newnode;
      }
    }
    ///////////////////////////////
    if (sons > 0) { //下级节点超过1个而且系统设置为“采用启发函数“
      if (type == 4) {
        int i = 0;
        while (i < sons) {
          h1[i] = temp[i++].h1(end);
        }
        sort(h1, temp, sons);
      }
      int i = 0;
      while (i < sons) {
        array_open.addElement(temp[i++]);
      }
    }
    if (sons == 0) { //无下级节点则返回另一个同级节点
      while (current != start) {
        if ( ( (Node) array_open.get(array_open.size() - 2)) == current.pre) {
          current = (Node) array_open.get(array_open.size() - 2);
          array_open.removeElementAt(array_open.size() - 1);
          depth--;
        }
        else {
          array_open.removeElementAt(array_open.size() - 1);
          break;
        }
      }
    }
    else {
      depth++;
    }
    return (Node) array_open.get(array_open.size() - 1);
  }

  private boolean isExist(Node next) {
    //只需判断节点是否与其祖先节点相同，而不去与所有节点比较判断，这样可以加快速度
    Node temp=next.pre;
    while(temp!=null) {
        if(temp.equals(next))
          return true;
        else
          temp=temp.pre;
      }
    return false;
  }

  public Vector getOptim() {
    Vector vector = new Vector();
    int length = this.array_open.size();
    Node node = (Node)this.array_open.get(length - 1);
    while (node.pre != null) {
      vector.add(0, node);
      node = node.pre;
    }
    return vector;
  }

  private void sort(int h1[], Node temp[], int sons) {
    Node sort;
    for (int i = 1; i < sons; i++) {
      for (int j = i; (j > 0) && (h1[j] > h1[j - 1]); j--) {
        sort = temp[j - 1];
        temp[j - 1] = temp[j];
        temp[j] = sort;
      }
    }
  }

  private void sort_open(Node current) {//对未展开的节点排序
  //array_open最后的几个节点是current节点的子节点。
  //只需对这几个节点计算f值，然后再重新排序
  int len=array_open.size();
  int sons=0;//用于判断子节点数量
  int i,j;
  Node son[]=new Node[4];
  Node temp;
  while(sons<len && sons<4){
    if(((Node)(array_open.get(len-sons-1))).pre.equals(current)){
      son[sons]=(Node)(array_open.get(len-sons-1));
      son[sons].setf(end);
      sons++;
    }else
      break;
  }
  for(i=0;i<sons;i++){
    j=0;
    while(j<len-sons){
      if(son[i].getf()<((Node)(array_open.get(j))).getf()){
        //将该子节点从后面插到前面
        array_open.remove(len-sons+i);
        array_open.add(j,son[i]);
        break;//break while
      }
      j++;
    }
  }
  }
}