Qi

设计模式-单例模式

发表于 2022-12-27 分类于 pattern

线程安全问题

volatile：保证多线程下的可见性

读volatile：每当子线程读取volatile变量时，都会从主线程重新拷贝一份
写volatile: 每当子线程修改volatile变量时，都会在修改后同步到主线程去

synchronized：对象锁、类锁、方法锁（其它篇有介绍）

public class Singleton {

private static volatile Singleton instance;

private Singleton(){
}

public static Singleton getInstance(){
    if(instance == null){
        synchronized(Singleton.class){
            if(instance == null){
                instance = new Singleton();
            }
        }
    }
    return instance;
}

}

遗传算法

发表于 2022-12-27 分类于 algrithom

遗传算法（Genetic Algorithms ）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。

步骤

初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）
个体评价计算P（t）中各个个体的适应度；
选择运算将选择算子作用于群体；
交叉运算将交叉算子作用于群体；
变异运算将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;
终止条件判断 t≦T：t← t+1 转到步骤2；t>T：终止输出解。

模型构成

决策变量及各种约束条件，即个体的表现型X和问题的解空间
目标函数最大OR 最小，数学描述形式量化方法
染色体编码方法（二进制、整数、浮点数）
解码方法
个体适应度的量化评价方法 F(x) （旅行商问题及最短路径）
设计遗传算子
有关运行参数

缺点

局部收敛
全局搜索能力不够强

改进

交叉算子
变异算子
选择策略

代码实现

