javascript - 如何实现节点模拟退火(TSP)

Question

我需要编写诸如旅行推销员问题之类的程序，但带有节点。我需要获得较少错位的金额。

我不知道如何使用玻尔兹曼常数实现模拟退火算法。

我已经编写了第一部分的代码:

`导入java.util.ArrayList；导入 java.util.Random;

公开课金额{ 私有(private)ArrayList数量；//所有节点列表 私有(private) int ak；//所有节点数 私有(private)随机兰特；//随机

public Amount(int a)
{
    amount = new ArrayList<Node>();
    ak = a;
    rand = new Random();

    int i = 0;
    while(i < ak)
    {
        Node k = new Node();
        amount.add(k);
        i++;
    }

    this.connect();
}
public ArrayList<Node> giveAmount()
{
    return amount;
}
public void connect()
{
    for(int i=0;i<ak;i++) //We gradually go through all the nodes and add neighbors to it        {
        for(int j=0;j<ak;j++) // We go through all the nodes again and add them with 20% probability as neighbors from the current node i
        {
            int k = rand.nextInt(10);
            if(k < 2 && i != j) //20% chance of connection, not possible with himself                {
                if(amount.get(i).showNeighbor().contains(amount.get(j)) == false) // Double neighborhood is avoided
                {
                    amount.get(i).newNeighbor(amount.get(j)); // j is stored as the neighbor of i                    }
                if(amount.get(j).showNeighbor().contains(amount.get(i)) == false) // Double neighborhood is avoided
                {
                    amount.get(j).newNeighbor(amount.get(i)); // i is stored as the neighbor of j                    }
            }
        }
    }
}

}`

如何使用这些节点在这里实现模拟退火？

我知道我需要这样的东西prob = Math.exp(-(proposal - current)/温度)

有人能给我一个示例代码吗？谢谢

Answer 1

您想阅读并尝试https://stackabuse.com/simulated-annealing-optimization-algorithm-in-java/

确实，概率部分是

    public static double probability(double f1, double f2, double temp) {
        if (f2 < f1) return 1;
        return Math.exp((f1 - f2) / temp);
    }

是示例的一部分。