import java.util.*;
public class Tsp {
private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"};
//private String cityEnd[]=new String[34];
private int cityNum=cityName.length; //城市个数
private int popSize = 50; //种群数量
private int maxgens = 20000; //迭代次数
private double pxover = 0.8; //交叉概率
private double pmultation = 0.05; //变异概率
private long[][] distance = new long[cityNum][cityNum];
private int range = 2000; //用于判断何时停止的数组区间
private class genotype {
int city[] = new int[cityNum]; //单个基因的城市序列
long fitness; //该基因的适应度
double selectP; //选择概率
double exceptp; //期望概率
int isSelected; //是否被选择
}
private genotype[] citys = new genotype[popSize];
/**
* 构造函数，初始化种群
*/
public Tsp() {
for (int i = 0; i < popSize; i++) {
citys[i] = new genotype();
int[] num = new int[cityNum];
for (int j = 0; j < cityNum; j++)
num[j] = j;
int temp = cityNum;
for (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
citys[i].city[j] = num[r];
num[r] = num[temp - 1];
temp--;
}
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
initDistance();
}
/**
* 计算每个种群每个基因个体的适应度，选择概率，期望概率，和是否被选择。
*/
public void CalAll(){
for( int i = 0; i< popSize; i++){
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
CalFitness();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* 填充，将多选的填充到未选的个体当中
*/
public void pad(){
int best = 0;
int bad = 0;
while(true){
while(citys[best].isSelected <= 1 && best<popSize-1)
best ++;
while(citys[bad].isSelected != 0 && bad<popSize-1)
bad ++;
for(int i = 0; i< cityNum; i++)
citys[bad].city[i] = citys[best].city[i];
citys[best].isSelected --;
citys[bad].isSelected ++;
bad ++;
if(best == popSize ||bad == popSize)
break;
}
}
/**
* 交叉主体函数
*/
public void crossover() {
int x;
int y;
int pop = (int)(popSize* pxover /2);
while(pop>0){
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
executeCrossover(x,y);//x y 两个体执行交叉
pop--;
}
}
/**
* 执行交叉函数
* @param 个体x
* @param 个体y
* 对个体x和个体y执行佳点集的交叉，从而产生下一代城市序列
*/
private void executeCrossover(int x,int y){
int dimension = 0;
for( int i = 0 ;i < cityNum; i++)
if(citys[x].city[i] != citys[y].city[i]){
dimension ++;
}
int diffItem = 0;
double[] diff = new double[dimension];
for( int i = 0 ;i < cityNum; i++){
if(citys[x].city[i] != citys[y].city[i]){
diff[diffItem] = citys[x].city[i];
citys[x].city[i] = -1;
citys[y].city[i] = -1;
diffItem ++;
}
}
Arrays.sort(diff);
double[] temp = new double[dimension];
temp = gp(x, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
int tempDimension = dimension;
int tempi = 0;
while(tempDimension> 0 ){
if(citys[x].city[tempi] == -1){
citys[x].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
Arrays.sort(diff);
temp = gp(y, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
tempDimension = dimension;
tempi = 0;
while(tempDimension> 0 ){
if(citys[y].city[tempi] == -1){
citys[y].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
}
/**
* @param individual 个体
* @param dimension 维数
* @return 佳点集 (用于交叉函数的交叉点） 在executeCrossover()函数中使用
*/
private double[] gp(int individual, int dimension){
double[] temp = new double[dimension];
double[] temp1 = new double[dimension];
int p = 2 * dimension + 3;
while(!isSushu(p))
p++;
for( int i = 0; i< dimension; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (individual+1);
temp[i] = temp[i] - (int)temp[i];
if( temp [i]< 0)
temp[i] = 1+temp[i];
}
for( int i = 0; i< dimension; i++)
temp1[i] = temp[i];
Arrays.sort(temp1);
//排序
for( int i = 0; i< dimension; i++)
for( int j = 0; j< dimension; j++)
if(temp[j]==temp1[i])
temp[j] = i;
return temp;
}
/**
* 变异
*/
public void mutate(){
double random;
int temp;
int temp1;
int temp2;
for( int i = 0 ; i< popSize; i++){
random = Math.random();
if(random<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = citys[i].city[temp1];
citys[i].city[temp1] = citys[i].city[temp2];
citys[i].city[temp2] = temp;
}
}
}
/**
* 打印当前代数的所有城市序列，以及其相关的参数
*/
public void print(){}
/**
* 初始化各城市之间的距离
*/
private void initDistance(){
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++){
distance[i][j] = Math.abs(i-j);
}
}
}
/**
* 计算所有城市序列的适应度
*/
private void CalFitness() {
for (int i = 0; i < popSize; i++) {
for (int j = 0; j < cityNum - 1; j++)
citys[i].fitness += distance[citys[i].city[j]][citys[i].city[j + 1]];
citys[i].fitness += distance[citys[i].city[0]][citys[i].city[cityNum - 1]];
}
}
/**
* 计算选择概率
*/
private void CalSelectP(){
long sum = 0;
for( int i = 0; i< popSize; i++)
sum += citys[i].fitness;
for( int i = 0; i< popSize; i++)
citys[i].selectP = (double)citys[i].fitness/sum;
}
/**
* 计算期望概率
*/
private void CalExceptP(){
for( int i = 0; i< popSize; i++)
citys[i].exceptp = (double)citys[i].selectP * popSize;
}
/**
* 计算该城市序列是否较优，较优则被选择，进入下一代
*/
private void CalIsSelected(){
int needSelecte = popSize;
for( int i = 0; i< popSize; i++)
if( citys[i].exceptp<1){
citys[i].isSelected++;
needSelecte --;
}
double[] temp = new double[popSize];
for (int i = 0; i < popSize; i++) {
// temp[i] = citys[i].exceptp - (int) citys[i].exceptp;
// temp[i] *= 10;
temp[i] = citys[i].exceptp*10;
}
int j = 0;
while (needSelecte != 0) {
for (int i = 0; i < popSize; i++) {
if ((int) temp[i] == j) {
citys[i].isSelected++;
needSelecte--;
if (needSelecte == 0)
break;
}
}
j++;
}
}
/**
* @param x
* @return 判断一个数是否是素数的函数
*/
private boolean isSushu( int x){
if(x<2) return false;
for(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) return false;
return true;
}
/**
* @param x 数组
* @return x数组的值是否全部相等，相等则表示x.length代的最优结果相同，则算法结束
*/
private boolean isSame(long[] x){
for( int i = 0; i< x.length -1; i++)
if(x[i] !=x[i+1])
return false;
return true;
}
/**
* 打印任意代最优的路径序列
*/
private void printBestRoute(){
CalAll();
long temp = citys[0].fitness;
int index = 0;
for (int i = 1; i < popSize; i++) {
if(citys[i].fitness<temp){
temp = citys[i].fitness;
index = i;
}
}
System.out.println();
System.out.println("最佳路径的序列：");
for (int j = 0; j < cityNum; j++)
{
String cityEnd[]={cityName[citys[index].city[j]]};
for(int m=0;m<cityEnd.length;m++)
{
System.out.print(cityEnd[m] + " ");
}
}
//System.out.print(citys[index].city[j] + cityName[citys[index].city[j]] + " ");
//System.out.print(cityName[citys[index].city[j]]);
System.out.println();
}
/**
* 算法执行
*/
public void run(){
long[] result = new long[range];
//result初始化为所有的数字都不相等
for( int i = 0; i< range; i++)
result[i] = i;
int index = 0; //数组中的位置
int num = 1; //第num代
while(maxgens>0){
System.out.println("----------------- 第 "+num+" 代 -------------------------");
CalAll();
print();
pad();
crossover();
mutate();
maxgens --;
long temp = citys[0].fitness;
for ( int i = 1; i< popSize; i++)
if(citys[i].fitness<temp){
temp = citys[i].fitness;
}
System.out.println("最优的解："+temp);
result[index] = temp;
if(isSame(result))
break;
index++;
if(index==range)
index = 0;
num++;
}
printBestRoute();
}
/**
* @param a 开始时间
* @param b 结束时间
*/
public void CalTime(Calendar a,Calendar b){
long x = b.getTimeInMillis() - a.getTimeInMillis();
long y = x/1000;
x = x - 1000*y;
System.out.println("算法执行时间："+y+"."+x+" 秒");
}
/**
* 程序入口
*/
public static void main(String[] args) {
Calendar a = Calendar.getInstance(); //开始时间
Tsp tsp = new Tsp();
tsp.run();
Calendar b = Calendar.getInstance(); //结束时间
tsp.CalTime(a, b);
}
}
/**
* 人民币转成大写
*
* @param value
* @return String
*/
public static String hangeToBig(double value)
{
char[] hunit = { '拾', '佰', '仟' }; // 段内位置表示
char[] vunit = { '万', '亿' }; // 段名表示
char[] digit = { '零', '壹', '贰', '叁', '肆', '伍', '陆', '柒', '捌', '玖' }; // 数字表示
long midVal = (long) (value * 100); // 转化成整形
String valStr = String.valueOf(midVal); // 转化成字符串
String head = valStr.substring(0, valStr.length() - 2); // 取整数部分
String rail = valStr.substring(valStr.length() - 2); // 取小数部分
String prefix = ""; // 整数部分转化的结果
String suffix = ""; // 小数部分转化的结果
// 处理小数点后面的数
if (rail.equals("00"))
{ // 如果小数部分为0
suffix = "整";
}
else
{
suffix = digit[rail.charAt(0) - '0'] + "角" + digit[rail.charAt(1) - '0'] + "分"; // 否则把角分转化出来
}
// 处理小数点前面的数
char[] chDig = head.toCharArray(); // 把整数部分转化成字符数组
char zero = '0'; // 标志'0'表示出现过0
byte zeroSerNum = 0; // 连续出现0的次数
for (int i = 0; i < chDig.length; i++)
{ // 循环处理每个数字
int idx = (chDig.length - i - 1) % 4; // 取段内位置
int vidx = (chDig.length - i - 1) / 4; // 取段位置
if (chDig[i] == '0')
{ // 如果当前字符是0
zeroSerNum++; // 连续0次数递增
if (zero == '0')
{ // 标志
zero = digit[0];
}
else if (idx == 0 && vidx > 0 && zeroSerNum < 4)
{
prefix += vunit[vidx - 1];
zero = '0';
}
continue;
}
zeroSerNum = 0; // 连续0次数清零
if (zero != '0')
{ // 如果标志不为0,则加上,例如万,亿什么的
prefix += zero;
zero = '0';
}
prefix += digit[chDig[i] - '0']; // 转化该数字表示
if (idx > 0)
prefix += hunit[idx - 1];
if (idx == 0 && vidx > 0)
{
prefix += vunit[vidx - 1]; // 段结束位置应该加上段名如万,亿
}
}
if (prefix.length() > 0)
prefix += '圆'; // 如果整数部分存在,则有圆的字样
return prefix + suffix; // 返回正确表示
}
//哈弗曼编码的实现类
public class HffmanCoding {
private int charsAndWeight[][];// [][0]是 字符，[][1]存放的是字符的权值（次数）
private int hfmcoding[][];// 存放哈弗曼树
private int i = 0;// 循环变量
private String hcs[];
public HffmanCoding(int[][] chars) {
// TODO 构造方法
charsAndWeight = new int[chars.length][2];
charsAndWeight = chars;
hfmcoding = new int[2 * chars.length - 1][4];// 为哈弗曼树分配空间
}
// 哈弗曼树的实现
public void coding() {
int n = charsAndWeight.length;
if (n == 0)
return;
int m = 2 * n - 1;
// 初始化哈弗曼树
for (i = 0; i < n; i++) {
hfmcoding[i][0] = charsAndWeight[i][1];// 初始化哈弗曼树的权值
hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点
hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子
hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子
}
for (i = n; i < m; i++) {
hfmcoding[i][0] = 0;// 初始化哈弗曼树的权值
hfmcoding[i][1] = 0;// 初始化哈弗曼树的根节点
hfmcoding[i][2] = 0;// 初始化哈弗曼树的左孩子
hfmcoding[i][3] = 0;// 初始化哈弗曼树的右孩子
}
// 构建哈弗曼树
for (i = n; i < m; i++) {
int s1[] = select(i);// 在哈弗曼树中查找双亲为零的 weight最小的节点
hfmcoding[s1[0]][1] = i;// 为哈弗曼树最小值付双亲
hfmcoding[s1[1]][1] = i;
hfmcoding[i][2] = s1[0];// 新节点的左孩子
hfmcoding[i][3] = s1[1];// 新节点的右孩子
hfmcoding[i][0] = hfmcoding[s1[0]][0] + hfmcoding[s1[1]][0];// 新节点的权值是左右孩子的权值之和
}
}
// 查找双亲为零的 weight最小的节点
private int[] select(int w) {
// TODO Auto-generated method stub
int s[] = { -1, -1 }, j = 0;// s1 最小权值且双亲为零的节点的序号 ， i 是循环变量
int min1 = 32767, min2 = 32767;
for (j = 0; j < w; j++) {
if (hfmcoding[j][1] == 0) {// 只在尚未构造二叉树的结点中查找（双亲为零的节点）
if (hfmcoding[j][0] < min1) {
min2 = min1;
s[1] = s[0];
min1 = hfmcoding[j][0];
s[0] = j;
} else if (hfmcoding[j][0] < min2) {
min2 = hfmcoding[j][0];
s[1] = j;
}
}
}
return s;
}
public String[] CreateHCode() {// 根据哈夫曼树求哈夫曼编码
int n = charsAndWeight.length;
int i, f, c;
String hcodeString = "";
hcs = new String[n];
for (i = 0; i < n; i++) {// 根据哈夫曼树求哈夫曼编码
c = i;
hcodeString = "";
f = hfmcoding[i][1]; // f 哈弗曼树的根节点
while (f != 0) {// 循序直到树根结点
if (hfmcoding[f][2] == c) {// 处理左孩子结点
hcodeString += "0";
} else {
hcodeString += "1";
}
c = f;
f = hfmcoding[f][1];
}
hcs[i] = new String(new StringBuffer(hcodeString).reverse());
}
return hcs;
}
public String show(String s) {// 对字符串显示编码
String textString = "";
char c[];
int k = -1;
c = new char[s.length()];
c = s.toCharArray();// 将字符串转化为字符数组
for (int i = 0; i < c.length; i++) {
k = c[i];
for (int j = 0; j < charsAndWeight.length; j++)
if (k == charsAndWeight[j][0])
textString += hcs[j];
}
return textString;
}
// 哈弗曼编码反编译
public String reCoding(String s) {
String text = "";// 存放反编译后的字符
int k = 0, m = hfmcoding.length - 1;// 从根节点开始查询
char c[];
c = new char[s.length()];
c = s.toCharArray();
k = m;
for (int i = 0; i < c.length; i++) {
if (c[i] == '0') {
k = hfmcoding[k][2];// k的值为根节点左孩子的序号
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判断是不是叶子节点，条件（左右孩子都为零）
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
if (c[i] == '1') {
k = hfmcoding[k][3];// k的值为根节点右孩子的序号
if (hfmcoding[k][2] == 0 && hfmcoding[k][3] == 0)// 判断是不是叶子节点，条件（左右孩子都为零）
{
text += (char) charsAndWeight[k][0];
k = m;
}
}
}
return text;
}
}
java各种数据库连接
Java code
MySQL：
String Driver="com.mysql.jdbc.Driver"; //驱动程序
String URL="jdbc:mysql://localhost:3306/db_name"; //连接的URL,db_name为数据库名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).new Instance();
Connection con=DriverManager.getConnection(URL,Username,Password);
Microsoft SQL Server 2.0驱动(3个jar的那个):
String Driver="com.microsoft.jdbc.sqlserver.SQLServerDriver"; //连接SQL数据库的方法
String URL="jdbc:microsoft:sqlserver://localhost:1433;DatabaseName=db_name"; //db_name为数据库名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).new Instance(); //加载数据可驱动
Connection con=DriverManager.getConnection(URL,UserName,Password); //
Microsoft SQL Server 3.0驱动(1个jar的那个): // 老紫竹完善
String Driver="com.microsoft.sqlserver.jdbc.SQLServerDriver"; //连接SQL数据库的方法
String URL="jdbc:microsoft:sqlserver://localhost:1433;DatabaseName=db_name"; //db_name为数据库名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).new Instance(); //加载数据可驱动
Connection con=DriverManager.getConnection(URL,UserName,Password); //
Sysbase:
String Driver="com.sybase.jdbc.SybDriver"; //驱动程序
String URL="jdbc:Sysbase://localhost:5007/db_name"; //db_name为数据可名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance();
Connection con=DriverManager.getConnection(URL,Username,Password);
Oracle(用thin模式):
String Driver="oracle.jdbc.driver.OracleDriver"; //连接数据库的方法
String URL="jdbc:oracle:thin:@loaclhost:1521:orcl"; //orcl为数据库的SID
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance(); //加载数据库驱动
Connection con=DriverManager.getConnection(URL,Username,Password);
PostgreSQL:
String Driver="org.postgresql.Driver"; //连接数据库的方法
String URL="jdbc:postgresql://localhost/db_name"; //db_name为数据可名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance();
Connection con=DriverManager.getConnection(URL,Username,Password);
DB2：
String Driver="com.ibm.db2.jdbc.app.DB2.Driver"; //连接具有DB2客户端的Provider实例
//String Driver="com.ibm.db2.jdbc.net.DB2.Driver"; //连接不具有DB2客户端的Provider实例
String URL="jdbc:db2://localhost:5000/db_name"; //db_name为数据可名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance();
Connection con=DriverManager.getConnection(URL,Username,Password);
Informix:
String Driver="com.informix.jdbc.IfxDriver";
String URL="jdbc:Informix-sqli://localhost:1533/db_name:INFORMIXSER=myserver"; //db_name为数据可名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance();
Connection con=DriverManager.getConnection(URL,Username,Password);
JDBC-ODBC:
String Driver="sun.jdbc.odbc.JdbcOdbcDriver";
String URL="jdbc:odbc:dbsource"; //dbsource为数据源名
String Username="username"; //用户名
String Password="password"; //密码
Class.forName(Driver).newInstance();
Connection con=DriverManager.getConnection(URL,Username,Password);
点到线段的最短距离
private double pointToLine(int x1, int y1, int x2, int y2, int x0,
int y0) {
double space = 0;
double a, b, c;
a = lineSpace(x1, y1, x2, y2);// 线段的长度
b = lineSpace(x1, y1, x0, y0);// (x1,y1)到点的距离
c = lineSpace(x2, y2, x0, y0);// (x2,y2)到点的距离
if (c <= 0.000001 || b <= 0.000001) {
space = 0;
return space;
}
if (a <= 0.000001) {
space = b;
return space;
}
if (c * c >= a * a + b * b) {
space = b;
return space;
}
if (b * b >= a * a + c * c) {
space = c;
return space;
}
double p = (a + b + c) / 2;// 半周长
double s = Math.sqrt(p * (p - a) * (p - b) * (p - c));// 海伦公式求面积
space = 2 * s / a;// 返回点到线的距离（利用三角形面积公式求高）
return space;
}
// 计算两点之间的距离
private double lineSpace(int x1, int y1, int x2, int y2) {
double lineLength = 0;
lineLength = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2)
* (y1 - y2));
return lineLength;
}