Re: Heurísticas!!??? (EP3)

[Ricardo Drizin <ricardo@linux.ime.usp.br>]

Assino embaixo.

E tem muita gente precisando de nota (quem não entregou algum dos eps
anteriores, por exemplo).. vai ser chato ficar de recuperação por causa
de ep. Se pelo menos houvesse um ep-sub.. ou ep-rec ;)

Quem vai fazer a boa ação do dia e resolver as dúvidas sobre o EP que
ninguem respondeu ainda?

Todos os colegas que eu consultei estão mais perdidos do que
eu..

Como nenhuma das minhas dúvidas foi sanada.. (nem de outros), vou falar o
que entendi e fiz, e alguém por favor me corrija aonde eu estiver
errado.. pois não pretendo ficar de recuperação por causa de um
ep.

Pra quem está muito perdido, recomendo:
http://mat.gsia.cmu.edu/orclass/integer/integer.html
- Leiam "Solving Integer Programs", "Relationship to Linear Programming", e "Branch and Bound". Ah, tem também sobre o knapsack, e outras coisas que podem ser úteis.

Pra quem está na duvida sobre os 3 métodos de percorrer a árvore:
http://www.cs.csustan.edu/~john/Classes/CS4440/Notes/Chapter09/9.7-branchBound.html (fim do texto)
A única diferença entre os métodos é a estrutura usada para armazenar os futuros nós (heap, pilha, ou fila). E o heap nada mais é do que uma fila de prioridade para obtermos os nós com melhor custo.

O lower-bound só será inicializado quando acharmos a primeira solução inteira.

Um nó será ativo quando (uma destas):
a) ainda nao foi usado para "branch" (dividido em 2 subproblemas)
b) todas variáveis da solução são inteiras.
c) o problema é infactível
d) você pode descartar o nó (e seus filhos, pois o custo de um filho nunca será melhor que o do pai) por um "bounding argument" (uma solução inteira melhor, que é nosso lower-bound).

Ou seja, os nós que se dividirão em subproblemas são apenas os que têm solução fracionária, e custo melhor do que nossa "melhor solução inteira encontrada".

Tirando isso tudo.. falta alguma coisa?

(Os professores que me perdoem se eu dei alguma dica que nao deveria.. é que tá fogo.. )


At 21:23 24/06/02 -0300, you wrote:
> A verdade é que este EP3 é o mais nebuloso com o qual já nos deparamos. Na
> sala de aula, os círculos de discussão sobre esse assunto demonstram que
> pouca gente sabe sequer por onde começar e a impressão é que nem o professor
> sabe exatamente o que ele quer que se faça neste EP. Entendo que devemos nos
> acostumar a pesquisar sozinhos, mas quando vamos atrás dos "Google" da vida
> para procurar algo sobre o assunto, deparamo-nos com maneiras muito
> complexas de implementar as heurísticas. Acho que precisamos de um pouco
> mais de LUZ!
>
> Cabral.
>
>
> ----- Original Message -----
> From: "Juliana Barby Simão" <julianab@linux.ime.usp.br>
(...)
> > Oh, vida... qts dúvidas para um ep a ser entregue daqui a 4 dias... ;-)