Um problema de otimização contínua que reduz a TSP

11

Suponha que eu sou dado um conjunto finito de pontos no plano, e pediu para desenhar um duas vezes diferenciável curva C ( P ) através do p i 's, de tal modo que o seu perímetro seja tão pequena quanto possível. Supondo que p i = ( x i , y i ) e x i < x i + 1 , posso formalizar esse problema como:p1,p2,..pnC(P)pipi=(xi,yi)xi<xi+1

Problema 1 (editado em resposta aos comentários de Suresh) Determine as funções x ( t ) , y ( t ) de um parâmetro t de modo que o comprimento do arco L = [ t 0 , 1 ] C2x(t),y(t)t é minimizado, comx(0)=x1,x(1)=xne para todosti:x(ti)=xi, temosy(ti)=yi).L=[t0,1]x2+y2dtx(0)=x1,x(1)=xnti:x(ti)=xiy(ti)=yi)

Como provar (ou talvez refutar) que o Problema 1 é difícil para o NP?

Por que eu suspeito que a dureza NP Suponha que a suposição de seja relaxada. Evidentemente, a função do comprimento do arco mínima é o passeio do Caixeiro Viajante do p i 's. Talvez a restrição de C 2 apenas torne o problema muito mais difícil?C2piC2

Contexto Uma variante deste problema foi postada no MSE . Não recebeu uma resposta lá e no MO . Dado que não é trivial resolver o problema, quero estabelecer o quão difícil é.

PKG
fonte
1
A restrição de que parece facilitar muito o problema. Em particular, se você agora eliminar a restrição C 2 , por que esse problema não é resolvido trivialmente porque você conecta os pontos por linhas retas? xi<xi+1C2
Suresh
1
Isso não é uma função. Se você "pular" de para p 2 , sob a restrição de que x 1 < x 2 < x 3 , sua curva cruzará uma linha vertical duas vezes. p3p2x1<x2<x3
quer
1
Não está claro, você precisa indicar o que você quer dizer com "determinar" aqui. Não é uma terminologia padrão. Nem sequer é um problema de decisão, portanto, usar o termo NP-hard não faz sentido.
Kaveh
1
@Suresh, você pode expandir a parte de saída? Eu estou supondo que você quer dizer emitir o nome de uma maldição a partir de um conjunto enumerável de curvas. Observe que, nesse caso, não está claro que a curva ideal será sempre dessa classe. Por outro lado, se pretendemos encontrar o melhor ou o melhor entre esses (ou uma aproximação até um dado parâmetro da curva ótima), a classe de curvas paramétricas deve ser especificada; caso contrário, a questão é incompleta e não pode ser respondidas.
Kaveh
1
A entrada / saída não é mais um objeto finito, por exemplo, se você realmente está lidando com números / funções reais, seu problema é do tipo superior. Cada objeto infinito é dado por uma série infinita de aproximações ao objeto pretendido. A página da rede CCA contém mais links, se você estiver interessado.
Kaveh

Respostas:

12

O requisito de diferenciabilidade não altera a natureza do problema: exigir (continuidade) ou C (diferenciabilidade infinita) fornece o mesmo limite inferior para o comprimento e a mesma ordem de pontos e é equivalente a resolver o problema do vendedor ambulante .C0C

Se você tem uma solução para o TSP, possui uma curva que passa por todos os pontos. Por outro lado, suponha que você tenha uma curva C 0 de comprimento finito que passa por todos os pontos e permita que p σ ( 1 ) , , p σ ( n ) seja a ordem em que ele percorre os pontos et 1 , , t n os parâmetros correspondentes (se a curva atravessa um ponto mais do que uma vez, escolher qualquer um dos possíveis valores de t ). Então a curva construída a partir de n segmentos [C0C0pσ(1),,pσ(n)t1,,tntn[pσ(1),pσ(2)],,[pσ(n1),pσ(n)],[pσ(n),pσ(1)]é mais curto, porque para cada segmento uma linha reta é mais curta do que qualquer outra curva que conecta o ponto. Assim, para cada pedido dos pontos, a melhor curva é uma solução TSP, e a solução TSP fornece o melhor pedido dos pontos.

Vamos agora mostrar que exigir que a curva seja (ou C k para qualquer k ) não altera a melhor ordem dos pontos. Para qualquer solução TSP de comprimento total e ϵ > 0 , podemos arredondar todos os cantos, ou seja, construir uma curva C que atravessa os pontos na mesma ordem e tem um comprimento máximo de + ϵ (a construção explícita depende de funções algébricas e e - 1 / t 2 para definir funções de resposta e a partir dessas conexões suaves entre segmentos de curva, comoCCkkϵ>0C+ϵe1/t2 que se conecta com y = 0 em x = 0 e com y = x em x = 1 ; é tedioso explicitar isso, mas eles são computáveis); Assim, o limite inferior para um C curva é a mesma que para um conjunto de segmentos (nota que o limite inferior não é alcançado, em geral).e11/x2(xe1/(1x)2)y=0x=0y=xx=1C

Gilles 'SO- parar de ser mau'
fonte
Este é exatamente o argumento que eu procurava há muito tempo! Você pode dar uma referência para a construção tediosa?
PKG
1
Isso não é totalmente rigoroso, especialmente porque no plano você pode obter uma aproximação arbitrariamente boa do TSP em tempo polinomial.
quer
Eu pensei que você poderia aproximar TSP apenas dentro de um fator de 2 no tempo poli?
PKG
@PKG A construção provavelmente tem um nome, mas temo que minhas aulas de cálculo tenham sido há muito tempo para eu me lembrar. Acabei de lembrar que a conexão básica é chamada de função de resposta.
Gilles 'SO- stop being evil'
1
ϵ1/ϵ1+ϵ