O Papai Noel pode ser justo e eficiente?
Como estabelece a rede sempre-verde A Física do Papai Noel , é fisicamente impossível para o Papai Noel receber um presente para todas as crianças do planeta. O planejamento de rotas não ajuda muito lá, mas pode um bom algoritmo de planejamento garantir que todas as crianças recebam um presente de vez em quando, enquanto o Papai Noel também serve o maior número possível de crianças a cada ano?
Considere um gráfico completo com pesos reais reais e uma constante kk. Queremos resolver uma variante do problema da pessoa de vendas itinerante:
Existe uma rota circular de comprimento no máximo kk que serve mais de mm nós?
A versão de otimização seria:
Maximize o número de nós que podem ser atendidos com uma rota circular de comprimento no máximo kk.
Isso é motivado pelas limitações do mundo real nas rotas: o Papai Noel tem uma noite para entregar o maior número possível de presentes, um vendedor tem oito horas para a rota de um dia e assim por diante.
A primeira pergunta, mas não a final, é: quão difícil é esse problema? Vamos supor que podemos começar em qualquer nó, mas isso não deve fazer muita diferença.
Agora, para modelar a justiça, vamos assumir que existem NN nós e podemos visitar no máximo MMcom cada passeio. Idealmente, gostaríamos que cada nó fosse visitadot⋅MNt⋅MN vezes através ttpasseios eficientes. Como pode haver nós de gargalo que precisam ser visitados com mais frequência para garantir que as rotas visitem muitos nós, alguns inevitavelmente precisarão ser visitados com menos frequência. Isso também exclui a aproximação trivial de remover os nós visitados uma vez até que todos tenham sido visitados.
Então, aqui está a pergunta final. DeixeiTTser o número de passeios necessárias até que todos os nós têm sido visitado por eficiente kk-tours. Como podemos determinar algoritmicamente o valor mínimo deTT(e todas as rotas necessárias)? Quão complexo é esse problema?
Eu acho que esse é realmente um problema com vários critérios: cada passeio deve visitar o maior número possível de nós, enquanto queremos mantê-lo o mais distraído possível.
O verdadeiro Papai Noel usa boa mágica para resolver problemas completos de NP em O(1)O(1)Tempo. Se você tem uma instância difícil do 3DM que precisa resolver até o final do ano, tente escrever para ele no Pólo Norte e, se você for um bom pesquisador, ele poderá lhe responder no Natal.
Estou um pouco confuso. E sekk é uma constante, então você pode tentar tudo O(nk)O(nk)possíveis passeios. Portanto, o problema está emPP.
No entanto, se kk faz parte da entrada, o problema de decisão é NPNP-completo. Isso pode ser demonstrado reduzindo-seHAM-CIRCUITHAM-CIRCUIT para o problema, pela seguinte redução.
Suponha que desejamos determinar se um nn-vertex graph GGtem um circuito hamiltoniano. Então, tomamos o gráfico completoKnKn com a seguinte função de distância
Além disso, escolhemos k=nk=n e m=n−1m=n−1.
Deixe-me dizer por que isso é uma redução. E seGG tem um circuito Hamiltoniano, então há um tour em KnKn com comprimento nn. Em outras palavras, uma rota circular de comprimento≤n≤n que serve >(n−1)>(n−1)nós. Por outro lado, se houver um passeio de Papai Noel que visite>(n−1)>(n−1)nós é tem que visitar todos os nós. Como o passeio de Papai Noel só pode ter duração≤n≤n e todo comprimento da borda é pelo menos 1, todos nn As arestas deste passeio têm duração 1. Portanto, este passeio corresponde a um circuito hamiltoniano em GG.
Isso é verdade para encontrar um passeio com muitos nós, mas o objetivo adicional e concorrente de visitar todos os nós com poucos passeios dificulta as coisas?