Двойной выбор можно
обобщить как выбор k элементов для любого
постоянного k. В этом случае мы удаляем
до k ребер и «перекоммутируем» оставшиеся
элементы в любом порядке, пытаясь получить
какой-либо маршрут. Обратите внимание:
мы не требуем, чтобы удалённые рёбра вообще
были несмежными, хотя в случае двойного
выбора не было никакого смысла рассматривать
удаление двух смежных рёбер. Обратите
внимание, что при k>2 существует несколько
способов соединения частей графа.
Легко убедиться
в том, что дя фиксированного k количество
различных преобразований при k-выборе,
которые необходимо рассмортреть при
наличии вершин, равно O(nk). Например,
при k=2 точное количество таких преобразований
равно n(n-3)/2.
Однако время, которое
требуется для получения какого-либо из
локально-оптимальных маршрутов, может
оказаться значительно больше этой величины,
поскольку для получения этого локально-оптимального
маршрута надо выполнить довольно много
локальных преобразований, а каждое улучшающее
преобразование связано с введением новых
рёбер, которые могут учавствовать в последующих
преобразования и ещё больше улучшают
данный маршрут.
Интерфейс программы
Для реализации метода локального
поиска будем использовать систему программирования
Delphi.
Интерфейс программы состоит
из формы, на которой расположены компоненты.
StringGrid, отвечает за вывод матрицы стоимостей.
При нажатии на кнопку «загрузить»
выводится диалоговое окно для выбора
текстового файла, хранящего количество
вершин графа и матрицу стоимостей. Выбираем
в окне наш текстовый файл. В данном случае
– это файл «input.txt». В таблице выводится
матрица стоимостей графа. В строку Edit
нужно ввести целое число, означающее
сколько раз нужно провести испытание
поиска минимального маршрута. Чем больше
количество итераций, тем более точный
будет результат.
При нажатии на кнопку «найти
путь» выводится значение минимального
пути, найденного методом, и последовательность
пройденных вершин.
Реализация метода
локального поиска на ЭВМ
Для начала работы программы
ограничим количество вершин графа и запишем
матрицу стоимостей из файла в таблицу
StringGrid.
function LoadMatrice(fn: string; var CCount: integer;
strnggrd: tstringgrid): boolean;
var
f: textfile;
i, j: byte;
n: byte;
data: integer;
begin
assignfile(f, fn);
reset(f);
readln(f, n);
if (n < 4) then
begin
closefile(f);
showmessage('Слишком мало вершин
в файле! Вершин не может быть меньше 4');
LoadMatrice := false;
exit;
end;
if (n > maxn) then
begin
closefile(f);
showmessage('Слишком много вершин
в файле! Вершин не может быть больше '
+ inttostr(maxn));
LoadMatrice := false;
exit;
end;
CCount:=n;
strnggrd.ColCount := n+1;
strnggrd.RowCount := n+1;
strnggrd.Height := n * 24 + 24+n+4;
strnggrd.Width := n * 30 + 30+n+4;
for i := 1 to n do
begin
for j := 1 to n do
begin
read(f, data);
strnggrd.Cells[j, i] := inttostr(data);
end;
readln(f);
end;
closefile(f);
LoadMatrice := true;
end;
Далее идет заполнение массива
расстояний между городами с целью дальнейшего
использования этого массива для проведения
над ним расчетов.
procedure TForm1.Button1Click(Sender: TObject);
var
pathN: string;
num, i, j, d, s: integer;
begin
setlength(map, ColGorod + 1, ColGorod + 1);
for i := 1 to form1.StringGrid1.ColCount - 1 do //
заполняем карту-массив
for j := 1 to form1.StringGrid1.rowCount - 1 do
begin
if StringGrid1.Cells[i, j] = '' then
begin
map[i-1, j-1] := 0;
end
else
begin
map[i-1, j-1] := strtoint(form1.StringGrid1.Cells[i,
j]);
end;
end;
num := strtoint(Edit1.Text);
Monte.raschet(num, ColGorod, map, stoimost, pathN);
Memo1.Lines.Add('Оптимальный путь:
');
Memo1.Lines.Add(inttostr(stoimost));
Memo1.Lines.Add('Последовательность
пути: ');
Memo1.Lines.Add(pathN);
end;
Процедура генерации случайного
пути выглядит следующим образом:
procedure TDvoynoy_Vibor.GenerateFirstPath(var mas:
gorodN);
var m: set of byte; //множество проверенных
вершин
i: integer; //номер вершины в цикле
begin
setlength(mas, CityCount); //устанавливаем
длину массива по количеству городов
m := []; //очищаем множество проверенных
вершин
randomize;
for i := 0 to CityCount-1 do //цикл прохода
по вершинам
begin
repeat //цикл генерации случайного
города
if i=0 then //если первый город,
то он будет начальным
mas[i] := 0 //номер первого
else //если город не первый, тогда
mas[i] := random(CityCount); //выбираем случайный
город
until not(mas[i] in m); //если выбранный
случайный город еще не добавлен, повторяем
цикл иначе выходим из него
include(m, mas[i]); //добавление добавленного
города во множество
end;
end;
Процедура, отвечающая за расчёт:
procedure TDvoynoy_Vibor.raschet(iter: integer; CCount:
integer; m: maps; var s: integer; var Path: string);
var
i, j: integer;
gorod, Tempgorod: gorodN;
LenPath, TempLenPath: integer;
a, b, c: integer;
begin
randomize;
CityCount:=CCount;
setlength(m, CityCount, CityCount); // задаем
массивы
setlength(gorod, CityCount);
setlength(Tempgorod, CityCount);
LenPath:=0;
GenerateFirstPath(gorod);
LenPath := GetLenPath(m, gorod);
for j := 0 to CityCount - 1 do
Tempgorod[j]:=gorod[j];
for i := 0 to iter-1 do
begin
a:=random(CityCount-2)+1;
repeat
b:=random(CityCount-2)+1;
until not((a=b)or((a+1)=b));
if (m[a, a+1]+m[b, b+1])>(m[a, b]+m[a+1, b+1])
then
begin
c:=Tempgorod[a];
Tempgorod[a]:=Tempgorod[b];
Tempgorod[b]:=c;
c:=Tempgorod[a+1];
Tempgorod[a+1]:=Tempgorod[b+1];
Tempgorod[b+1]:=c;
end;
TempLenPath := GetLenPath(m, Tempgorod);
if LenPath>TempLenPath then
begin
for j := 0 to CityCount - 1 do
gorod[j]:=Tempgorod[j];
LenPath:=TempLenPath;
end;
end;
LenPath := GetLenPath(m, gorod);
s:=LenPath;
Path:='';
for i := 0 to CityCount - 1 do
begin
if i=0 then
Path := Path + inttostr(gorod[i]+1) + ' ';
Path := Path + '- ';
Path := Path + inttostr(gorod[(i + 1)mod CityCount]+1)
+ ' ';
end;
end;
Заключение
Целью этой курсовой работы
являлось рассмотрение метода локального
поиска для решения одной из задач минимизации
— задаче о коммивояжере, а также выяснение
связи этой задачи с другими задачами
линейного программирования.
Важность решения задачи о коммивояжере
связана с тем, что многие явления в физике
(особенно в кристаллографии) и проблемы
экономики представляются математическими
моделями, решение которых и есть решение
задачи о коммивояжере. Необходимо заметить,
что реальные жизненные ситуации обычно
оказываются намного сложнее искусственных
схем. Тем не менее, методы решения и этих
упрощенных моделей во многих случаях
могут подсказать пути отыскания лучшего
из множества конкурирующих вариантов.
Список литературы
1. Ашманов М. Г. Линейное
программирование. М., Наука, 1989.
2. Карманов Э. Т. Математическое
программирование. М., Наука, 1980.
3. А.В. Ахо, Д.Э.Хопкрофт, Д.Д.Ульман:
Структуры данных и алгоритмы
4. Дж. Литл, К. Мурти, Д. Суини,
К. Кэрел. Алгоритм для решения задачи
о коммивояжере. ─ “ Экономика и математические
методы”, т.1, вып. 1, 1965.
5. http://www.zachetik.ru/ref-117946-zadacha-kommivoyazhera.html
6. http://habrahabr.ru/post/151151/
7. http://www.myshared.ru/slide/486789/
1 Задача Де-Мере
заключается в следующем: два игрока условились
сыграть ряд партий, выигравшим считается
тот, кто первым выиграл S партий. Игра
была прервана тогда, когда один из игроков
выиграл
2 Паскаль, Блез
(1623—1661 гг.)— выдающийся французский математик
и физик, автор большого числа работ по
геометрии, теории чисел, теории вероятностей
и т. д. В 1641 г. одним из первых сконструировал
суммирующий автомат.
3 Борель, Эмиль
(1871—1956 гг.)— французский математик, известен
своими работами в области анализа, теории
множеств и теории вероятностей.