package com.cj;
import java.io.FileWriter;
import java.io.IOException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
class ba_num implements Comparable {
ba_num parent;
int gCost;
int hCost;
int[] nums = new int[9];
static int[] tt = new int[]{1,10,100,1000,10000,100000,1000000,10000000,1000000000};
public ba_num(int[] src)
{
for(int i = 0; i<9;i++)
{
nums[i] = src[i];
}
}
public int getFCost() {
return gCost + hCost;
}
public int hashCode()
{
int sum = 0;
for(int i = 0; i<9;i++)
{
sum+=nums[i]*tt[i];
}
return sum;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof ba_num) {
ba_num n = (ba_num) obj;
for(int i =0 ;i<9;i++)
{
if(this.nums[i] !=n.nums[i])
return false;
}
return true;
} else {
return false;
}
}
public int getHCost(ba_num node) {
int num = 0;
for(int i =0;i<9;i++)
{
for(int j=0;j<9;j++)//(this.nums[i]!=node.nums[i])
{
if(nums[i]==node.nums[j])
{
num += (Math.abs((i-j)%3)+Math.abs((i-j)/3));
}
}
}
return num;
}
public ArrayList<ba_num> getNeighbors()
{
ArrayList<ba_num> result = new ArrayList<ba_num>();
int index = 0;
for(int i =0;i<9;i++)
{
if(nums[i]==0)
{
index=i;
break;
}
}
if(index==0||index==1||index==3
||index==4||index==6||index==7)
{
result.add(swap(this,index,index+1));
}
if(index==1||index==2||index==4
||index==5||index==7||index==8)
{
result.add(swap(this,index,index-1));
}
if(index==0||index==1||index==2
||index==3||index==4||index==5)
{
result.add(swap(this,index,index+3));
}
if(index==6||index==7||index==8
||index==3||index==4||index==5)
{
result.add(swap(this,index,index-3));
}
return result;
}
public ba_num swap(ba_num old,int i ,int j)
{
int[] new_nums = swap(old.nums,i,j);
return new ba_num(new_nums);
}
private int[] swap(int[] nums,int i , int j)
{
int[] new_nums = new int[nums.length];
for(int k = 0;k<nums.length;k++)
{
new_nums[k] = nums[k];
}
new_nums[j] = nums[i];
new_nums[i] = nums[j];
return new_nums;
}
@Override
public int compareTo(Object other) {
int thisValue = this.getFCost();
int otherValue = ((ba_num) other).getFCost();
int v = thisValue - otherValue;
return (v > 0) ? 1 : (v < 0) ? -1 : 0;
}
}
public class aa {
public static class PriorityList<ba_num> extends LinkedList {
public void add(Comparable object) {
for (int i = 0; i < size(); i++) {
if (object.compareTo(get(i)) <= 0) {
add(i, object);
return;
}
}
addLast(object);
}
}
public static int[] getNums()
{
Random r = new Random();
ArrayList<Integer> result = new ArrayList<Integer>();
for(int n=0,num=r.nextInt(9);n<9;n++)
{
while(result.contains(num))
num = r.nextInt(9);
result.add(num);
}
int[] r1 = new int[result.size()];
for(int i = 0 ;i<result.size();i++)
{
r1[i] = result.get(i);
}
return r1;
}
public static boolean isAcheive(int[] a,int[] b)
{
int num1=0,num2=0;
for(int i = 0 ;i<8;i++)
{
for(int j =i+1;j<9;j++)
{
if(a[i]>a[j])
num1++;
if(b[i]>b[j])
num2++;
}
}
return (num1-num2)%2==0;
}
static FileWriter fw;
static{
try {
fw = new FileWriter("c:/aa.text");
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
static void print(int[] a) throws IOException
{
fw.write("===================================\r\n");
fw.write("*\t"+a[0]+"\t"+a[1]+"\t"+a[2]+"\t*\r\n");
fw.write("*\t"+a[3]+"\t"+a[4]+"\t"+a[5]+"\t*\r\n");
fw.write("*\t"+a[6]+"\t"+a[7]+"\t"+a[8]+"\t*\r\n");
fw.write("===================================\r\n");
fw.flush();
}
static void printP(ba_num a) throws IOException
{
print(a.nums);
while((a=a.parent)!=null)
{
fw.write(" ↓ \r\n");
print(a.nums);
}
fw.close();
}
public static void main(String[] args) throws IOException
{
PriorityList openList = new PriorityList();
ArrayList<ba_num> all = new ArrayList<ba_num>();
LinkedList<ba_num> closedList = new LinkedList<ba_num>();
int[] src = getNums();
int[] dest = getNums();
while(!isAcheive(src,dest))
{
print(src);
print(dest);
fw.write("以上八星不能达到。false\r\n");
fw.write("\r\n");
src = getNums();
}
//src =new int[]{1,2,3,4,5,6,7,8,0};
//dest = new int[]{1,2,3,0,4,6,7,5,8};
print(src);
print(dest);
fw.write("下面开始转换步骤:\r\n\r\n");
ba_num src_ba = new ba_num(src);
all.add(src_ba);
ba_num dest_ba = new ba_num(dest);
src_ba.gCost=0;
src_ba.hCost = src_ba.getHCost(dest_ba);
openList.add(src_ba);
all.add(dest_ba);
all.add(src_ba);
while (!openList.isEmpty()) {
ba_num node = (ba_num) openList.removeFirst();
if(node.equals(dest_ba))
{
printP(node);
return;
}
List neighbors = node.getNeighbors();
for (int i = 0; i < neighbors.size(); i++) {
ba_num neighborNode = (ba_num)neighbors.get(i);
if(all.contains(neighborNode))
{
neighborNode = all.get(all.indexOf(neighborNode));
}else{
all.add(neighborNode);
if(all.size()%100==0)
{
System.out.println(all.size());
System.out.println(new SimpleDateFormat("yyyy-MM-dd hh:mm:ss").format(new Date()));
}
}
boolean isOpen = openList.contains(neighborNode);
boolean isClosed = closedList.contains(neighborNode);
int costFromStart = node.gCost+ 1;
if((!isOpen&&!isClosed)
||costFromStart<neighborNode.gCost)
{
if (isClosed) {
closedList.remove(neighborNode);
}
neighborNode.parent = node;
neighborNode.gCost = costFromStart;
neighborNode.hCost = neighborNode.getHCost(dest_ba);
if (!isOpen) {
openList.add(neighborNode);
}
}
}
closedList.add(node);
}
}
}
分享到:
相关推荐
java.lang.management 提供管理接口,用于监视和管理 Java 虚拟机以及 Java 虚拟机在其上运行的操作系统。 java.lang.ref 提供了引用对象类,支持在某种程度上与垃圾回收器之间的交互。 java.lang.reflect 提供类...
Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行ATM...
这是一本以面试题为入口讲解 Java 核心内容的技术书籍,书中内容极力的向你证实代码是对数学逻辑的具体实现。当你仔细阅读书籍时,会发现Java中有大量的数学知识,包括:扰动函数、负载因子、拉链寻址、开放寻址、...
Java OCR(Optical Character Recognition,光学字符识别)技术是一种计算机视觉领域的应用,它能将图像中的文字转换成可编辑的文本格式。这项技术在各种场景下都有广泛应用,比如文档扫描、车牌识别、发票处理等。...
Java API文档是Java开发者的重要参考资料,它包含了Java开发工具包(JDK)中的所有类、接口、方法和常量的详细说明。这份中文网页版的Java API文档为中国的开发者提供了便利,无需通过英文版本来学习和查找API信息,...
Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行...
Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行...
java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java...
JAVA开发人员最新版本7.0 api文档!本文档是 Java Platform Standard Edition 7 的 API !Java 1.7 API的中文帮助文档。 深圳电信培训中心 徐海蛟博士教学用api 7.0中文文档。支持全文检索,在线即时查询。 里面列...
java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏...
java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
Java2Pas是一个实用工具,主要用于将Java编程语言编写的源代码转换为Pascal语言的等效代码。这个工具对于那些需要在两种语言之间迁移代码或者理解不同编程语言语法的开发者来说非常有价值。Java和Pascal虽然都是面向...
HelloWorldApp.java 第一个用Java开发的应用程序。 firstApplet.java 第一个用Java开发的Applet小程序。 firstApplet.htm 用来装载Applet的网页文件 第2章 示例描述:本章介绍开发Java的基础语法知识。 ...
### Java 错误处理:java.lang.OutOfMemoryError: Java heap space 在Java应用程序开发过程中,经常遇到的一个问题就是内存溢出错误,特别是在处理大量数据或长时间运行的应用时。其中,“java.lang....
Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 ...
Java是一种广泛使用的面向对象的编程语言,其设计目标是具有高度的可移植性,灵活性和安全性。本学习笔记主要涵盖了Java的基础知识,包括面向对象、集合、IO流、多线程、反射与动态代理以及Java 8的新特性等方面,...