Китайцы наступают!!!

[Nox]

Уже долгое время пытаюсь решить программу, реализующую алгоритм китайского почтальона, результат неустраивает...
Если у кого-то есть уже готовый рабочий алгоритм, плз.... покажите мне его... хочу взглянуть...

[AVer]

А ты хотя бы в общих чертах опиши это алгоритм. А то лично я, например, впервые об этом слышу...

[Nox]

Это алгоритм обхода графа. В нем необходимо обойти все ребра, у которых есть стоимость, и вернуться в начальную вершину, причем полная стоимость после обхода должна быть минимальной...
вот такая весчь

[Alar]

Реализация, то простая. найти все варианты и выбрать один из наименьших.

[Nox]

Если б все было так просто.
Смысл в том, что необходимо найти пути наименьшей стоимости, по которым можно проходить дважды, вот как раз в этом случае у меня начинаются зависания... зацикливается алгоритм...

[Virtson]

это 'задача коммивояжора'.
для больших графов полный перебор - практически неосуществим.

(другого) готового алгоритма у меня нету ...

[Nox]

задача комивояжера у меня давно готова)... тут мы проходим по вершинам, а не по ребрам

В нашем случае (о китайце) необходимо пройти по всем ребрам... я находил минимальные ребра, но в участках графа, где встречаются циклы, у меня все зацикливается, вот я ищу решение этой проблемы, или же другую идею...

//Как всегда... Есть кнопка редактировать

[Virtson]

про коммивояжора - Ты прав, я недосматрел

НО
по каким всем ребрам ?
зачем тогда думать про минимальные ?

[Nox]

Сообщение от Virtson

про коммивояжора - Ты прав, я недосматрел

НО
по каким всем ребрам ?
зачем тогда думать про минимальные ?

Китайцы народ хитрый, они чтобы лишнего не делать, выбирают минимальный путь, так и тут, общий пройденный путь должен быть минимальным, поэтому сучше повторно походить по коротким(с минимальной стоимостью) ребрам, а не по длинным(с максимальной стоимостью).