Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema da alocação em python usando a técnica conhecida como Branch and Bound?

+1 voto
157 visitas
perguntada Mai 14, 2016 em Ciência da Computação por CaioP (21 pontos)  
editado Mai 14, 2016 por CaioP
Compartilhe
comentou Mai 14, 2016 por CaioP (21 pontos)  
editado Mai 14, 2016 por CaioP

É interessante notar que a estratégia "branch and bound" é um caso particular da estratégia "exhaustive search" (ie gerar todos os casos e identificar o que atende ao critério desejado). Nesse sentido, a estratégia "branch and bound" é uma implementação esperta, pois acrescenta um critério de viabilidade que restringe o universo da busca, baseado numa cota superior/inferior ao que se pode obter com um determinado "caminho", daí sua aplicação natural em problemas de otimização.

1 Resposta

+1 voto
respondida Mai 14, 2016 por CaioP (21 pontos)  
people_jobs = {0:[9,2,7,8],
               1:[6,4,3,7],
               2:[5,8,1,8],
               3:[7,6,9,4]}

import Queue

bestList=[]

class Node:
    def __init__(self,level,value,bound,ans):
        self.level=level 
        self.value=value 
        self.bound=bound   
        self.ans=ans   

def get_Bound(node,people_jobs):
    lowerBound = node.value
    j = node.level + 1
    while j < len(people_jobs[0]):
        lowerBound = lowerBound + min(people_jobs[j])
        j = j + 1
    return lowerBound

def solve_assignment(people_jobs):
    numberJobs=len(people_jobs[0])
    queue=Queue.PriorityQueue()
    root=Node(-1,0,0,[])
    queue.put((0,root))
    minvalue=10000000000
    while not queue.empty():
        v=queue.get()[1]
        print "Level: ",v.level,"Value: ",v.value, "Bound: ",v.bound,"Value ",v.value,"Ans ",v.ans
        if(v.bound<minvalue and v.level<numberJobs-1):
            uLevel=v.level+1
            for i in range(0,numberJobs):
                if i not in v.ans:
                    uValue=v.value+people_jobs[uLevel][i]
                    uAssignment=v.ans[:]
                    uAssignment.append(i)
                    u=Node(uLevel,uValue,0,uAssignment)
                    uBound=get_Bound(u,people_jobs)
                    u=Node(uLevel,uValue,uBound,uAssignment)

                if u.level==numberJobs-1 and u.value<minvalue:
                    minvalue=u.value
                    global bestList 
                    bestList=u.ans[:]

                if u.bound<minvalue:
                    queue.put((u.bound,u))

    print "minValue",minvalue                
    return minvalue,bestList

solve_assignment(people_jobs)
comentou Mai 14, 2016 por CaioP (21 pontos)  
O algoritmo dessa resposta é baseado no desenvolvido em http://prorum.com/index.php/2470/resolver-problema-mochila-usando-tecnica-conhecida-branch.
comentou Mai 14, 2016 por CaioP (21 pontos)  
No caso particular desse problema, o critério para determinar se um determinado "caminho" é promissor é o mínimo das alocações com as quais é factível, supondo que os trabalhos possam ser alocados a mais de uma pessoa. Naturalmente essa suposição não se sustenta na resposta final, mas é um indicativo se a solução "tentative" é promissora e permite cortar ("prune") as que não o forem. Afinal, se nem com essa hipótese o caminho leva a uma solução melhor que a já identificada, que dirá sem ela.
...