package noah;  
  
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;  
public class GA {  
private int scale;// 种群规模  
private int cityNum; // 城市数量，染色体长度  
private int MAX_GEN; // 运行代数  
private int[][] distance; // 距离矩阵  
private int bestT;// 最佳出现代数  
private int bestLength; // 最佳长度  
private int[] bestTour; // 最佳路径  

// 初始种群，父代种群，行数表示种群规模，一行代表一个个体，即染色体，列表示染色体基因片段
private int[][] oldPopulation;
private int[][] newPopulation;// 新的种群，子代种群
private int[] fitness;// 种群适应度，表示种群中各个个体的适应度  
private float[] Pi;// 种群中各个个体的累计概率
private float Pc;// 交叉概率
private float Pm;// 变异概率
private int t;// 当前代数  
private Random random;  
public GA() {  
}  
/** 

constructor of GA 

@param s 
       种群规模 


@param n 
       城市数量 


@param g 
       运行代数 


@param c 
       交叉率 


@param m 
       变异率 




 **/
public GA(int s, int n, int g, float c, float m) {
    scale = s;
    cityNum = n;
    MAX_GEN = g;
    Pc = c;
    Pm = m;
}  
// 给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默
@SuppressWarnings(“resource”)
/** 

初始化GA算法类 

@param filename 数据文件名，该文件存储所有城市节点坐标数据 

@throws IOException
 */
private void init(String filename) throws IOException {
 // 读取数据
 int[] x;
 int[] y;
 String strbuff;
 BufferedReader data = new BufferedReader(new InputStreamReader(
     new FileInputStream(filename)));
 distance = new int[cityNum][cityNum];
 x = new int[cityNum];
 y = new int[cityNum];
 for (int i = 0; i &lt; cityNum; i++) {
 // 读取一行数据，数据格式1 6734 1453
 strbuff = data.readLine();
 // 字符分割
 String[] strcol = strbuff.split(“ “);
 x[i] = Integer.valueOf(strcol[1]);// x坐标
 y[i] = Integer.valueOf(strcol[2]);// y坐标
 }
 // 计算距离矩阵
 // ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
 for (int i = 0; i &lt; cityNum - 1; i++) {
 distance[i][i] = 0; // 对角线为0
 for (int j = i + 1; j &lt; cityNum; j++) {
     double rij = Math
             .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
                     * (y[i] - y[j])) / 10.0);
     // 四舍五入，取整
     int tij = (int) Math.round(rij);
     if (tij &lt; rij) {
         distance[i][j] = tij + 1;
         distance[j][i] = distance[i][j];
     } else {
         distance[i][j] = tij;
         distance[j][i] = distance[i][j];
     }
 }
 }
 distance[cityNum - 1][cityNum - 1] = 0;  
 bestLength = Integer.MAX_VALUE;
 bestTour = new int[cityNum + 1];
 bestT = 0;
 t = 0;  
 newPopulation = new int[scale][cityNum];
 oldPopulation = new int[scale][cityNum];
 fitness = new int[scale];
 Pi = new float[scale];  
 random = new Random(System.currentTimeMillis());
 /* 

for(int i=0;i&lt;cityNum;i++) { for(int j=0;j&lt;cityNum;j++) { 
System.out.print(distance[i][j]+”,”); } System.out.println(); }
  */
 // 初始化种群



}  
// 初始化种群
void initGroup() {
    int i, j, k;
    // Random random = new Random(System.currentTimeMillis());
    for (k = 0; k &lt; scale; k++)// 种群数
    {
        oldPopulation[k][0] = random.nextInt(65535) % cityNum;
        for (i = 1; i &lt; cityNum;)// 染色体长度
        {
            oldPopulation[k][i] = random.nextInt(65535) % cityNum;
            for (j = 0; j &lt; i; j++) {
                if (oldPopulation[k][i] == oldPopulation[k][j]) {
                    break;
                }
            }
            if (j == i) {
                i++;
            }
        }
    }  
/* 
 * for(i=0;i&amp;lt;scale;i++) { for(j=0;j&amp;lt;cityNum;j++) { 
 * System.out.print(oldPopulation[i][j]+","); } System.out.println(); } 
 */  

}  
public int evaluate(int[] chromosome) {
    // 0123
    int len = 0;
    // 染色体，起始城市,城市1,城市2…城市n
    for (int i = 1; i &lt; cityNum; i++) {
        len += distance[chromosome[i - 1]][chromosome[i]];
    }
    // 城市n,起始城市
    len += distance[chromosome[cityNum - 1]][chromosome[0]];
    return len;
}  
// 计算种群中各个个体的累积概率，前提是已经计算出各个个体的适应度fitness[max]，作为赌轮选择策略一部分，Pi[max]
void countRate() {
    int k;
    double sumFitness = 0;// 适应度总和  
double[] tempf = new double[scale];  

for (k = 0; k &amp;lt; scale; k++) {  
    tempf[k] = 10.0 / fitness[k];  
    sumFitness += tempf[k];  
}  

Pi[0] = (float) (tempf[0] / sumFitness);  
for (k = 1; k &amp;lt; scale; k++) {  
    Pi[k] = (float) (tempf[k] / sumFitness + Pi[k - 1]);  
}  

/* 
 * for(k=0;k&amp;lt;scale;k++) { System.out.println(fitness[k]+" "+Pi[k]); } 
 */  

}  
// 挑选某代种群中适应度最高的个体，直接复制到子代中
// 前提是已经计算出各个个体的适应度Fitness[max]
public void selectBestGh() {
    int k, i, maxid;
    int maxevaluation;  
maxid = 0;  
maxevaluation = fitness[0];  
for (k = 1; k &amp;lt; scale; k++) {  
    if (maxevaluation &amp;gt; fitness[k]) {  
        maxevaluation = fitness[k];  
        maxid = k;  
    }  
}  

if (bestLength &amp;gt; maxevaluation) {  
    bestLength = maxevaluation;  
    bestT = t;// 最好的染色体出现的代数;  
    for (i = 0; i &amp;lt; cityNum; i++) {  
        bestTour[i] = oldPopulation[maxid][i];  
    }  
}  

// System.out.println("代数 " + t + " " + maxevaluation);  
// 复制染色体，k表示新染色体在种群中的位置，kk表示旧的染色体在种群中的位置  
copyGh(0, maxid);// 将当代种群中适应度最高的染色体k复制到新种群中，排在第一位0  

}  
// 复制染色体，k表示新染色体在种群中的位置，kk表示旧的染色体在种群中的位置
public void copyGh(int k, int kk) {
    int i;
    for (i = 0; i &lt; cityNum; i++) {
        newPopulation[k][i] = oldPopulation[kk][i];
    }
}  
// 赌轮选择策略挑选
public void select() {
    int k, i, selectId;
    float ran1;
    // Random random = new Random(System.currentTimeMillis());
    for (k = 1; k &lt; scale; k++) {
        ran1 = (float) (random.nextInt(65535) % 1000 / 1000.0);
        // System.out.println(“概率”+ran1);
        // 产生方式
        for (i = 0; i &lt; scale; i++) {
            if (ran1 &lt;= Pi[i]) {
                break;
            }
        }
        selectId = i;
        // System.out.println(“选中” + selectId);
        copyGh(k, selectId);
    }
}  
//进化函数，正常交叉变异
public void evolution() {
    int k;
    // 挑选某代种群中适应度最高的个体
    selectBestGh();  
// 赌轮选择策略挑选scale-1个下一代个体  
select();  

// Random random = new Random(System.currentTimeMillis());  
float r;  

// 交叉方法  
for (k = 0; k &amp;lt; scale; k = k + 2) {  
    r = random.nextFloat();// /产生概率  
    // System.out.println("交叉率..." + r);  
    if (r &amp;lt; Pc) {  
        // System.out.println(k + "与" + k + 1 + "进行交叉...");  
        //OXCross(k, k + 1);// 进行交叉  
        OXCross1(k, k + 1);  
    } else {  
        r = random.nextFloat();// /产生概率  
        // System.out.println("变异率1..." + r);  
        // 变异  
        if (r &amp;lt; Pm) {  
            // System.out.println(k + "变异...");  
            OnCVariation(k);  
        }  
        r = random.nextFloat();// /产生概率  
        // System.out.println("变异率2..." + r);  
        // 变异  
        if (r &amp;lt; Pm) {  
            // System.out.println(k + 1 + "变异...");  
            OnCVariation(k + 1);  
        }  
    }  

}  

}  
//进化函数，保留最好染色体不进行交叉变异
public void evolution1() {
    int k;
    // 挑选某代种群中适应度最高的个体
    selectBestGh();  
// 赌轮选择策略挑选scale-1个下一代个体  
select();  

// Random random = new Random(System.currentTimeMillis());  
float r;  

for (k = 1; k + 1 &amp;lt; scale / 2; k = k + 2) {  
    r = random.nextFloat();// /产生概率  
    if (r &amp;lt; Pc) {  
        OXCross1(k, k + 1);// 进行交叉  
        //OXCross(k,k+1);//进行交叉  
    } else {  
        r = random.nextFloat();// /产生概率  
        // 变异  
        if (r &amp;lt; Pm) {  
            OnCVariation(k);  
        }  
        r = random.nextFloat();// /产生概率  
        // 变异  
        if (r &amp;lt; Pm) {  
            OnCVariation(k + 1);  
        }  
    }  
}  
if (k == scale / 2 - 1)// 剩最后一个染色体没有交叉L-1  
{  
    r = random.nextFloat();// /产生概率  
    if (r &amp;lt; Pm) {  
        OnCVariation(k);  
    }  
}  

}  
// 类OX交叉算子
void OXCross(int k1, int k2) {
    int i, j, k, flag;
    int ran1, ran2, temp;
    int[] Gh1 = new int[cityNum];
    int[] Gh2 = new int[cityNum];
    // Random random = new Random(System.currentTimeMillis());  
ran1 = random.nextInt(65535) % cityNum;  
ran2 = random.nextInt(65535) % cityNum;  
// System.out.println();  
// System.out.println("-----------------------");  
// System.out.println("----"+ran1+"----"+ran2);  

while (ran1 == ran2) {  
    ran2 = random.nextInt(65535) % cityNum;  
}  

if (ran1 &amp;gt; ran2)// 确保ran1&amp;lt;ran2  
{  
    temp = ran1;  
    ran1 = ran2;  
    ran2 = temp;  
}  
// System.out.println();  
// System.out.println("-----------------------");  
// System.out.println("----"+ran1+"----"+ran2);  
// System.out.println("-----------------------");  
// System.out.println();  
flag = ran2 - ran1 + 1;// 删除重复基因前染色体长度  
for (i = 0, j = ran1; i &amp;lt; flag; i++, j++) {  
    Gh1[i] = newPopulation[k2][j];  
    Gh2[i] = newPopulation[k1][j];  
}  
// 已近赋值i=ran2-ran1个基因  

for (k = 0, j = flag; j &amp;lt; cityNum;)// 染色体长度  
{  
    Gh1[j] = newPopulation[k1][k++];  
    for (i = 0; i &amp;lt; flag; i++) {  
        if (Gh1[i] == Gh1[j]) {  
            break;  
        }  
    }  
    if (i == flag) {  
        j++;  
    }  
}  

for (k = 0, j = flag; j &amp;lt; cityNum;)// 染色体长度  
{  
    Gh2[j] = newPopulation[k2][k++];  
    for (i = 0; i &amp;lt; flag; i++) {  
        if (Gh2[i] == Gh2[j]) {  
            break;  
        }  
    }  
    if (i == flag) {  
        j++;  
    }  
}  

for (i = 0; i &amp;lt; cityNum; i++) {  
    newPopulation[k1][i] = Gh1[i];// 交叉完毕放回种群  
    newPopulation[k2][i] = Gh2[i];// 交叉完毕放回种群  
}  

// System.out.println("进行交叉--------------------------");  
// System.out.println(k1+"交叉后...");  
// for (i = 0; i &amp;lt; cityNum; i++) {  
// System.out.print(newPopulation[k1][i] + "-");  
// }  
// System.out.println();  
// System.out.println(k2+"交叉后...");  
// for (i = 0; i &amp;lt; cityNum; i++) {  
// System.out.print(newPopulation[k2][i] + "-");  
// }  
// System.out.println();  
// System.out.println("交叉完毕--------------------------");  

}  
// 交叉算子,相同染色体交叉产生不同子代染色体
public void OXCross1(int k1, int k2) {
    int i, j, k, flag;
    int ran1, ran2, temp;
    int[] Gh1 = new int[cityNum];
    int[] Gh2 = new int[cityNum];
    // Random random = new Random(System.currentTimeMillis());  
ran1 = random.nextInt(65535) % cityNum;  
ran2 = random.nextInt(65535) % cityNum;  
while (ran1 == ran2) {  
    ran2 = random.nextInt(65535) % cityNum;  
}  

if (ran1 &amp;gt; ran2)// 确保ran1&amp;lt;ran2  
{  
    temp = ran1;  
    ran1 = ran2;  
    ran2 = temp;  
}  

// 将染色体1中的第三部分移到染色体2的首部  
for (i = 0, j = ran2; j &amp;lt; cityNum; i++, j++) {  
    Gh2[i] = newPopulation[k1][j];  
}  

flag = i;// 染色体2原基因开始位置  

for (k = 0, j = flag; j &amp;lt; cityNum;)// 染色体长度  
{  
    Gh2[j] = newPopulation[k2][k++];  
    for (i = 0; i &amp;lt; flag; i++) {  
        if (Gh2[i] == Gh2[j]) {  
            break;  
        }  
    }  
    if (i == flag) {  
        j++;  
    }  
}  

flag = ran1;  
for (k = 0, j = 0; k &amp;lt; cityNum;)// 染色体长度  
{  
    Gh1[j] = newPopulation[k1][k++];  
    for (i = 0; i &amp;lt; flag; i++) {  
        if (newPopulation[k2][i] == Gh1[j]) {  
            break;  
        }  
    }  
    if (i == flag) {  
        j++;  
    }  
}  

flag = cityNum - ran1;  

for (i = 0, j = flag; j &amp;lt; cityNum; j++, i++) {  
    Gh1[j] = newPopulation[k2][i];  
}  

for (i = 0; i &amp;lt; cityNum; i++) {  
    newPopulation[k1][i] = Gh1[i];// 交叉完毕放回种群  
    newPopulation[k2][i] = Gh2[i];// 交叉完毕放回种群  
}  

}  
// 多次对换变异算子
public void OnCVariation(int k) {
    int ran1, ran2, temp;
    int count;// 对换次数  
// Random random = new Random(System.currentTimeMillis());  
count = random.nextInt(65535) % cityNum;  

for (int i = 0; i &amp;lt; count; i++) {  

    ran1 = random.nextInt(65535) % cityNum;  
    ran2 = random.nextInt(65535) % cityNum;  
    while (ran1 == ran2) {  
        ran2 = random.nextInt(65535) % cityNum;  
    }  
    temp = newPopulation[k][ran1];  
    newPopulation[k][ran1] = newPopulation[k][ran2];  
    newPopulation[k][ran2] = temp;  
}  

/* 
 * for(i=0;i&amp;lt;L;i++) { printf("%d ",newGroup[k][i]); } printf("\n"); 
 */  

}  
public void solve() {
    int i;
    int k;  
// 初始化种群  
initGroup();  
// 计算初始化种群适应度，Fitness[max]  
for (k = 0; k &amp;lt; scale; k++) {  
    fitness[k] = evaluate(oldPopulation[k]);  
    // System.out.println(fitness[k]);  
}  
// 计算初始化种群中各个个体的累积概率，Pi[max]  
countRate();  
System.out.println("初始种群...");  
for (k = 0; k &amp;lt; scale; k++) {  
    for (i = 0; i &amp;lt; cityNum; i++) {  
        System.out.print(oldPopulation[k][i] + ",");  
    }  
    System.out.println();  
    System.out.println("----" + fitness[k] + " " + Pi[k]);  
}  
  
for (t = 0; t &amp;lt; MAX_GEN; t++) {  
    //evolution1();  
    evolution();  
    // 将新种群newGroup复制到旧种群oldGroup中，准备下一代进化  
    for (k = 0; k &amp;lt; scale; k++) {  
        for (i = 0; i &amp;lt; cityNum; i++) {  
            oldPopulation[k][i] = newPopulation[k][i];  
        }  
    }  
    // 计算种群适应度  
    for (k = 0; k &amp;lt; scale; k++) {  
        fitness[k] = evaluate(oldPopulation[k]);  
    }  
    // 计算种群中各个个体的累积概率  
    countRate();  
}  

System.out.println("最后种群...");  
for (k = 0; k &amp;lt; scale; k++) {  
    for (i = 0; i &amp;lt; cityNum; i++) {  
        System.out.print(oldPopulation[k][i] + ",");  
    }  
    System.out.println();  
    System.out.println("---" + fitness[k] + " " + Pi[k]);  
}  

System.out.println("最佳长度出现代数：");  
System.out.println(bestT);  
System.out.println("最佳长度");  
System.out.println(bestLength);  
System.out.println("最佳路径：");  
for (i = 0; i &amp;lt; cityNum; i++) {  
    System.out.print(bestTour[i] + ",");  
}  

}  
/** 

@param args 
@throws IOException
 */
