Please enable JavaScript.

Coggle requires JavaScript to display documents.

Branch-and-Bound - Coggle Diagram

- - - - problema clássico de otimização em que a tarefa é atribuir n tarefas (ou trabalhos) a n agentes (ou trabalhadores), de forma que a atribuição resulte no menor custo total possível.
      - Cada agente pode realizar apenas uma tarefa e cada tarefa deve ser realizada por um único agente.
      - O problema é modelado como um grafo bipartido completo, onde os vértices da primeira partição correspondem aos agentes e os vértices da segunda partição correspondem às tarefas. As arestas do grafo são rotuladas com os custos associados à atribuição de uma determinada tarefa a um determinado agente.
      - tem muitas aplicações práticas, como a atribuição de pessoal em empresas, a alocação de recursos em projetos e a programação de máquinas em fábricas.
    - - escolha de itens para serem colocados em uma mochila, de forma que se maximize o valor total dos itens escolhidos, considerando-se uma capacidade máxima predefinida para a mochila.
      - dado um conjunto de n itens, cada um com um valor vi e um peso wi, e uma capacidade máxima W para a mochila, escolha um subconjunto de itens que maximize o valor total dos itens escolhidos, de forma que a soma dos pesos desses itens não exceda a capacidade W da mochila.
      - problema NP-difícil, o que significa que não há uma solução eficiente conhecida para resolver todos os casos do problema em tempo polinomial.
      - A abordagem gulosa funciona selecionando o item de maior valor em cada etapa e o colocando na mochila, contanto que o peso do item não exceda a capacidade restante da mochila. A abordagem de programação dinâmica divide o problema em subproblemas menores e utiliza a solução ótima dos subproblemas menores para obter a solução ótima para o problema geral.
      - tem aplicações em diversas áreas, como gestão de estoque, planejamento financeiro, otimização de recursos, entre outras.