Existe um método geral para avaliar a otimização de um algoritmo de otimização?

existe um método geral para avaliar a otimização de um algoritmo de otimização, por exemplo, um algoritmo que resolve um problema NP-hard ou NP-complete?

O único método que eu vim até agora é comparar os resultados do algoritmo com soluções ótimas já conhecidas.

Caso contrário, existem métodos específicos para alguns problemas especiais?

EDIT Para esclarecer: por otimização, quero dizer o quão perto o resultado está de um resultado ideal de soluções.

Depende do tipo de problema.

Se houver um esquema de aproximação de tempo polinomial (PTAS) para o problema (por exemplo, TSP Euclidiano), você poderá obter uma solução arbitrariamente próxima da solução ideal no tempo polinomial. Isso significa que, para cada e > 0, existe um algoritmo de tempo polinomial que encontrará uma solução aproximada para o seu problema, que é garantida como estando dentro de (1+ e ) da solução ideal. Nesse caso, você compararia a complexidade do tempo de execução / memória de dois algoritmos para os mesmos valores de e . Se um algoritmo pode oferecer as mesmas "garantias de otimização" que o outro, mas com um menor tempo de execução / custo de memória, provavelmente é o melhor algoritmo.

Se o problema for APX, mas não PTAS , ou seja, se houver algoritmos de aproximação de tempo polinomial que garantam a produção de soluções que estejam dentro de um fator constante da solução ideal, você poderá comparar esse fator constante. Aquele com o fator mais baixo produzirá as melhores soluções (mas muitas vezes ao custo de custos de tempo / memória mais altos)

Se o problema não estiver em nenhuma dessas classes, acho que o melhor que você pode fazer é comparar suas soluções para um conjunto de problemas aleatórios ou para problemas com soluções ótimas conhecidas.

Não acho que exista uma maneira geral de fazê-lo, mas certamente existem métodos para fazê-lo.

Tome, por exemplo, o problema SET-COVER. Para quem não conhece o problema é o seguinte:

Dado um conjunto de elementos B={1,2,...,m}e um número de subconjuntos S_1, S_2, ..., S_ncuja união é B. Você está tentando encontrar o número mínimo desses subconjuntos para que a união ainda seja B. Um exemplo típico desse problema no mundo real é onde você recebe uma coleção de bairros e tenta encontrar os locais ideais para instalar escolas, de modo que cada bairro seja atendido a menos de alguma distância dda escola mais próxima. Nesse caso, Bé o conjunto de bairros e S_xconsiste em todos os conjuntos dentro dda cidade x.

Você prova que esse problema é NP-COMPLETE. No entanto, existe uma solução simples e gananciosa, na qual você escolhe repetidamente o aparelho S_icom o maior número de elementos descobertos. E você pode provar que esse algoritmo se sai bem .

Se o algoritmo ideal consistir em kconjuntos, o algoritmo ganancioso consistirá em não mais do que k ln(n)conjuntos onde ln é o logaritmo natural.

O problema de determinar se um programa tem 'desempenho de otimização' A ou 'desempenho de otimização' B para praticamente qualquer definição de 'desempenho de otimização' é indecidível em geral (prova a seguir). Isso implica que não existe um método único que possa sempre dizer o quão ótimo é um algoritmo.

No entanto, existem métodos frequentemente aplicados na análise de algoritmos de aproximação. Freqüentemente, os algoritmos de aproximação são avaliados por suas garantias de quão longe sua solução está da solução ideal. Vou dar um exemplo de problema e aproximação, que vou provar usando o método 'limite inferior', que é um método muito usado para provar proporções.

O problema em questão é o problema de "carregamento de caminhão": temos muitos caminhões idênticos (quantos quisermos), cada um capaz de transportar uma carga com peso máximo de T. Nós temos n objetos que queremos carregar nesses caminhões para transporte. Todo objeto i tem um peso w_i, onde w_i <= T (portanto, não há itens que não possam caber em um caminhão, nem eles mesmos). Os itens não podem ser divididos em partes. Gostaríamos de encher caminhões para que precisemos do menor número possível de caminhões. Este problema está NP-completo.

Existe um algoritmo de aproximação muito fácil para esse problema. Simplesmente começamos a carregar um caminhão com itens, até que o caminhão esteja tão cheio que o próximo item não caiba. Em seguida, pegamos outro caminhão e carregamos esse caminhão com este item que não se encaixava no caminhão anterior. Não carregamos mais itens neste caminhão: em vez disso, pegamos um caminhão novo, o preenchemos com muitos itens novamente até que ele não caiba mais, colocamos esse último item em seu próprio caminhão novamente e assim por diante.