public static void main(String[] args) throws IOException {
 System.out.println(“Start….”);
 GA ga = new GA(30, 48, 1000, 0.8f, 0.9f);
 ga.init(“c://data.txt”);
 ga.solve();
}


}

参考：https://blog.csdn.net/tyhj_sf/article/details/53321527

贪心算法-旅行商问题

发表于 2022-12-27 分类于 algrithom

问题

有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路已保证其旅行的费用最少？

还有背包、装箱问题

注：递归，时间复杂度为n!

贪心算法

在对问题求解时，总是做出当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。这是一种算法策略，每次选择得到的都是局部最优解。选择的策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

求解的问题分成若干个子问题，每一个子问题求解，得到子问题的局部最优解，子问题的局部最优解合成原问题的一个解

步骤

从某一个城市开始，每次选择一个城市，直到所有的城市被走完。

每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最小。

 从问题的某一初始解出发；
     while （能朝给定总目标前进一步）
     { 
           利用可行的决策，求出可行解的一个解元素；
     }
 由所有解元素组合成问题的一个可行解

缺点

不能保证最终为最优解
不能用来求最大最小解问题
无后效性

代码实现

package noah;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class TxTsp {
private int cityNum; // 城市数量
private int[][] distance; // 距离矩阵

private int[] colable;//代表列，也表示是否走过，走过置0
private int[] row;//代表行，选过置0
public TxTsp(int n) {
    cityNum = n;
}
private void init(String filename) throws IOException {
    // 读取数据
    int[] x;
    int[] y;
    String strbuff;
    BufferedReader data = new BufferedReader(new InputStreamReader(
            new FileInputStream(filename)));
    distance = new int[cityNum][cityNum];
    x = new int[cityNum];
    y = new int[cityNum];
    for (int i = 0; i &lt; cityNum; i++) {
        // 读取一行数据，数据格式1 6734 1453
        strbuff = data.readLine();
        // 字符分割
        String[] strcol = strbuff.split(“ “);
        x[i] = Integer.valueOf(strcol[1]);// x坐标
        y[i] = Integer.valueOf(strcol[2]);// y坐标
    }
    data.close();
// 计算距离矩阵
// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
for (int i = 0; i &amp;lt; cityNum - 1; i++) {
    distance[i][i] = 0; // 对角线为0
    for (int j = i + 1; j &amp;lt; cityNum; j++) {
        double rij = Math
                .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
                        * (y[i] - y[j])) / 10.0);
        // 四舍五入，取整
        int tij = (int) Math.round(rij);
        if (tij &amp;lt; rij) {
            distance[i][j] = tij + 1;
            distance[j][i] = distance[i][j];
        } else {
            distance[i][j] = tij;
            distance[j][i] = distance[i][j];
        }
    }
}

