Diferença entre algoritmo heurístico e de aproximação?

Eu tenho um problema em relação à seguinte situação.

Eu tenho duas matrizes de números como este:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

Agora, suponha que a segunda matriz seja muito difícil de calcular, mas notei que se eu adicionar

A [i] + A [i + 1]

na matriz 1, recebo o número muito próximo do número A [j] na matriz 2.

Minha solução é uma heurística ou aproximação?
Se eu tivesse um motivo para acreditar que nunca ultrapassarei o valor de A [j] por + -x com esse algoritmo e possa provar isso, minha solução seria uma heurística ou aproximação?

Existe alguma literatura que lida com questões heurísticas versus de aproximação para problemas da classe P, em que a solução pode ser alcançada em tempo polinomial, mas a entrada é grande demais para que um algoritmo de tempo poli seja prático.

obrigado

approximation heuristics user6697
fonte

Você primeiro precisa definir o que deseja aproximar para julgar se sua abordagem é uma aproximação.

Dan

Qual é exatamente o problema de otimização que você está tentando resolver? Uma vez que isso é conhecido, se você provar limites, sua heurística se torna uma aproximação. Além disso, os únicos problemas (clássicos, ou seja, sem transmissão) em P que possuem algoritmos de aproximação (que eu conheço) são algoritmos de fluxo máximo.

Nicholas Mancuso 01/03

ok então a coisa que eu quero calcular são os números dentro da segunda matriz. mas isso leva muito tempo, no entanto, descobri que, se adicionar dois valores consecutivos da matriz 1, obtive algo ok e posso provar que a estimativa sempre estará dentro de + -x. alg inicial para computação A [j] é O (n ^ 100)

user6697

Entendo que você deseja calcular os números na segunda matriz, mas qual é a formulação do problema de otimização. Dado X calcule Y sob as restrições de Z. Dizer que você deseja calcular alguma função arbitrária não ajuda.

Nicholas Mancuso 01/03

Sua solução é um exemplo perfeito de heurística!

Björn Lindqvist

Respostas:

Uma heurística é essencialmente um palpite, ou seja, o caso que você descreve ("notei que está próximo", você não tem uma prova disso) é uma heurística. Como está resolvendo o problema do vendedor ambulante , iniciando em um vértice aleatório e indo para o mais próximo ainda não visitado cada etapa. É uma ideia plausível , que não deve dar uma solução muito ruim. Nesse caso, pode ser demonstrado que nem sempre é uma boa solução.

Geralmente, um algoritmo de aproximação fornece uma solução aproximada, com algum tipo de garantia de desempenho (ou seja, resolve TSP, e o custo total nunca é reduzido em mais de um fator de 2; ou melhor ainda, resolve TSP e, dependendo de <alguns parâmetros que podem ser variados> a solução nunca é pior do que a ideal em mais de um fator , em que depende de <parâmetros>). $1 + \epsilon$ $\epsilon$

vonbrand
fonte

Você usou amostra ruim, é difícil aproximar o TSP; portanto, não há PTAS para TSP e também não há 2 aproximações para TSP. É fácil mostrar se há tempo polinomial. 2-aproximação para TSP há algoritmo de tempo polinomial para resolver problemas do ciclo hamiltoniano. , Acho que você quer dizer TSP métrico, que é um caso especial, mas ainda não existe PTAS nesse caso (e é impossível ter PTAS, exceto P = NP). Eu sugeriria escolher uma embalagem para falar sobre isso. (ou qualquer outro problema mais simples).

@SaeedAmiri, era apenas para fins ilustrativos. Talvez não seja o melhor exemplo (como você declara), mas o problema é fácil de entender. Obrigado pelo comentário.

vonbrand

Então, se você entende que este é um exemplo errado, por que você não o corrige?

@SaeedAmiri Eu acho que está totalmente bem. Lembre-se de que não sabemos se, por exemplo, , em que a dureza da aproximação pode ser baseada.

P = N P

$\mathsf{P}=\mathsf{NP}$

Juho

@Juho, pelo meu conhecimento é totalmente errado, mesmo sabendo que não sabemos , o ponto principal é que pode estar na direção de reverência ( ), portanto, não devemos usar amostras ruins, deve usar amostras que sabemos que estão corretas independentemente de coisas que não sabemos.

P = N P

$P=NP$

P \neq N P

$P\not =NP$

Você pode ver esta resposta muito interessante sobre heurística na Wikipedia:

"uma heurística é uma técnica projetada para resolver um problema mais rapidamente quando os métodos clássicos são muito lentos. O objetivo de uma heurística é produzir com rapidez suficiente uma solução que seja boa o suficiente para resolver o problema em questão".

A heurística pode derivar da teoria ou da experiência experimental, mas os algoritmos de aproximação têm base sólida na teoria (solução comprovável).

Reza
fonte

Quanto à sua última pergunta, não existe uma teoria separada para algoritmos de aproximação para problemas solucionáveis em tempo polinomial. De fato, pode ser que . Alguns exemplos de algoritmos de aproximação para problemas em incluem algoritmos para álgebra linear numérica e geometria computacional. Veja a pergunta Algoritmos de aproximação para problemas em P para obter mais. $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}$

Juho
fonte