![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
Иллюстрацией метода. будет N-Queens Problem
memberType - класс представляющий положение королев на доске. Функция TweakSolution - та самая хрень, случайным образом расставляющая королев на доске.
The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard.
В каждой колонке может располагаться лишь 1 фигура. Это облегчает задачу и существенно облегчает кодировку данных. Положение королев определяет одномерный массив размера n, каждый элемент которого может принимать значения от 1 до n. При этом все значения элементов массива уникальны, то есть сам массив размером n содержит n-1 натуральных чисел и 0 (так как код в сишарп, а первый элемент массива в языках семейства си имеет нулевой индекс).
memberType - класс представляющий положение королев на доске. Функция TweakSolution - та самая хрень, случайным образом расставляющая королев на доске.
class memberTypeКонструктор заполняет главную диагональ, а затем случайным образом перемешивает королев.
{
public int[] solution = new int[Program.MaxLength];
public float energy;
// Меняем положение коней из двух случаных столбцов местами.
public void TweakSolution()
{
int temp, x, y;
Random rnd = new Random();
x = rnd.Next(Program.MaxLength);
do
{
y = rnd.Next(Program.MaxLength);
}
while (x == y);
temp = this.solution[x];
this.solution[x] = solution[y];
this.solution[y] = temp;
}
public memberType()Дальше - больше :D. Энергия решения считается как количество конфликтов между королевами.
{
for (int i = 0; i < Program.MaxLength; i++)
{
solution[i] = i;
}
for (int i = 0; i < Program.MaxLength; i++)
{
TweakSolution();
}
}
public void ComputeEnergy()И последняя функция в классе решения просто выводит на экран оное.
{
int i, j, x, y, tempx, tempy, conflicts;
char [,]board = new char[Program.MaxLength,Program.MaxLength];
int[] dx = { -1, 1, -1, 1 };
int[] dy = { -1, 1, 1, -1 };
for (i = 0; i < Program.MaxLength; i++)
{
board[i,solution[i]] = 'Q';
}
conflicts = 0;
for ( i = 0; i < Program.MaxLength; i++)
{
x = i;
y = solution[i];
for ( j = 0; j < 4; j++)
{
tempx = x; tempy = y;
while (true)
{
tempx += dx[j];
tempy += dy[j];
if ((tempx < 0) || (tempx >= Program.MaxLength) || (tempy < 0) || (tempy >= Program.MaxLength))
break;
if (board[tempx,tempy] == 'Q') conflicts++;
}
}
}
energy = (float)conflicts;
}
public void emit()Теперь кульминация балета :D.
{
int MaxLength = Program.MaxLength;
char[,] board = new char[MaxLength, MaxLength];
int x, y;
for (x = 0; x < MaxLength; x++)
{
board[x, this.solution[x]] = 'Q';
}
for (y = 0; y < MaxLength; y++)
{
for (x = 0; x < MaxLength; x++)
{
if (board[x, y] != 'Q')
Console.Write(". ");
else
Console.Write("Q ");
}
Console.Write('\n');
}
Console.Write('\n');
}
}
class ProgramДо тех пор пока температура больше конечной выполняется алгоритм Metropolis Monte Carlo.
{
public static int MaxLength = 20; \\ размер доски
public static float InitialTemperature = 30.0f; \\ начальная температура
public static float FinalTemperature = 0.5f; \\ конечная температура
public static float Alpha = 0.99f; \\ во сколько раз уменьшается температура
public static int StepsPerChange = 100; \\ число итераций для каждого значения температуры
static void Main(string[] args)
{
int timer = 0, step, solution = 0, useNew, accepted;
float temperature = InitialTemperature;
memberType current, working, best;
StreamWriter Strw = new StreamWriter("strw");
Random rnd = new Random();
current = new memberType();
current.ComputeEnergy();
best = new memberType();
best.energy = 100.0f;
working = current;
- Если рабочее решение лучше данного (то есть энергия рабочего меньше) то он становится данным.
- Если же нет, то вычисляется вероятность принятия решения. Вероятность сравнивается со случайной величиной, меньше единицы, и если вероятность принятия рабочего решения больше случайной величины, то рабочее решение копируется в данное. В обратном случае соответсвенно данное копируется в рабочее.
T=Alpha*TИ в файл выводятся значения температуры, энергий и шага итерации.
while (temperature > FinalTemperature)В конце на экран выводится лучшее решение.
{
Console.WriteLine("Temperature: " + temperature);
accepted = 0;
for (step = 0; step < StepsPerChange; step++)
{
useNew = 0;
working.TweakSolution();
working.ComputeEnergy();
if (working.energy <= current.energy)
{
useNew = 1;
}
else
{
float test = (float)rnd.NextDouble();
float delta = working.energy - current.energy;
float calc = (float)Math.Exp(-delta / temperature);
if (calc > test)
{
accepted++;
useNew = 1;
}
}
if (useNew == 1)
{
useNew = 0;
current = working;
if (current.energy < best.energy)
{
best = current;
solution = 1;
}
else
{
working = current;
}
}
}
Strw.WriteLine("timer:" + timer++ + " Temperature:" + temperature +
" Best Energy: " + best.energy + " Accepted: " + accepted);
temperature *= Alpha;
}
Strw.Close();
if (solution == 1)
best.emit();
return;
}
}
}
