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