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

← →
PelMen © (2003-05-20 15:25) [0]

Здравствуйте, люди добрые!

Подскажите пожалуйста где можно взять решенный subj?
Буду очень признателен за исходники :)

← →
Mike Kouzmine © (2003-05-20 16:05) [1]

Задача коммивояжера - как можно больше впарить товара. При чем здесь Делфи?

← →
Странник © (2003-05-20 16:13) [2]

> Mike Kouzmine © (20.05.03 16:05)
не помню уж за давностью лет - но там что-то на тему оптимизации перемещений. из серии - как перевезти козу, волка и капусту.

← →
pasha676 (2003-05-20 16:13) [3]

Mike - :). Это название классической задачи нахождения оптимального пути через определенные точки.

← →
Странник © (2003-05-20 16:14) [4]

> Mike Kouzmine © (20.05.03 16:05)
не помню уж за давностью лет - но там что-то на тему оптимизации перемещений. из серии - как перевезти козу, волка и капусту.
вопрос парниша ставит некорректно.

← →
DAC © (2003-05-20 16:15) [5]

Я тоже был бы признателен за исходники. :-)))) Но...
На сегодняшний день не существует полиномиального решения задачи коммивояжера. Решишь её - решишь основную проблему теории сложности, тем самым произведешь мировую компьютерную революцию. После этого можешь смело требовать Нобелевскую премию, премию Тьюринга и т.д

← →
pasha_golub © (2003-05-20 16:25) [6]

>DAC
Совершенно верно, но все-таки приближенные алгоритмы существуют. Искать надо в теории графов.
ЗЫ. Мне интересно, а откуда появиласть надобность в решении данной задачи у автора вопроса?

← →
Думкин © (2003-05-20 16:32) [7]

Нобеля не дадут - если только под экономику замутить.

← →
Думкин © (2003-05-20 16:34) [8]

> pasha_golub © (20.05.03 16:25)
> ЗЫ. Мне интересно, а откуда появиласть надобность в решении
> данной задачи у автора вопроса?

Дык. Что непонятного: Образование: незаконченное высшее

← →
Mike Kouzmine © (2003-05-20 16:44) [9]

Выучи пролог. Там это проще решается.

← →
Soft © (2003-05-20 17:17) [10]

>>PelMen © (20.05.03 15:25)
>>Здравствуйте, люди добрые!
>>Подскажите пожалуйста где можно взять решенный subj?
>>Буду очень признателен за исходники :)

Кинь мне письмо с напоминанием, пришлю исходники процедурки построения матрицы маршрутов. Сложность 3*N^2 (тоесть количество итераций).

Это модифицированный алгоритм Дейкстры, когда сделал сам офигел, все настолько просто, что уже сам не понимаю, как это работает:)

← →
DAC © (2003-05-20 17:19) [11]

> pasha_golub © (20.05.03 16:25)
> но все-таки приближенные алгоритмы существуют

Существуют и точные, но неполиномиальные. Простейший - полный перебор. :-))) Может автору это вполне подойдет, если он делает расчеты на очень небольшом количестве вершин.

> Думкин © (20.05.03 16:32)
> Нобеля не дадут - если только под экономику замутить.

Ну почему же? Сейчас очень много актуальных NP-задач. И решение задачи коммивояжера решит их все. Это действительно будет событием, сравнимым с изобретением компьютера или созданием летательных аппаратов.

← →
Soft © (2003-05-20 17:56) [12]

>>DAC © (20.05.03 17:19)
>>Ну почему же? Сейчас очень много актуальных NP-задач. И решение задачи коммивояжера решит их все. Это действительно будет событием, сравнимым с изобретением компьютера или созданием летательных аппаратов.

Квантовый компьютер вам поможет, сер:)

← →
Думкин © (2003-05-21 06:44) [13]

> DAC © (20.05.03 17:19)

Я к тому что математиков Нобель обломил. ТОлько под экономику и косят - Канторович например.

← →
Дмитрий К.К. © (2003-05-21 06:48) [14]

У Нобеля зуб на математиков, как у Думкина на Собчака... или наоборот...

← →
Думкин © (2003-05-21 07:11) [15]

> Дмитрий К.К. © (21.05.03 06:48)

У меня на Собчака зуба нет из-за одной его фразы...
"Политика не грязное дело - грязной ее делают грязные люди".
Так что зря. :-)
А про Нобеля - разные версии есть.

Жена его спала с математиком... какие еще версии?

> Дмитрий К.К. © (21.05.03 07:28)