distance[cityNum - 1][cityNum - 1] = 0;

colable = new int[cityNum];
colable[0] = 0;
for (int i = 1; i &amp;lt; cityNum; i++) {
    colable[i] = 1;
}

row = new int[cityNum];
for (int i = 0; i &amp;lt; cityNum; i++) {
    row[i] = 1;
}

}
public void solve(){
int[] temp = new int[cityNum];
String path="0";

int s=0;//计算距离
int i=0;//当前节点
int j=0;//下一个节点
//默认从0开始
while(row[i]==1){
    //复制一行
    for (int k = 0; k &amp;lt; cityNum; k++) {
        temp[k] = distance[i][k];
        //System.out.print(temp[k]+" ");
    }
    //System.out.println();
    //选择下一个节点，要求不是已经走过，并且与i不同
    j = selectmin(temp);
    //找出下一节点
    row[i] = 0;//行置0，表示已经选过
    colable[j] = 0;//列0，表示已经走过
    
    path+="--&amp;gt;" + j;
    //System.out.println(i + "--&amp;gt;" + j);
    //System.out.println(distance[i][j]);
    s = s + distance[i][j];
    i = j;//当前节点指向下一节点
}
System.out.println("路径:" + path);
System.out.println("总距离为:" + s);

}
public int selectmin(int[] p){
    int j = 0, m = p[0], k = 0;
    //寻找第一个可用节点，注意最后一次寻找，没有可用节点
    while (colable[j] == 0) {
        j++;
        //System.out.print(j+” “);
        if(j&gt;=cityNum){
            //没有可用节点，说明已结束，最后一次为 *–&gt;0
            m = p[0];
            break;
            //或者直接return 0;
        }
        else{
            m = p[j];
        }
    }
    //从可用节点J开始往后扫描，找出距离最小节点
    for (; j &lt; cityNum; j++) {
        if (colable[j] == 1) {
            if (m &gt;= p[j]) {
                m = p[j];
                k = j;
            }
        }
    }
    return k;
}
public void printinit() {
    System.out.println(“print begin….”);
    for (int i = 0; i &lt; cityNum; i++) {
        for (int j = 0; j &lt; cityNum; j++) {
            System.out.print(distance[i][j] + “ “);
        }
        System.out.println();
    }
    System.out.println(“print end….”);
}
public static void main(String[] args) throws IOException {
    System.out.println(“Start….”);
    TxTsp ts = new TxTsp(48);
    ts.init(“c://data.txt”);
    //ts.printinit();
    ts.solve();
}

}

