Проблема китайского почтальона: поиск наилучших связей между узлами нечетной степени

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

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

В качестве примера есть нечетные степени узлы . Лучшие комбинации могут быть: $A, B, C, D, E, F, G, H$

, , , $AB$ $CD$ $EF$ $GH$
, , , $AC$ $BD$ $EH$ $FG$
, , , $AD$ $BC$ $EG$ $FH$
.... $AE$

где означает «ребро между узлом и узлом ». $AB$ $A$ $B$

Поэтому мой вопрос: существует ли известный алгоритм, который решает эту проблему сложнее, чем чисто грубая сила (вычисляя и оценивая их все)?

€: После некоторых исследований я нашел эту статью, говоря о «алгоритме соответствия минимальной длины Эдмондса», но не могу найти псевдокод или описания этого алгоритма для учащихся (или, по крайней мере, я их не распознаю, как Google предлагает множество совпадений алгоритмов сопоставления Дж. Эдмондса)

algorithms graph-theory graphs Сим
источник

Википедия утверждает, что для задачи китайского почтальона существует алгоритм

O (n^{3})

$O(n^3)$ .

hugomg

Я знаю, но мне все еще интересно узнать, как это сделать.

Сим

Эти лекционные заметки посвящены

Алекс тен Бринк

Сим, я заинтересован в твоем программном обеспечении, так как столкнулся с проблемой сопоставления: help.openstreetmap.org/questions/13197/… Удачи в твоем проекте. вечера в pmbooks точка ком

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

Сим

Ответы:

Как отмечается в комментариях, Википедия дает сокращение от проверки маршрута до сопоставлений с минимальным весом . Владимир Колмогоров опубликовал быструю реализацию взвешенной версии алгоритма цветения Эдмондса в C ++ [1].

[1] В. Колмогоров, Блоссом В. Новая реализация алгоритма идеального согласования с минимальной стоимостью . Математическое программирование вычислений , 1 (1): 43–67, 2009.

Дэвид Ричерби
источник

И давайте не будем называть это «проблемой китайского почтальона». Единственная связь с Китаем заключается в том, что он был введен Мей-Ко Кваном, и его гражданство не имеет отношения к проблеме. Называя его «китаец», можно предположить, что самым важным в нем является его этническое происхождение. Мы, например, не называем известный алгоритм вычисления кратчайших путей в графах как «голландский алгоритм» или, что еще хуже, «алгоритм белого человека». (Да, я возражаю против "китайской теоремы об остатках" по той же причине, но эта лошадь слишком долго

болталась