Еся такая - но я слышал, что невесту у него математик увел.
Но есть и иная. Туповат он был. И считал, что практики и есть соль мира - потому математику и математиков - не любил. Обычное дело. :-)

Собственно, мне не нужно ничего оригинального :)
Вполне подойдут существующие методы.
Для курсача надо хотя бы пару :)
Просто я, наверно, совсем глупый: смотрю в книгу на метод ветвей и границ и ничче не понимаю :)

unit LinkTo;

interface
uses math;

type inttype=integer;

type Tway=record
port:inttype;//следующая вершина маршрута
time:inttype;//время достижения маршрута
end;

type TLinkMatrix=record
size:inttype;//размерность квадратной матрицы
links:array of array of inttype;//вес каждой связи квадратной матрицы
//обычным числом выставляется вес связи
//если связи нет, то ставится 0
//пока не работает со значением связи MaxInt
//пока не работает с "разорванными графами"
end;

type TWaymatrix=record
size:inttype;//размерность квадратной матрицы
Ways:array of array of Tway;//параметры пути
//строки матрицы обозначают вершину из которой добираемся
//до нужной нам вершины
//в стобцах находятся вершины достижимости
//каждая ячейка матрицы содержит два поля
//port обозначает следующую верщину пути
//time время всего пути
//например на пересечении строка-столбец[2,5]
//значение port=4 time=6
//это означает, сдедующая вершина пути 4
//общее время пути от 2 до 5 вершины 6 тактов
end;

function PPPAll(var LinkMatrix:TLinkMatrix):TWaymatrix;

implementation

function PPPAll(var LinkMatrix:TLinkMatrix):TWaymatrix;
var
X:array of inttype;
Xpoint:array of inttype;
Xm: array of boolean; { Mask of X}
P,i,j,n: inttype; { N }
Waymatrix:TWaymatrix;
begin
SetLength(Xm,LinkMatrix.size+1);
SetLength(X,LinkMatrix.size+1);
SetLength(Xpoint,LinkMatrix.size+1);
Waymatrix.Size:=LinkMatrix.Size;
SetLength(Waymatrix.Ways,Waymatrix.Size+1,Waymatrix.Size+1);

for j:=1 to LinkMatrix.size do
begin

for i:=1 to LinkMatrix.size do
begin
Xm[i]:=False;
X[i]:=MaxInt;
Xpoint[i]:=0;
end;

P:=j;
Xm[P]:=True; X[P]:=0; { step 1}

repeat
for i:=1 to LinkMatrix.size do if LinkMatrix.links[P, i]<>0 then
begin
if (X[i]>(X[P]+LinkMatrix.links[P, i])) then
Xpoint[i]:=P;
X[i]:=min(X[i], X[P]+LinkMatrix.links[P, i]); {step2 }
end;
for i:=1 to LinkMatrix.size do if not Xm[i] then P:=i;
for i:=1 to LinkMatrix.size do
if (not Xm[i]) and (X[i]<=X[P]) then P:=i; { step 4 }
if Xm[P] then P:=0
else Xm[P]:=True; { step 3}
until P=0;

for i:=1 to LinkMatrix.size do
if (X[i]<>MaxInt) and (X[i]<>0) then
begin
n:=i;
repeat
if (Xpoint[n]=j) and
(X[n]<>MaxInt)then
begin
Waymatrix.Ways[j,i].port:=n;
Waymatrix.Ways[j,i].time:=X[i];
end;
if (Xpoint[n]<>j) then
n:=Xpoint[n];
if (Xpoint[n]=j) and (X[n]<>MaxInt)then
begin
Waymatrix.Ways[j,i].port:=n;
Waymatrix.Ways[j,i].time:=X[i];
end;
until (Xpoint[n]=j)
end;

end;

SetLength(Xm,0);
SetLength(X,0);
SetLength(Xpoint,0);
Xm:=nil;
Xpoint:=nil;
X:=nil;

PPPAll:=Waymatrix;
end;

end.

ЗЫ
Только сейчас до меня дошло, что задача коммивояжжера, это несколько другое:) Алгоритм, что я дал, на самом деле строит матрицу кратчайших маршрутов внутри системы. Для задачи придется немного доделать.

2 Soft
Задача коммивояжера (в моей трактовке :-) Кратчайшим маршрутом обойти все узлы, не побывав при этом ни в одном дважды.

Задача эта решаема если граф допускает планарную укладку. (Извините если напутал, 2 года назад учил.)

А вот это утверждение вызывает у меня сомнения: Нужно чтобы коммивояжер возвращался в исходный узел али нет?

Задача коммивояжера Найти похожие ветки