背包问题

发表于 2022-12-27 分类于 algrithom

背包问题是动态规划领域中一个重要且经典的问题，涉及在限定容量的背包中如何选择物品，使得物品的总价值最大化或总重量最小化。主要有两类背包问题：0-1背包问题和完全背包问题。

0-1背包问题：每个物品要么被选择一次，要么不选。
完全背包问题：每个物品可以被选择无限次。

以下是背包问题的一般步骤：

定义状态：通常使用一个二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 个物品在背包容量为 j 时的最优解（价值或重量）。
状态转移方程：对于每个物品，可以选择将其放入背包（如果容量允许），也可以选择不放入。状态转移方程通常为：
1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
其中 weight[i] 表示第 i 个物品的重量，value[i] 表示第 i 个物品的价值。
边界条件：初始时，当没有物品可选时，dp[0][j] 都应为 0，当背包容量为 0 时，dp[i][0] 也都为 0。
计算顺序：通常从小规模问题开始，逐步计算出大规模问题的最优解。

下面是一个0-1背包问题的 Java 代码示例：

public class KnapsackProblem {
    public int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][capacity];
    }

    public static void main(String[] args) {
        KnapsackProblem knapsackProblem = new KnapsackProblem();
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;
        int maxValue = knapsackProblem.knapsack(weights, values, capacity);
        System.out.println("Maximum value: " + maxValue);
    }
}

