Como você pode limitar o erro de uma aproximação sem conhecer a solução ideal?

14

Eu estive pesquisando neste site e ele diz que as pessoas encontraram soluções para passeios TSP que são apenas 0,031% mais altos do que o passeio ideal. Sem encontrar o passeio ideal, como eles sabem qual é a duração?

complexity-theory approximation Ilya Gazman
fonte
4
As soluções são, no máximo, 0,031% mais altas do que o tour ideal. Sem encontrar o tour ideal, ainda é possível encontrar um limite inferior nele e no algoritmo de aproximação, o que permite "comparar" soluções aproximadas com a solução ideal.
Tpecatte
3
Você deveria realmente pegar um livro sobre a teoria da complexidade e / ou como resolver problemas difíceis de NP . Você tem pouca esperança de realmente resolver P? = NP em sua vida e convencer alguém que você fez se continuar insistindo em propostas / perguntas que provam que você não entendeu os conceitos de graduação. Obviamente, podemos ajudá-lo a chegar a esse entendimento.
Raphael
seria útil se você citasse a pessoa declarando esse limite [TO, o mesmo]. depois, não existe esse limite de tempo P conhecido em geral. existem outros limites de aproximação expressos em funções dos parâmetros do problema, por exemplo, pontos etc.
vzn 17/10/2013

Respostas:

8

Em geral, quando você deseja vincular a taxa de aproximação de um algoritmo, procura um limite inferior fácil no valor ideal. O mais direto é frequentemente o relaxamento de LP de uma formulação de ILP (adequadamente escolhida) do problema. Às vezes, outras coisas são usadas, para TSP, por exemplo, você também pode usar o peso de um MST (o passeio ideal menos uma borda é uma árvore, por isso não pode pesar menos que o MST).

Para casos particulares, é claro que você ainda pode usar o que usa em suas provas, ou seja, pode resolver o LP e comparar sua solução heurística com o valor do LP. Se você tiver mais tempo de CPU em suas mãos, também poderá iniciar um processo de ramificação e ligação para resolver o ILP. Mesmo que você não resolva completamente o ILP, obtém melhores limites inferiores da dualidade do LP.

adrianN
fonte
Você pode explicar ou me fornecer um link para ler sobre. O que é LP, ILP, MST
Ilya Gazman
1
Eu editei minha resposta para incluir links da Wikipedia.
Adriann