Compactar gráfico matemático

Question

Eu quero desenhar um gráfico que será algo como isto: texto alt http://img25.imageshack.us/img25/9786/problemo.png

Você pode ver 3 pathes: A, B & C. Como posso alterar a posição dos elementos (1,2,3 ..., 9) para fazer longo do caminho mais curto possível? Quero dizer estas linhas devem ser tão curtos quanto possível.

Estou muito interessado nele becouse eu estou de desenhar um gráfico com a pergunta, algum tipo de infográfico como 'siga as linhas de saber a resposta'. Eu sei que é um pouco sobre a teoria dos grafos ... por isso, se a sua muito difícil, você sabe se existe algum programa para linux para coisas compacto como este?

Por exemplo programa deve funcionar assim: Na entrada deve obter 3 pathes

a='1,5,7,8,4,2,6'
b='4,2,3,6,9,8,5'
c='7,9'

E na produção in deve ser coordenadas deste elementos.

Answer 1

Sempre que tenho um problema de otimização que é difícil de resolver, penso em algoritmos genéticos . Minha solução abaixo assume que você está familiarizado com GA (não muito difícil de implementar it yourself)
Olhando para o gráfico de exemplo que você deu, vamos supor que os nós serão colocados em uma grade NxN (inteiro posições), seguida de codificar o genomas , considere o seguinte esquema:

00101 00100 11010 11110 11000     
  A     B     C     D     E

onde cada parte codifica a posição na grelha (em binário) dos nós (nessa ordem). O comprimento de cada parte depende do tamanho da grelha (comprimento = ceil (log2 (N * N))).
A grade é numerada linha por linha, da esquerda para a direita.

Assim, como um exemplo, para um gráfico completo com 4 nódulos (A, B, C, D) e uma grade de 3x3, a cadeia:

0011 0001 0101 1000    =   3  1  5  8 
 A    B    C    D          A  B  C  D

representa o seguinte esquema:

. B .       00  01  02
A . C       03  04  05
. . D       06  07  08

Em seguida, projetar o cruzamento operador como de costume (de um ou dois pontos de cruzamento), e mutação , bem como (pouco uma aleta de forma aleatória). Nós apenas temos que ter certeza de que a qualquer momento, só temos posições válidas dentro da grade.
Finalmente, o função de fitness será alguma função das distâncias entre os nós no caminho (soma de múltiplos caminhos), o que penaliza caminhos longos (como um problema de minimização). Um exemplo é tomar a cidade-block distância entre os nós.
O resto do método é o algoritmo genético padrão (inicialização, a avaliação, a selecção, a reprodução, terminação).

Exemplo Para ilustrar, considere o layout anterior com a distância city-block, dadas os dois caminhos a seguir: A D C B e C B D A

A -> D -> C -> B
  3  + 1  + 2    = 6        therefore
C -> B -> D -> A              fitness(0011 0001 0101 1000) = 6 + 8 = 14
  2  + 3  + 3    = 8

Obviamente, o objetivo é encontrar o layout que minimiza a função de fitness.