在这个示例中，我们使用动态规划解决了0-1背包问题。通过遍历每个物品和背包容量，根据状态转移方程计算在当前情况下的最优解。最终，dp[n][capacity] 就是问题的最优解，表示在前 n 个物品中选择放入容量为 capacity 的背包所能获得的最大价值。

请注意，背包问题的动态规划解法也可能因为问题的具体要求而有所变化，但通常都涵盖了上述的状态定义、状态转移方程和边界条件。

线性dp LIS

发表于 2022-12-27 分类于 algrithom

线性动态规划（Linear Dynamic Programming）在许多问题中都有广泛的应用，其中一个典型的问题是最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题。LIS 问题的目标是找到一个给定序列中的最长递增子序列的长度，其中递增子序列指的是序列中的元素按照顺序递增排列。

以下是最长递增子序列问题的一般步骤：

定义状态：通常使用一个数组 dp，其中 dp[i] 表示以第 i 个元素为结尾的最长递增子序列的长度。
状态转移方程：对于第 i 个元素，我们需要找到前面所有比它小的元素中，以它们为结尾的最长递增子序列的最大长度。状态转移方程可以表示为：
1
dp[i] = max(dp[j] + 1), 其中 0 <= j < i 且 nums[j] < nums[i]
这意味着我们在计算 dp[i] 时，会考虑前面所有满足条件的 dp[j] 的最大值加 1。
边界条件：初始时，每个元素自成一个长度为 1 的递增子序列，所以 dp[i] = 1。
计算顺序：通常从小规模问题开始，逐步计算出大规模问题的最优解。

下面是一个最长递增子序列问题的 Java 代码示例：

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxLength = 0;
        for (int len : dp) {
            maxLength = Math.max(maxLength, len);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int maxLength = lis.lengthOfLIS(nums);
        System.out.println("Length of longest increasing subsequence: " + maxLength);
    }
}

在这个示例中，我们使用动态规划解决了最长递增子序列问题。通过遍历每个元素，根据状态转移方程计算以当前元素为结尾的最长递增子序列长度。最终，我们在 dp 数组中找到最大的长度，即为最长递增子序列的长度。

请注意，LIS 问题的动态规划解法可能因为问题的具体要求而有所变化，但通常都涵盖了上述的状态定义、状态转移方程和边界条件。

石子合并问题

发表于 2022-12-27 分类于 algrithom

石子合并问题是一个经典的动态规划问题，其目标是找到一种合并方式，使得合并石子的总代价最小。在这个问题中，一开始有一排石子，每个石子有一个权值，合并两个相邻的石子可以获得它们的权值之和作为代价。问题的关键在于如何安排合并的顺序，以获得最小的总代价。

下面是石子合并问题的一般步骤：

