34
Busca Informada

Busca Informada

Embed Size (px)

Citation preview

Page 1: Busca Informada

Busca Informada

Page 2: Busca Informada
Page 3: Busca Informada
Page 4: Busca Informada
Page 5: Busca Informada
Page 6: Busca Informada
Page 7: Busca Informada
Page 8: Busca Informada
Page 9: Busca Informada
Page 10: Busca Informada
Page 11: Busca Informada
Page 12: Busca Informada
Page 13: Busca Informada
Page 14: Busca Informada
Page 15: Busca Informada
Page 16: Busca Informada
Page 17: Busca Informada
Page 18: Busca Informada
Page 19: Busca Informada
Page 20: Busca Informada
Page 21: Busca Informada
Page 22: Busca Informada
Page 23: Busca Informada
Page 24: Busca Informada
Page 25: Busca Informada
Page 26: Busca Informada
Page 27: Busca Informada
Page 28: Busca Informada
Page 29: Busca Informada
Page 30: Busca Informada

O Problema da mochila

Dados um conjunto de n objetos e uma mochila com:

cj = benefício do objeto j

wj = peso do objeto j

b = capacidade da mochila

Determinar quais objetos devem ser colocados na mochila para maximizar o benefício total de tal forma que o peso da mochila não ultrapasse sua capacidade.

Page 31: Busca Informada

Uma instância do Problema da Mochila

Page 32: Busca Informada

O problema da mochila zero-um

𝑧=∑𝑗=1

𝑛

𝑐 𝑗𝑠 𝑗Maximizar

∑𝑗=1

𝑛

𝑤 𝑗 𝑠 𝑗≤𝑏Sujeito a

𝑠 𝑗∈ {0,1 }

Uma solução s é um vetor de uns e zeros.Se o objeto j está mochila então sj = 1, caso contráriosj = 0.

(do inglês, 0-1 knapsack problem)

Page 33: Busca Informada

Vizinhança no problema da mochila

s = (0,1,0,1,0)

(1,1,0,1,0)

(0,0,0,1,0)

(0,1,1,1,0)

(0,1,0,0,0) (0,1,0,1,1)

O movimento consiste em mudar a variável sj de 1 para 0ou vice-versa.

Page 34: Busca Informada