Qual algoritmo você usaria para encontrar o caminho mais curto de um gráfico, incorporado em um plano euclidiano, de modo que o caminho não contenha nenhuma auto-interseção (na incorporação)?
Por exemplo, no gráfico abaixo, você deseja ir de . Normalmente, um algoritmo como o algoritmo de Dijkstra produziria uma sequência como:
Gráfico completo:
Caminho mais curto:
Caminho mais curto sem interseção:
No entanto, esse caminho se cruza no plano euclidiano, portanto, eu quero um algoritmo que me daria a menor seqüência sem interseção, neste caso:
Esse caminho é mais longo que o menor, mas é o menor caminho sem interseção.
Existe um algoritmo (eficiente) que pode fazer isso?
Fontes TikZ
algorithms
graphs
shortest-path
graph-traversal
weighted-graphs
Realz Slaw
fonte
fonte
Respostas:
É NP-completo até decidir se existe algum caminho.
É claramente possível verificar se um caminho é válido no gráfico fornecido. Assim, o problema de comprimento delimitado está no NP, assim como seu subconjunto, o problema de qualquer caminho.
Agora, para provar a dureza NP do problema de qualquer caminho (e, portanto, do problema de comprimento delimitado), vamos reduzir o SAT-CNF para esse problema:
A estrutura global é uma grade de peças de arame unidas por uma coluna de peças de cláusula. A fórmula lógica é satisfatória se existir um caminho sem interseção no gráfico.
É impossível cruzar duas partes do caminho, mas é necessário cruzar dois fios lógicos. Em vez disso, o fluxo do caminho é dado estritamente: um ponto de conexão é dado por dois nós. A sequência dos pontos dos fios através dos quais o caminho passa é forçada pela redução. A lógica é representada por qual nó é escolhido. Qualquer caminho pode ser escolhido desde que passe por todos os pontos de conexão.
Neste diagrama, o caminho é representado pela curva vermelha e o fluxo lógico é representado pelos fios pretos:
Agora vamos construir cada componente.
A fiação usa três peças: a travessia, o ponto de ramificação e o fio vertical. Vamos começar com o mais difícil:
A idéia básica por trás da travessia é preparar um caminho para cada par de pontos de ligação e dobrar os caminhos possíveis o suficiente para que todos os pares, exceto aqueles que codificam a mesma lógica (caminhos compatíveis), se cruzem. É claro que não podemos apenas dizer que duas arestas paralelas se cruzam, mas podemos introduzir nós de ordem 2 extras para fazer dois caminhos se cruzarem.
Supondo que os caminhos venham de norte a oeste e de sul a leste, podemos: coletar cada caminho do norte com seu caminho compatível do leste em uma linha (alguns caminhos incompatíveis se cruzam); cruze cada par, invertendo a ordem dos pares; distribuir os caminhos para os pontos de extremidade sul e oeste. Isso é melhor explicado por um diagrama. Aqui, cada par de nós representa um ponto de conexão. Caminhos com o mesmo código de cor (carregando a mesma lógica) não se cruzam, caminhos com um código de cor diferente:
O ponto de ramificação e o fio vertical funcionam da mesma forma, mas há menos caminhos para correlacionar:
É possível generalizar essa redução para codificar uma árvore arbitrária de portas AND e OR ramificando o fio de leitura de maneira diferente. Em particular, SAT-CNF e SAT-DNF são ambos possíveis de reduzir ao problema do caminho sem interseção da maneira descrita acima.
fonte
<sub>)?o problema parece remontar a Turan, em 1944. isso parece uma boa pesquisa de teoria e algoritmos, o Número Cruzado de Gráficos: Teoria e Computação, de Mutzel. wikipedia tem algumas informações abaixo do número de cruzamentos de gráficos
fonte