Задача Коммивояжера

ritmix93

New Member
19.06.2013
1
0
#1
Имеется N населённых пунктов, пронумерованных от 1 до N. Некоторые пары населенных пунктов соединены дорогами. Известны стоимости проездов по этим дорогам. Определить, можно ли попасть по этим дорогам из первого пункта в N-ный. Если да, то найти маршрут с минимальной стоимостью проезда.

program proezd;

const
Max = 5;

var
A: Array[1..Max, 1..Max] Of Integer;
{ *Матрица расстояний между городами. *}
f: text;
N: integer;
B: Array[1..Max, 1..Max] Of Byte;{^Вспомогательный
массив, элементы каждой строки матрицы
сортируются в порядке возрастания, но сами
элементы не переставляются, а изменяются
в матрице В номера столбцов матрицы А.*}
Way, BestWay: Array[1..Max] Of Byte;{*Хранится
текущее решение и лучшее решение. *}
Nnew: Array[1..Max] Of Boolean;{*3начение
элемента массива False говорит о том,
что в соответствующем городе коммивояжер
уже побывал. *}
BestCost: Integer;{*Стоимость лучшего решения. *}


procedure Solve(v, Count: Byte; Cost: Integer);
{*v - номер текущего города; Count - счетчик числа
пройденных городов; Cost - стоимость текущего
решения. *}
var
i: Integer;
begin
if Cost > BestCost Then Exit;{*Стоимость текущего
решения превышает стоимость лучшего из
ранее полученных. *}
if Count = N Then begin
Cost := Cost + A[v, 1];
Way[N] := v;{*Последний город
пути. Добавляем к решению стоимость
перемещения в первый город и сравниваем
его с лучшим из ранее полученных. *}
if Cost < BestCost Then begin
BestCost := Cost;
BestWay := Way; end;
Exit;{*Оператор нарушает структурный стиль
программирования ~ "любой фрагмент логики
должен иметь одну точку входа и одну точку
выхода. Следует убрать его" . *}
end;

Nnew[v] := False;
Way[Count] := v;{*Город с номером v
пройден, записываем его номер в путь
коммивояжера. *}
for i := 1 To N do
if Nnew[B[v, i]] Then Solve(B[v, i],
Count + 1, Cost + A[v, B[v, i]]); {*Поиск города, в который
коммивояжер может пойти из города,
с номером v.*}
Nnew[v] := True; {^Возвращаем город с номером v
в число непройденных. *}
end;

var
i, j: integer;

begin
assign(f, 'f:\1.txt');
reset(f);
i := 1;
j := 1;
while not eof(f) do
begin
while not eoln(f) do
begin
read(f, a[i, j]);
inc(j);
end;
readln(f);
inc(i);
end;
solve();
writeln('лучшая цена-', BestCost);
end.



Просьба исправить и доработать