Caminho mais curto sem interseção para um gráfico incorporado em um plano euclidiano (2D)

14

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:(0 0,0 0)(-3,2)

[(0 0,0 0)3(0 0,3)2(1,2)4(-3,2)]=7+2.

Gráfico completo:

insira a descrição da imagem aqui

Caminho mais curto:

insira a descrição da imagem aqui

Caminho mais curto sem interseção:

insira a descrição da imagem aqui

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:

[(0 0,0 0)3(0 0,3)3(0 0,6)5(-3,2)]=11)

Esse caminho é mais longo que o menor, mas é o menor caminho sem interseção.

Existe um algoritmo (eficiente) que pode fazer isso?

Fontes TikZ

Realz Slaw
fonte
2
Bom problema! (+1). Você pode dizer algo sobre o aplicativo ou contexto em que esse problema surge? Estou intrigado. (PS Em uma observação separada: a saída óbvia desse dilema é ver se é possível introduzir um novo vértice para cada ponto de interseção, ou seja, todo ponto em que uma aresta pode interceptar outra aresta. No entanto, eu sei que para algumas / muitas aplicações isso pode não ser possível.)
DW
2
@DW, sou eu que estou reformulando o problema de burro / pônei ardente de Babibu ; o aplicativo é o algoritmo heurístico do TSP euclidiano, não sei exatamente como ele pretende usá-lo, mas imagino que ele queira saber se consegue encontrar um caminho entre dois pontos, quando já visitou vários outros (o tour ideal do TSP euclidiano será seja sem interseção). E sim, se você pode introduzir novos nós, isso seria ótimo, mas a questão é se você não pode (e, é claro, você não pode introduzir novas cidades para o TSP Euclidiano).
Realz Slaw
1
Deixe-me tentar converter o problema de existência do caminho para 3SAT. Criar uma maneira de cruzar dois sinais sem cruzar dois caminhos parece o maior desafio.
precisa
1
Sim. Eu quis dizer resolver SAT através disso.
precisa
2
n

Respostas:

11

É 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:

grade de fios à esquerda, coluna de peças da cláusula à direita.

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:

representação gráfica do acima

O ponto de ramificação e o fio vertical funcionam da mesma forma, mas há menos caminhos para correlacionar:

dois pares de caminhos são suficientes aqui.  O fio é essencialmente um ponto de ramificação com a ramificação destruída

¬UMA¬B

insira a descrição da imagem aqui

É 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.

John Dvorak
fonte
Uau, homem bem feito. Ainda não revi, mas o trabalho que você faz é incrível.
Realz Slaw
OK, só quero resumir meu entendimento: usando o primeiro gadget, é possível cruzar dois pares de caminhos literais e manter os caminhos usados. Portanto, não é necessário se preocupar com a planaridade para definir os caminhos (como o gadget xor no PlanarCircuitSat faz para os circuitos). Em seguida, usando o gadget final, é possível criar cláusulas lógicas arbitrárias (não sendo mais necessário se preocupar com a planaridade). Isso está correto?
Realz Slaw
Isso parece correto, mas você precisa garantir duas coisas para um layout geral: que você consiga alimentar todos os dispositivos com um caminho NIP (isso sempre deve ser possível - se um caminho ficar preso no centro, você poderá introduzir dispositivos de arame) reunir extremidades solitárias do caminho) e que todos os caminhos no fio de leitura se cruzem de tal maneira que não seja possível reverter dentro do fio (parece-me que é garantido se não houver cláusulas verdadeiras ( sem cruzar nenhum literal) e se todas as cláusulas estiverem do lado de fora do circuito (na mesma face, o início e o fim estão)).
precisa
é fácil garantir que todos os caminhos no fio de leitura se cruzem - se você quiser ter certeza, basta ramificar n caminhos, depois cruze todos eles imediatamente. Eu acho que isso nunca é necessário, no entanto.
precisa
1
Usei o OpenOffice Draw para a estrutura global e [yEd] (www.yworks.com/products/yed) para o resto. Devo editar isso em (com <sub>)?
precisa
-1

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

vzn
fonte
1
Talvez isso seja melhor como um comentário?
Juho 22/10
-lo cientificamente responde à pergunta básica "o algoritmo que você usaria"
vzn
1
Embora isso possa teoricamente responder à pergunta, seria preferível incluir aqui as partes essenciais da resposta e fornecer o link para referência.
precisa
jan cita uma ref da meta stackexchange. Embora seja uma idéia válida, o papel das citações em ciências / matemática é diferente de um site de dicas de programação ... [reconhecidamente o juiz não está disponível para mim atualmente para obter uma resposta mais detalhada] .. de qualquer maneira, é bem possível algo como construção Jans, embora útil / vale a pena, já está na literatura e na ciência, a sua parte do processo padrão / melhores práticas para [tentativa de] localizá-lo ....
vzn