定义状态：通常使用一个二维数组 dp[i][j] 表示合并第 i 到第 j 个石子所需的最小代价。
状态转移方程：假设要合并第 i 到第 j 个石子，可以将它们分为两部分：第 i 到 k 个石子和第 k+1 到 j 个石子，其中 i <= k < j。那么合并的代价就是将这两部分合并的代价加上这两部分的权值之和。状态转移方程可以表示为：
1
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j]), 其中 i <= k < j
其中 sum[i][j] 表示第 i 到第 j 个石子的权值之和。
边界条件：当 i == j 时，只有一个石子，无需合并，所以 dp[i][i] = 0。
计算顺序：通常从小规模问题开始，逐步计算出大规模问题的最优解。

下面是一个简单的石子合并问题的 Java 代码示例：

public class StoneMergeProblem {
    public int mergeStones(int[] stones) {
        int n = stones.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
        }
        
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        StoneMergeProblem problem = new StoneMergeProblem();
        int[] stones = {3, 1, 4, 2};
        int minCost = problem.mergeStones(stones);
        System.out.println("Minimum cost to merge stones: " + minCost);
    }
}

在这个示例中，我们使用了动态规划来解决石子合并问题。首先计算了石子的前缀和，然后使用二维数组 dp 来存储合并石子的最小代价。根据状态转移方程，我们通过计算不同的区间长度和区间起始位置，逐步填充 dp 数组，最终得到合并所有石子的最小代价。

需要注意的是，石子合并问题的动态规划解法通常要结合问题的具体要求来确定状态转移方程，边界条件等。

环形DP

发表于 2022-12-27 分类于 algrithom

环形动态规划（Circular Dynamic Programming）是一种动态规划的应用，适用于解决环形问题，即问题中的元素或状态在某种意义上是循环的，首尾相连的。这类问题在动态规划中需要考虑元素之间的相互关系，以及环形带来的特殊情况。

一般来说，环形动态规划的核心思想是将环形问题转化为线性问题，然后通过适当的状态转移方程和边界条件来求解。以下是环形动态规划的一般步骤：

问题转化：将环形问题转化为线性问题。可以通过复制一份原始数据，将环形结构“展开”成线性结构，从而将问题转化为已知的线性动态规划问题。
定义状态：定义动态规划的状态，通常与问题的特性相关。对于环形问题，需要考虑首尾相连的情况，可能需要多设置一个状态来表示“首尾相连”的状态。
确定状态转移方程：根据问题的性质，确定状态之间的转移关系。考虑环形结构，需要确保转移关系在环形首尾相连的情况下也能正确地进行。
确定边界条件：环形问题的边界条件可能相对复杂，需要确保首尾相连的元素能够正确处理。这些边界条件可能需要在状态转移方程中单独处理。
计算顺序：通常从小规模问题开始，按照线性结构的顺序逐步计算状态，直到计算出整个环形结构的状态。

下面以一个具体问题为例，来说明环形动态规划的应用。假设有一个环形数组，每个元素代表一个房屋，每个房屋中有一定数量的金钱。由于房屋是环形排列的，意味着第一个和最后一个房屋也相邻。要求在不偷相邻房屋的情况下，计算可以偷到的最大金钱数。

public class CircularDPExample {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        }
        
        // Calculate the maximum amount that can be robbed if starting from the first house.
        int[] dp1 = new int[n];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        
        // Calculate the maximum amount that can be robbed if starting from the second house.
        int[] dp2 = new int[n];
        dp2[1] = nums[1];
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }
        
        // The maximum amount that can be robbed will be the maximum of the two scenarios.
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }

    public static void main(String[] args) {
        CircularDPExample example = new CircularDPExample();
        int[] nums = {2, 7, 9, 3, 1};
        int maxAmount = example.rob(nums);
        System.out.println("Maximum amount that can be robbed: " + maxAmount);
    }
}

在这个例子中，我们通过定义两个状态数组 dp1 和 dp2，分别表示从第一个房屋和第二个房屋开始偷窃时的最大金额。通过动态规划的思想，我们逐步计算出每个状态的最大金额，最终得到在不偷相邻房屋的情况下可以偷到的最大金钱数。

请注意，以上仅是环形动态规划的一个简单例子。实际应用中，问题可能会更加复杂，需要根据问题的具体情况来定义状态、状态转移方程和边界条件。

状压DP

发表于 2022-12-27 分类于 algrithom

状压动态规划（Bitmask Dynamic Programming，状压DP）是一种优化技巧，通常用于解决组合优化问题，特别是集合的子集问题。以下是一个使用状压DP解决集合的最短路径问题的Java代码示例：

public class BitmaskDP {

