07 - Busca local

Nesta aula trabalharemos com um algoritmo chamado "Busca local", que consiste basicamente em fazer pequenas atualizações que melhoram sucessivamente uma solução.

Solução aleatorizada

Vamos iniciar criando soluções aleatórias. Isto nos permitiria criar uma grande quantidade de soluções e, eventualmente, pegar a melhor delas. Apesar de ser muito mais simples que a busca heurística, a quantidade massiva de soluções geradas tem potencial de encontrar boas soluções.

Vamos trabalhar com um algoritmo bem simples para gerar soluções aleatórias:

• Para cada objeto, selecione-o com probabilidade 0.5.
• Se o objeto for selecionado, coloque-o na mochila se couber.

Question

Supondo que só existe uma solução ótima global, qual é a chance de a encontrarmos repetindo o algoritmo acima?

Question

Supondo que todos os objetos caibam na mochila, quantos são selecionados em média?

Example

Implemente o algoritmo acima. Use seed=10.

Example

Repita o algoritmo 10 vezes e pegue somente a melhor solução.

Tip

Use os arquivos de entrada/saída disponibilizados nas aulas passadas.

Busca local

Vamos agora implementar uma busca local para a Mochila Binária seguindo os dois algoritmos vistos na expositiva.

Mochila cheia

Para implementar a Mochila cheia iremos adotar a seguinte estratégia:

1. Gere uma solução aleatória.
2. Percorra novamente todos os objetos (na ordem da entrada)
3. Se um objeto couber na mochila, inclua-o.

Example

Implemente o algoritmo acima.

Example

Rode a Mochila cheia 10 vezes e retorne a melhor solução.

Question

Houve melhoria em relação ao aleatório sozinho? Foi significativa?

Fechamento

Question

Como você avalia os ganhos obtidos pela busca local em relação ao aleatório? E em relação a heurística?