Custo mínimo DiDraph fortemente conectado

StackOverflow https://stackoverflow.com/questions/1536067

Pergunta

Eu tenho uma díadera que está fortemente conectada (ou seja, há um caminho de I a J e J a I para cada par de nós (i, j) no gráfico G). Desejo encontrar um gráfico fortemente conectado deste gráfico, de modo que a soma de todas as arestas seja a menor.

Para, de maneira diferente, preciso me livrar das bordas de tal maneira que, depois de removê -las, o gráfico ainda estará fortemente conectado e com menor custo para a soma das bordas.

Eu acho que é um problema difícil do NP. Estou procurando uma solução ideal, não a aproximação, para um pequeno conjunto de dados como 20 nós.

Editar

Uma descrição mais geral: dada uma uva g (v, e), encontre um gráfico G '(v, e'), de modo que, se existir um caminho de V1 a V2 em G, também existe um caminho entre V1 e V2 em G 'e a soma de cada EI em e' é a menos possível. Portanto, é semelhante a encontrar um gráfico equivalente mínimo, apenas aqui queremos minimizar a soma dos pesos da borda, em vez da soma das bordas.

Editar:

Minha abordagem até agora: pensei em resolvê -la usando TSP com várias visitas, mas não está correta. Meu objetivo aqui é cobrir cada cidade, mas usando um caminho de custo mínimo. Então, é mais como o problema do conjunto de capa, eu acho, mas não tenho exatamente certeza. Sou obrigado a cobrir cada cidade usando caminhos cujo custo total é mínimo; portanto, visitar os caminhos já visitados várias vezes não aumenta o custo.

Foi útil?

Solução

Seu problema é conhecido como Gráfico mínimo de submet (DI) (MSSS) ou, de maneira mais geral, o gráfico mínimo de spanning sub (DI) e é NP-Hard de fato. Veja também outro livro: Página 501 e Página 480.

Começaria com a remoção de todas as arestas que não satisfazem a desigualdade do triângulo -você pode remover a borda a -> c se estiver a -> b -> c for mais barato. Isso me lembra o TSP, mas não sei se isso leva a algum lugar.

Minha resposta anterior foi usar o Algoritmo Chu-Liu/Edmonds que resolve Arborborcença problema; Como Kazoom e Shreevatsar apontaram, isso não ajuda.

Outras dicas

Eu tentaria isso de uma maneira dinâmica de programação.

0- Coloque o gráfico em uma lista

1- Faça uma lista de novos subgrafos de cada gráfico na lista anterior, onde você remove uma borda diferente para cada um dos novos subgrafos

2- Remova duplicatas da nova lista

3- Remova todos os gráficos da nova lista que não estão fortemente conectados

4- Compare o melhor gráfico da nova lista com o melhor, se melhor, defina um novo melhor atual

5- Se a nova lista estiver vazia, o melhor atual é a solução, caso contrário, recorrer/loop/goto 1

Em Lisp, talvez pudesse ficar assim:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

As definições de strongly-connected, list-subgraphs-1, digraph-equal, best, e better são deixados como um exercício para o leitor.

Este problema é equivalente ao problema descrito aqui: http://www.facebook.com/careers/puzzles.php?puzzle_id=1

Poucas idéias que me ajudaram a resolver o famoso quebra -cabeça do FaceBull:

Etapa de pré -processamento:

  1. Poda: remova todas as bordas AB se houver mais barato ou tendo o mesmo custo Caminho, por exemplo: ACB.

  2. Decomposição de gráficos: você pode resolver subproblemas se o gráfico tiver pontos de articulação

  3. Mesclar vértices em um vértice virtual se houver apenas uma borda de saída.

Etapa de cálculo:

  1. Obtenha solução aproximada usando o TSP direcionado com visitas repetidas. Use o Floyd Warshall e, em seguida, resolva o problema da atribuição o (n^3) usando o método húngaro. Se obtivemos um ciclo uma vez - é a solução TSP direcionada, se não - use o ramo e o TSP ligado. Depois disso, temos o valor limite superior - o ciclo do custo mínimo.

  2. Solução exata - ramificação e abordagem ligada. Removemos os vértices do ciclo mais curto e tentamos construir um gráfico fortemente conectado com menos custo do que o limite superior.

Isso é tudo, pessoal. Se você quiser testar suas soluções - tente aqui: http://codercharts.com/puzzle/caribbean-salesman

Parece que você quer usar o Algoritmo Dijkstra

Parece que o que você basicamente deseja é uma solução ideal para o Salesman de Viajantes, onde é permitido que os nós sejam visitados mais de uma vez.

Editar:

Hum. Você poderia resolver isso essencialmente iterando sobre cada nó i e depois fazendo uma árvore de abrangência mínima de todas as bordas apontando para aquele nó i, sincronizado com outra árvore mínima de abrangência de todas as bordas apontando um jeito desse nó?

Uma aproximação 2 para o subgrafileiro mínimo fortemente conectado é obtido tomando um sindicato de um ramificação mínimo e o mínimo de ramos, ambos enraizados no mesmo (mas arbitrário) vértice.

Um ramificação externa, também conhecido como arborborcença, é uma árvore direcionada enraizada em um único vértice que abrange todos os vértices. Uma ramificação é a mesma com bordas reversas. Estes podem ser encontrados por Algoritmo de Edmonds em tempo O (VE), e há acelerações para O (e log (v)) (Veja o Página da wiki). Existe até um Implementação de código aberto.

A referência original para o resultado de 2 abordagem é o Papel de Jaja e Frederickson, mas o artigo não é acessível livremente.

Existe até uma aproximação de 3/2 por Adrian Vetta (Pdf), mas mais complicado do que o acima.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top