Форум: "Потрепаться";
Текущий архив: 2003.06.09;
Скачать: [xml.tar.bz2];
ВнизЗадача коммивояжера Найти похожие ветки
← →
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)
У меня на Собчака зуба нет из-за одной его фразы...
"Политика не грязное дело - грязной ее делают грязные люди".
Так что зря. :-)
А про Нобеля - разные версии есть.
← →
Дмитрий К.К. (2003-05-21 07:28) [16]Жена его спала с математиком... какие еще версии?
← →
Думкин (2003-05-21 07:39) [17]
> Дмитрий К.К. © (21.05.03 07:28)
Еся такая - но я слышал, что невесту у него математик увел.
Но есть и иная. Туповат он был. И считал, что практики и есть соль мира - потому математику и математиков - не любил. Обычное дело. :-)
← →
PelMen (2003-05-21 14:15) [18]Собственно, мне не нужно ничего оригинального :)
Вполне подойдут существующие методы.
Для курсача надо хотя бы пару :)
Просто я, наверно, совсем глупый: смотрю в книгу на метод ветвей и границ и ничче не понимаю :)
← →
Soft (2003-05-21 16:53) [19]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.
← →
Soft (2003-05-21 17:02) [20]ЗЫ
Только сейчас до меня дошло, что задача коммивояжжера, это несколько другое:) Алгоритм, что я дал, на самом деле строит матрицу кратчайших маршрутов внутри системы. Для задачи придется немного доделать.
← →
pasha_golub (2003-05-21 17:17) [21]2 Soft
Задача коммивояжера (в моей трактовке :-) Кратчайшим маршрутом обойти все узлы, не побывав при этом ни в одном дважды.
Задача эта решаема если граф допускает планарную укладку. (Извините если напутал, 2 года назад учил.)
А вот это утверждение вызывает у меня сомнения: Нужно чтобы коммивояжер возвращался в исходный узел али нет?
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.06.09;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.009 c