Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Задача коммивояжера где найти алгоритм
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
2D_UFO
Guest
 
Сообщений: n/a
По умолчанию Задача коммивояжера где найти алгоритм - 28.02.2004, 01:30

Люди помогите нужна прога на с==(или хотя бы алгоритм) насчет задачи коммивояжера.
ПЛИЗЗ
срочно!
Ответить с цитированием
  (#2 (permalink)) Старый
Shunix Shunix вне форума
Member
 
Сообщений: 1,355
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.06.2002
По умолчанию 28.02.2004, 12:48

http://alglib.manual.ru/combinatorial/salesman.php
Ответить с цитированием
  (#3 (permalink)) Старый
marlen marlen вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 29.03.2005
По умолчанию 29.03.2005, 14:55

Цитата:
Originally posted by Shunix
[b]http://alglib.manual.ru/combinatorial/salesman.php
А если не перебором, может у кого-нибудь заволялась программка про коммивояжеру! желательно Delphi или Paskal!!! Заранее всем спасибо!!!
Ответить с цитированием
  (#4 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,959
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 03.04.2005, 22:09

Цитата:
А если не перебором
Так а другого способа в природе не существует. Только переборы бывают разные, ну и эвристики - тоже используют разные. Всё зависит от природы самого графа.
Ответить с цитированием
  (#5 (permalink)) Старый
marlen marlen вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 29.03.2005
По умолчанию 04.04.2005, 23:29

Цитата:
Originally posted by Винитарх
[b]<div class='quotetop'>Цитата
Цитата:
А если не перебором
Так а другого способа в природе не существует. Только переборы бывают разные, ну и эвристики - тоже используют разные. Всё зависит от природы самого графа.[/quote]
т.е. если решать метод ветвей и границ, то могут некоторые задачи не решиться(случай большого числа корней не рассматривать!!!).
А то я сделала этим методом, и если рассматривать случай: городов>5 и все стороны одинаковые, то программа не работает!!! этот метод предусматривает такие проблеммы???
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,959
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 06.04.2005, 11:11

Цитата:
т.е. если решать метод ветвей и границ, то могут некоторые задачи не решиться
Если количество вершин графа невелико (~ до 17-19), то задача решится.

Цитата:
А то я сделала этим методом, и если рассматривать случай: городов>5 и все стороны одинаковые, то программа не работает!!! этот метод предусматривает такие проблеммы???
1. Это вина не метода, а программиста. Вы уж меня извините, но где-то у Вас в алгоритме промашка вышла.
2. Если в прогу ввести эвристику, что мол веса связей у графа - целочисленные (и положительные), то прога в Вашем случае мгновенно (за один проход) поймёт, что любой цикл - минимальный, и сразу выдаст решение.
3. Если в прогу ввести эвристику об одинаковости всех путей (проверяется априорно), то прога также, найдя первый попавшийся цикл, выдаст решение.
Ответить с цитированием
  (#7 (permalink)) Старый
yureckor yureckor вне форума
Member
 
Сообщений: 462
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.03.2004
По умолчанию 06.04.2005, 14:38

Я вот только не понимаю зачем для нахождения кратчайшего пути в графе делать перебор всех вариантов.
Ответить с цитированием
  (#8 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,959
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 06.04.2005, 18:36

Ищется не путь, а цикл, причём минимальный. А это, извините, NP-трудная задача, не имеющая ни аналитического решения, ни алгоритма, дающего точное решение.
Ответить с цитированием
  (#9 (permalink)) Старый
yureckor yureckor вне форума
Member
 
Сообщений: 462
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.03.2004
По умолчанию 07.04.2005, 09:24

>т.е. побывать во всех точках и вернуться назад?
Попробую чего-нибудь придумать.
Ответить с цитированием
  (#10 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 18.04.2005, 19:21

NP-сложная, да шо вы такое говорите а венгерский алгоритм? а хотя бы симплекс метод? это задача дискретной оптимизации по факту и линейного программирования по сути, а вовсе не теории графов
Ответить с цитированием
  (#11 (permalink)) Старый
Scorpion1105 Scorpion1105 вне форума
Member
 
Сообщений: 74
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.12.2004
По умолчанию 24.04.2005, 22:21

Если ещё нужно, прошу сюда: http://www.hardforum.ru/t58611
Ответить с цитированием
  (#12 (permalink)) Старый
STORM STORM вне форума
Member
 
Сообщений: 26
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2005
По умолчанию 30.04.2005, 02:07

Вот отлично работающий алгоритм, может быть пригодиться:
ЗАДАЧА КОММИВОЯЖЕРА
Пусть заданы конечное множество C городов, целые положительные расстояния A(c1,c2) для каждой пары городов c1,c2.
Требуется найти маршрут минимальной длины, проходящий через все города ровно один раз и возвращающийся в исходный пункт.
Это — задача на минимум. Карта представляется графом, ребрам которого приписаны веса. Из всех гамильтоновых циклов (это полный граф, в нем существуют гамильтоновы циклы) в этом графе нужно выбрать цикл минимальной длины. Длина определяется естественным образом — как сумма расстояний между городами, входящими в маршрут. Можно поступить просто — сгенерировать алгоритмом с возвратом все циклы и среди них выбрать минимальный. Однако немного изменив общую схему алгоритма с возвратом, можно добиться того, что возвраты будут происходить значительно раньше, и решение будет найдено быстрее.
Итак, задача на минимум — среди всех допустимых объектов ищется минимальный.
Каждому решению( и полному, и частичному ) приписывается стоимость — ее еще называют целевой функцией. Будем обозначать ее cost.
При продолжении решения стоимость может только увеличиваться:
cost(< X(1), … , X(i-1) >)<= cost(< X(1), … , X(i-1), X(i)>).
Для задачи коммивояжера целевой функцией, удовлетворяющей такому условию, будет
cost(< X(1), … , X(i)>)=A(X(1), X(2))+…+ A(X(i-1), X(i)).
Очевидно, что ее значение будет увеличиваться при удлинении маршрута.
Идея алгоритма:
1. Находим первое решение и запоминаем его стоимость в OptCost.
2. Пусть < X(1), … , X(i)> — текущее частичное решение. Прежде, чем пытаться продолжать его дальше, проверим, имеет ли смысл это делать. Если cost(< X(1), … , X(i)>) >= OptCost,
то любое его продолжение будет заведомо больше текущего минимального решения. Производим возврат к предыдущему частичному решению < X(1), … , X(i-1)>.
Таким образом, произведя «досрочный» возврат, мы избавляем себя от генерации всех заведомо неоптимальных продолжений, т.е. обрубаем целое поддерево на дереве поиска.
АЛГОРИТМ. {Нахождение гамильтоновых цикла min длины}
Данные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], матрица весов A[u,v].
Результаты: Печать min гамильтонова цикла.
Переменные ЗАПИСЬ, X, cost, OptX, OptCost, DOP — глобальные.

Код:
1  procedure KOMMI(i);
2  begin
3   for y Є ЗАПИСЬ[X[i-1]] do
4   if cost + A[X[i-1], y] < OptCost then
5    if (i = n+1) AND (y = k) then
6     begin OptX:=X; OptCost:= cost + A[X[i-1],y] end
7    else if DOP[y] then
8     begin 
9      X[i]:=y; DOP[y]:= ложь;
10     cost:=cost + A[X[i-1], y];
11     KOMMI(i+1);
11     DOP[y]:= истина; cost:=cost — A[X[i-1], y];
12    end;
13 end; {KOMMI }


1 begin { основная программа }
2  for v Є V do DOP[v]:=истина;
3  X[1]:=k; { k — произвольная }
4  DOP[k]:= ложь;
5  cost:=0; OptCost:= +бесконечность(большое число);;
6  KOMMI(2);
7 end.
ЗАПИСЬ[x] - списки инцедентности для данного графа.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,959
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 30.04.2005, 11:24

tokito пишет:
Цитата:
NP-сложная, да шо вы такое говорите а венгерский алгоритм? а хотя бы симплекс метод? это задача дискретной оптимизации по факту и линейного программирования по сути, а вовсе не теории графов
tokito! Вы очень самоуверенный человек! Свою самоуверенность Вы показали ещё в задаче на переливание:
http://www.hardforum.ru/t54877
Я рад за Вас, что Вы знаете методы мат.программирования. Но к сожалению, они работают не везде и не всегда. Класс NP-полных задач довольно велик (несколько тысяч), и задача коммивояжера - это характерный пример из этого класса. Не верите мне, обратитесь к людям, которым Вы доверяете.
Эгервари я уважаю как человека, но его алгоритм - безнадёга для NP-задач. Читайте учебники по дискретной математике.

STORM пишет:
Цитата:
Вот отлично работающий алгоритм, может быть пригодиться:
ЗАДАЧА КОММИВОЯЖЕРА
STORM! Вы открыли для себя известный метод ветвей и границ в его простейшем варианте. Молодец, так держать!
Применение метода ветвей и границ оправдано только на графах до ~17 вершин, и об этом я здесь уже говорил.

МЕТОДЫ МАТ.ПРОГРАММИРОВАНИЯ НЕ СПОСОБНЫ НАХОДИТЬ ОПТИМАЛЬНОЕ РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА, ОНИ НАХОДЯТ ЛИШЬ СУБОПТИМАЛЬНОЕ РЕШЕНИЕ.
Ответить с цитированием
  (#14 (permalink)) Старый
tokito tokito вне форума
Member
 
Сообщений: 477
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 01.10.2004
По умолчанию 06.05.2005, 10:32

признаю что я лох - я перепутал задачу комивояжора с транспортной задачей

однако откуда оценочка числа задач класса NP-полных энто бред
Ответить с цитированием
  (#15 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,959
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 06.05.2005, 14:32

Цитата:
однако откуда оценочка числа задач класса NP-полных, энто бред
Списки NP-полных задач приведены во многих источниках. Например: Касьянов, Евстигнеев, "Графы в программировании". Там сорок страниц отведено под простое перечисление одних только математических формулировок NP-полных задач. А также приведён обширный список литературы о NP-полных задачах. Каждая математическая постановка NP-задачи для каждой прикладной области имеет свои модификации: для радиосвязи - одно, для локации - другое, для шифрования - третье и т.д.
Так что "энто не бред".
Легко давать советы направо и налево. Трудно становиться, когда надо отвечать за результаты своих советов.
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача Прима-Краскала (“жадный” алгоритм) Dem Prolog 13 21.03.2012 22:51
Задача коммивояжера. Метод ветвей и границ Dmitry-PZ C++ Builder 4 11.11.2010 22:05
Задача коммивояжера luds Prolog 21 19.12.2009 20:29
Задача коммивояжера метод ветвей и границ azarov00@mail.ru Вопросы начинающих программистов 1 19.09.2008 12:24
Модификация задача коммивояжера Scorpion1105 Алгоритмы 3 08.05.2008 15:07
Где найти алгоритм для remOdd felixb Алгоритмы 2 18.12.2007 00:28
Задача Прима-Крскала (жадный алгоритм) mickey Prolog 2 22.10.2007 13:19
МД5 где найти алгоритм Aram Алгоритмы 3 23.02.2007 19:41
Интересная задача как создать алгоритм данных на вычисление ЕкатеринаАК Алгоритмы 8 06.12.2005 12:07
Задача почтальона и коммивояжера! lakygirla Visual Basic 0 24.05.2005 20:54
Где можно найти решение и объеснение задачи коммивояжера MTony Вопросы начинающих программистов 7 13.02.2005 06:32
Алгоритм тетриса где его найти Форсаж Алгоритмы 2 17.06.2003 18:41



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов