n クイーン問題を解決するためのシミュレーテッド アニーリング アルゴリズムに問題があります。基本的に、私はもっと良いものを探すようにしていますが、それは問題なく機能しますが、式を実行して、「悪い」動きをするべきかどうかを確認します。私の理解では、式は e^(ボード状態の計算の変化)/CurrentTemperature です。この数値は、ランダムな double または float と比較する必要があります。乱数が方程式よりも大きい場合、アルゴリズムは「悪い」動きを取る必要があります。私が得ている問題は、式が常に1に近いか1を超えていることです。ここに私のコードの一部を示します(さらに提供する必要がある場合はお知らせください):
temperature = n*100; //initializes starting temperature
currentTemp = n*100;
int cooldown = n*2; //initializes cool down temperature
float examine = 0; //this is the change in board calculation
int cost = 1;
boolean betterMove = false;
queen = new int[n];
int[][] board = graph; // generates a board of n size
float ran = 0; //random float to compare to
double compareAgainst = 0; //formula variable
cost = calculate(board, n); //calculates the cost
while (cost > 0 && currentTemp > 0)
{
// chooses a random queen to move that has a heuristic higher than zero
int Q = rand.nextInt(n);
while (queen[Q] == 0)
Q = rand.nextInt(n);
betterMove = false;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 1 && j == Q)
{
while (!betterMove)
{
int move = i;
while (move == i)
move = rand.nextInt(n); //pick a random move
tempBoard[i][j] = 0; //erase old position
tempBoard[move][j] = 1; //set new position
examine = calculate(tempBoard, n) - calculate(board, n); //calculates the difference between the change in boards
ran = rand.nextFloat(); //generates random number to compare against
compareAgainst = Math.pow(Math.E, (-examine / currentTemp)); //formula out of the book, basically is e^(change in board state divided by currentTemp)
if (calculate(tempBoard, n) < calculate(board, n)) //if this is a better move
{
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
board[a][b] = tempBoard[a][b]; //set it to the board
cost = calculate(board, n);
currentTemp -= cooldown; //cool down the temperature
betterMove = true;
}
else if(calculate(tempBoard,n) >= calculate(board,n)) //if this is a worse move
{
if(verbose == 1) //outputs whether or not this is a bad move and outputs function value and random float for simulated annealing purposes
{
System.out.println("This is a worse move");
System.out.println("The numbers for Simulated Annealing:");
System.out.println("Random number = " + ran);
System.out.println("Formula = " + compareAgainst);
System.out.println("Examine = " + examine);
}
if(ran > compareAgainst) //if the random float is greater than compare against, take the bad move
{
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
board[a][b] = tempBoard[a][b]; //take the move
cost = calculate(board, n);
currentTemp-= cooldown;
betterMove = true;
}
else //if not, do not take the move
{
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
tempBoard[a][b] = board[a][b];
}
currentTemp-= cooldown;
betterMove = true;
}
}
}
i = n;
j = n;
}
}
}
}
調べる変数を負にしたり、ボードの状態間の差の絶対値を取得したりするなど、多くのことを試しました。また、呼び出されている計算関数は基本的にボードをスキャンし、競合しているクイーンの数を int で返します。さらに説明が必要な場合はお知らせください。ありがとう
