![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 17.12.2006
Сообщений: 5
|
![]()
Уже долгое время пытаюсь решить программу, реализующую алгоритм китайского почтальона, результат неустраивает...
Если у кого-то есть уже готовый рабочий алгоритм, плз.... покажите мне его... хочу взглянуть... |
![]() |
![]() |
![]() |
#2 |
Андрей
Форумчанин
Регистрация: 21.11.2006
Сообщений: 457
|
![]()
А ты хотя бы в общих чертах опиши это алгоритм. А то лично я, например, впервые об этом слышу...
ICQ: 5311314
[SIGPIC][/SIGPIC] |
![]() |
![]() |
![]() |
#3 |
Регистрация: 17.12.2006
Сообщений: 5
|
![]()
Это алгоритм обхода графа. В нем необходимо обойти все ребра, у которых есть стоимость, и вернуться в начальную вершину, причем полная стоимость после обхода должна быть минимальной...
вот такая весчь |
![]() |
![]() |
![]() |
#4 |
Александр
Администратор
Регистрация: 28.10.2006
Сообщений: 17,530
|
![]()
Реализация, то простая. найти все варианты и выбрать один из наименьших.
|
![]() |
![]() |
![]() |
#5 |
Регистрация: 17.12.2006
Сообщений: 5
|
![]()
Если б все было так просто.
Смысл в том, что необходимо найти пути наименьшей стоимости, по которым можно проходить дважды, вот как раз в этом случае у меня начинаются зависания... зацикливается алгоритм... |
![]() |
![]() |
![]() |
#6 |
Владимир М.
Участник клуба
Регистрация: 30.10.2006
Сообщений: 1,289
|
![]()
это 'задача коммивояжора'.
для больших графов полный перебор - практически неосуществим. (другого) готового алгоритма у меня нету ...
Берегите друг друга!
|
![]() |
![]() |
![]() |
#7 |
Регистрация: 17.12.2006
Сообщений: 5
|
![]()
задача комивояжера у меня давно готова)... тут мы проходим по вершинам, а не по ребрам
В нашем случае (о китайце) необходимо пройти по всем ребрам... я находил минимальные ребра, но в участках графа, где встречаются циклы, у меня все зацикливается, вот я ищу решение этой проблемы, или же другую идею... //Как всегда... Есть кнопка редактировать ![]() Последний раз редактировалось SuperVisor; 17.12.2006 в 17:41. Причина: Объединение |
![]() |
![]() |
![]() |
#8 |
Владимир М.
Участник клуба
Регистрация: 30.10.2006
Сообщений: 1,289
|
![]()
про коммивояжора - Ты прав, я недосматрел
![]() НО по каким всем ребрам ? зачем тогда думать про минимальные ?
Берегите друг друга!
|
![]() |
![]() |
![]() |
#9 |
Регистрация: 17.12.2006
Сообщений: 5
|
![]()
Китайцы народ хитрый, они чтобы лишнего не делать, выбирают минимальный путь, так и тут, общий пройденный путь должен быть минимальным, поэтому сучше повторно походить по коротким(с минимальной стоимостью) ребрам, а не по длинным(с максимальной стоимостью).
|
![]() |
![]() |