Задача коммивояжера! Мое решение, помогите дорешать!

← →
Dbe (2006-11-26 15:07) [0]

Помоги, пожалуйста, разобраться! Вот такая задача и примерно мое решение! Как доделать! Заранее благодарен!

Дано множество точек на плоскости. Найти ломаную минимальной длины, соединяющую все точки множества.
Вход:
В текстовом файле INPUT.TXT записаны вещественные координаты точек. Количество точек НЕ записано в файле, но не превосходит 30.
Выход:
В текстовый файл OUTPUT.TXT записать длину найденной ломаной с тремя дробными цифрами.
Пример входа:
1.99 -1.31
8.91 4.44
1.29 -7.21
8.28 9.73
-9.07 1.80
2.66 -7.42
Пример выхода:
35.587

Мое решение:

{$APPTYPE CONSOLE}
uses
SysUtils;
const
Nmax=100;
type
Tpoint=record
x,y: real;
end;
var
a: array[1..Nmax,1..Nmax] of real;
p: array[1..Nmax] of Tpoint;
n,i,j: integer;

function dlina(a,b: Tpoint): real;
begin
dlina:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
end;
begin
Assign(Input,"input.txt"); reset(Input);
Assign(output,"output.txt"); rewrite(output);
readln(n);
for i:=1 to n do readln(p[i].x,p[i].y);
for i:=1 to n do
for j:=1 to n do a[i,j]:=dlina(p[i],p[j]); //тут создается матрица смежности
// а что дальше?
end.

← →
MBo © (2006-11-26 16:13) [1]

В google нетрудно найти, например, решение методом ветвей и границ

← →
shcamane (2006-11-26 16:15) [2]

Задача о коммавояжоре не имеет четкого, не эвристического решения, кроме метода полной индукции.

← →
Рамиль © (2006-11-26 16:50) [3]

> Мое решение:

> // а что дальше?

С тем же успехом мог сказать дайте код :)

← →
KilkennyCat © (2006-11-26 17:02) [4]

> // а что дальше?

баул на горб и вперед, торговать.

← →
Anatoly Podgoretsky © (2006-11-26 17:24) [5]

> KilkennyCat (26.11.2006 17:02:04) [4]

Опыта набираться :-)

> shcamane (26.11.06 16:15) [2]

... в общем случае. В частных случаях - имеет.

← →
PHPDeveloper (2006-11-27 05:32) [7]

Мде.
Есть книга, название и автора не помню :DD (в голове крутится, но вспомнить не могу), так там разобраны методы решения распрастраненных задача (ваша задача, ханойские башни и т.п.). Если не ошибась можно найти на сайте: g6prog.narod.ru, там же в разборах задач, может что полезное есть.
Давно там был

Задача коммивояжера! Мое решение, помогите дорешать! Найти похожие ветки