Problema do carteiro chinês: encontrando as melhores conexões entre nós de grau ímpar

Estou escrevendo um programa, resolvendo o problema do carteiro chinês (também conhecido como problema de inspeção de rota) em um draph não direcionado e atualmente enfrentando o problema para encontrar as melhores arestas adicionais para conectar os nós em graus ímpares, para que eu possa calcular um circuito euleriano.

Pode haver (considerando o tamanho do gráfico que deseja ser resolvido) uma enorme combinação de arestas que precisam ser calculadas e avaliadas.

Como um exemplo, existem os nós estranho graus . As melhores combinações podem ser: $A, B, C, D, E, F, G, H$

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

onde significa "borda entre o nó e o nó ". $AB$ $A$ $B$

Portanto, minha pergunta é: existe um algoritmo conhecido para resolver esse problema em uma complexidade melhor que a força bruta pura (calculando e avaliando todos eles)?

€: Após algum esforço de pesquisa, encontrei este artigo, falando sobre o "algoritmo de correspondência de tamanho mínimo de Edmonds", mas não consigo encontrar nenhum pseudo-código ou descrição de alunos desse algoritmo (ou pelo menos não os reconheço, como o Google oferece muitos hits e algoritmos de correspondência por J. Edmonds)

algorithms graph-theory graphs Sim
fonte

O (n^{3})

$O(n^3)$

Eu sei, mas ainda estou curioso para saber como fazer isso.

Sim #

Estas notas de aula tratar o problema do carteiro chinês: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf

Alex ten Brink

Sim, estou interessado no seu software, pois estou enfrentando um problema de mapeamento: help.openstreetmap.org/questions/13197/… Boa sorte com seu projeto. pm no pmbooks pontocom

tente o artigo que vinculei e descreve um algoritmo de correspondência de tamanho mínimo, mas devido à minha falta de experiência e à falta de pseudo-código, infelizmente não consegui implementá-lo.

Sim

Respostas:

Conforme observado nos comentários, a Wikipedia reduz a inspeção de rota para correspondências de peso mínimo . Vladimir Kolmogorov publicou uma rápida implementação da versão ponderada do algoritmo de flor de Edmonds, em C ++ [1].

[1] V. Kolmogorov, Blossom V: Uma nova implementação de um algoritmo de correspondência perfeita de custo mínimo . Computação em Programação Matemática , 1 (1): 43–67, 2009.

David Richerby
fonte

E não vamos chamá-lo de "Problema do Carteiro Chinês". O único elo com a China é que ele foi introduzido por Mei-Ko Kwan e sua nacionalidade é irrelevante para o problema. Nomear "chinês" sugere que a coisa mais significativa sobre ele é sua origem étnica. Por exemplo, não nos referimos ao algoritmo conhecido para calcular os caminhos mais curtos dos gráficos como "o algoritmo holandês" ou, pior ainda, "o algoritmo do homem branco". (Sim, eu opor-se "teorema chinês do resto", pela mesma razão, mas esse cavalo aparafusado muito tempo atrás.)

David Richerby