Esse algoritmo é a chamada aproximação 2 para o problema: utiliza no máximo o dobro do número de caminhões necessário para a solução ideal. O 'máximo' é crucial: podemos ter sorte e encontrar a solução ideal, mas pelo menos não faremos muito mal.

Para provar isso, primeiro definimos um limite inferior para o número ideal de caminhões de que precisamos. Para isso, imagine que podemos cortar itens em partes: então poderíamos encher facilmente todos os caminhões, exceto o último. O número de caminhões que precisaríamos se o fizéssemos é um limite inferior para o número de caminhões que precisamos para a pergunta original: no "melhor" caso, a solução ideal sempre preenche todos os caminhões completamente; nesse caso, o número de caminhões é igual, mas se as soluções ideais deixarem os caminhões não preenchidos, ele precisará apenas de mais caminhões.

Agora, olhamos para o nosso algoritmo de aproximação. Observe que em cada etapa, nós (parcialmente) enchemos dois caminhões. Observe também que, pela maneira como o algoritmo funciona, os itens no primeiro caminhão e o item no segundo caminhão juntos não podem caber no primeiro caminhão, portanto, sua soma é pelo menos T. Isso significa que a cada passo, carregamos pelo menos um caminhão vale itens em dois caminhões. Agora compare isso com nosso limite inferior: nesse caso, carregamos um caminhão cheio de itens em um caminhão. Em outras palavras, nosso algoritmo de aproximação calcula (em tempo linear) uma solução que se parece muito com nossa 'solução' de limite inferior, mas usa dois caminhões em vez de um. Portanto, usamos no máximo o dobro de caminhões do que o algoritmo ideal, porque usamos no máximo o dobro de caminhões do que nosso limite inferior no algoritmo ideal.

Esse algoritmo fornece uma aproximação de fator constante: é no máximo duas vezes mais ruim que a solução ideal. Alguns exemplos de outras medidas: no máximo C acima da solução ideal (erro aditivo, bastante incomum), no máximo c log n vezes tão ruim quanto a solução ideal, no máximo cn vezes tão ruim quanto a solução ideal, no máximo c 2 ^ (dn) vezes tão ruim quanto a solução ideal (muito ruim; por exemplo, o TSP geral só admite algoritmos com esse tipo de garantia).

Obviamente, se você quer ter certeza de que o fator que você prova é o melhor que pode provar, tente encontrar casos em que a solução fornecida por seu algoritmo é realmente tão ruim quanto possível.

Observe também que, às vezes, usamos algoritmos de aproximação em problemas que não são difíceis de NP.

Aprendi isso (entre muito mais) no curso de algoritmos de aproximação na minha universidade.

Prova de indecidibilidade: seja P um problema e A e B sejam algoritmos de aproximação para P, onde A e B não têm a mesma 'otimização' para alguma definição sensata de 'otimização' e onde o tempo de execução de A e B é ômega (1) (estritamente mais lento que o tempo constante, ou seja, eles se tornam mais lentos para casos maiores) e onde A e B sempre param.

Seja D um programa que afirma que pode calcular o seguinte: dado algum programa C calculando uma aproximação para P, decida se é tão bom quanto A ou tão bom quanto B para entradas suficientemente grandes (você pode, portanto, usá-lo para categorizar programas de acordo com a sua otimização).

Podemos então usar D para resolver o problema de parada. Seja E um programa e F seja uma entrada para este programa. Usaremos D para decidir se E será interrompido na entrada F.

Nós projetamos um programa G que faz o seguinte: dada uma entrada S para o problema P, ele executa E em F e A em S em paralelo: executa E por um tempo, depois A, depois E novamente e assim por diante. Se E parar em F, ele pára de executar A e, em vez disso, executa B em S e retorna o resultado de B. Se A parar antes de E parar, ele retornará o resultado de A.

O uso de D em G agora decide se E pára em F: se E pára em F, então para entradas suficientemente grandes S, E pára em F antes de A parar em S (porque o tempo que leva para parar E não depende do tamanho de entrada, ao contrário de A). D, portanto, relata que G possui as características de otimalidade de B. Se E não parar em F, D relatará que G possui as características de otimalidade de A.