    public static int shortestPath(int n, int[][] dist) {
        int totalStates = 1 << n;  // Total possible subsets

        int[][] dp = new int[n][totalStates];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[0][1] = 0;  // Starting state: only the first city visited

        for (int mask = 1; mask < totalStates; mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) != 0) {  // Check if u is in the current subset
                    for (int v = 0; v < n; v++) {
                        if (v != u && (mask & (1 << v)) != 0) {  // Check if v is in the current subset and not equal to u
                            dp[u][mask] = Math.min(dp[u][mask], dp[v][mask ^ (1 << u)] + dist[v][u]);
                        }
                    }
                }
            }
        }

        int minPath = Integer.MAX_VALUE;
        for (int u = 1; u < n; u++) {
            minPath = Math.min(minPath, dp[u][totalStates - 1] + dist[u][0]);
        }

        return minPath;
    }

    public static void main(String[] args) {
        int n = 4;  // Number of cities
        int[][] dist = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        int shortest = shortestPath(n, dist);
        System.out.println("Shortest Path: " + shortest);
    }
}

在这个示例中，shortestPath 方法使用状压DP解决了集合的最短路径问题。算法通过构建一个二维数组 dp 来保存状态转移，从而计算最短路径。

请注意，状压DP通常用于解决集合的子集问题，例如在TSP（Traveling Salesman Problem）中寻找最短路径。实际应用中，可能需要根据问题的需求进行适当的修改。

深度优先广度优先

发表于 2022-12-27 分类于 algrithom

深度优先

深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。整个遍历过程如下：

首先将A节点压入栈中，stack（A）;
将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)；
将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）；
将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）；
将E节点弹出，同时将E的子节点I压入，stack（I,C）；

…依次往下，最终遍历完成

public void depthFirst() {

Stack&lt;Map&lt;String, Object&gt;&gt; nodeStack = new Stack&lt;Map&lt;String, Object&gt;&gt;();

Map&lt;String, Object&gt; node = new HashMap&lt;String, Object&gt;();

nodeStack.add(node);

while (!nodeStack.isEmpty()) {

    node = nodeStack.pop();

    System.out.println(node);

    //获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点

    List&lt;Map&lt;String, Object&gt;&gt; children = getChildren(node);

    if (children != null &amp;&amp; !children.isEmpty()) {

        for (Map child : children) {

            nodeStack.push(child);

        }

    }

}

}

广度优先

广度优先遍历各个节点，需要使用到队列（Queue）这种数据结构，queue的特点是先进先出，其实也可以使用双端队列，区别就是双端队列首尾都可以插入和弹出节点。整个遍历过程如下：

首先将A节点插入队列中，queue（A）;
将A节点弹出，同时将A的子节点B，C插入队列中，此时B在队列首，C在队列尾部，queue（B，C）；
将B节点弹出，同时将B的子节点D，E插入队列中，此时C在队列首，E在队列尾部，queue（C，D，E）;
将C节点弹出，同时将C的子节点F，G，H插入队列中，此时D在队列首，H在队列尾部，queue（D，E，F，G，H）；
将D节点弹出，D没有子节点，此时E在队列首，H在队列尾部，queue（E，F，G，H）；

…依次往下，最终遍历完成

public void breadthFirst() {

Deque&lt;Map&lt;String, Object&gt;&gt; nodeDeque = new ArrayDeque&lt;Map&lt;String, Object&gt;&gt;();

Map&lt;String, Object&gt; node = new HashMap&lt;String, Object&gt;();

nodeDeque.add(node);

while (!nodeDeque.isEmpty()) {

    node = nodeDeque.peekFirst();

    System.out.println(node);

    //获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点

    List&lt;Map&lt;String, Object&gt;&gt; children = getChildren(node);

    if (children != null &amp;&amp; !children.isEmpty()) {

        for (Map child : children) {

            nodeDeque.add(child);

        }

    }

}

}

最长上升子序列最大连续子序列和，最长公共子串

发表于 2022-12-27 分类于 algrithom

下面是分别解决最长上升子序列、最大连续子序列和和最长公共子串问题的Java代码示例：

最长上升子序列（Longest Increasing Subsequence）：

public class LongestIncreasingSubsequence {

    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;  // Minimum length is 1 (the element itself)
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int lisLength = lengthOfLIS(nums);
        System.out.println("Length of Longest Increasing Subsequence: " + lisLength);
    }
}

最大连续子序列和（Maximum Subarray Sum）：

public class MaximumSubarraySum {

    public static int maxSubArraySum(int[] nums) {
        int n = nums.length;
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < n; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = maxSubArraySum(nums);
        System.out.println("Maximum Subarray Sum: " + maxSum);
    }
}

最长公共子串（Longest Common Substring）：

public class LongestCommonSubstring {

    public static int longestCommonSubstring(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s1 = "ABABC";
        String s2 = "BABCBA";
        int commonSubstringLength = longestCommonSubstring(s1, s2);
        System.out.println("Length of Longest Common Substring: " + commonSubstringLength);
    }
}

这些示例分别展示了如何解决最长上升子序列、最大连续子序列和和最长公共子串问题。实际应用中，根据问题的需求可能需要进行适当的修改。