LinhaDeMontagem_PD.py

LinhaDeMontagem_PD.py

def pd(processo,mudanca):
	
	linhas = len(mudanca)
	colunas = len(mudanca[0])
	nProcessos = len(processo[0])
	
	# Cria a matriz de custos
	custo = [[None for i in range(colunas)] for x in range(linhas)]
	# Cria a matriz de caminhos
	caminho = [[None for i in range(nProcessos)] for x in range(linhas)]
	
	# Inicio - Segue sempre este modelo
	custo[0][0] = mudanca[0][0] + processo[0][0]
	custo[1][0] = mudanca[1][0] + processo[1][0]
	
	# Meio - Processado usando PD (Programacao Dinamica)
	for j in range (1,nProcessos):
		for i in range(linhas):
			if (custo[i][j-1] + processo[i][j]) < (custo[1-i][j-1] + processo[i][j] + mudanca[1-i][j]):
				custo[i][j] = (custo[i][j-1] + processo[i][j])
				caminho[i][j-1] = i  ### Manteve a mesma linha de montagem
			else:
				custo[i][j] = (custo[1-i][j-1] + processo[i][j] + mudanca[1-i][j])
				caminho[i][j-1] = 1-i  ### Alterou a linha de montagem 
	
	# Fim - Segue sempre o mesmo modelo
	caminho[0][nProcessos-1] = 0
	caminho[1][nProcessos-1] = 1
	custo[0][colunas-1] = custo[0][colunas-2] + mudanca[0][colunas-1]
	custo[1][colunas-1] = custo[1][colunas-2] + mudanca[1][colunas-1]
	
	print("Matriz de Custos:\n",custo)
	print("Matriz de Caminhos:\n",caminho)

	return custo,caminho


def recuperaCaminho(custo,caminho):
	
	#Cria a lista de Melhor Caminho
	melhorCaminho = [None for x in range(len(caminho[0]))]
	
	pos = len(caminho[0])-1
	linha = 0 if (custo[0][len(custo[0])-1] < custo[1][len(custo[0])-1]) else 1

	while(pos>=0):
		melhorCaminho[pos] = linha
		pos -= 1
		linha = caminho[linha][pos]
		
	print("Melhor Caminho:\n",melhorCaminho)
	

def main():
	
	processo = [[7,9,3,4,8,4],[8,5,6,4,5,7]]
	mudanca = [[2,2,3,1,3,4,3],[4,2,1,2,2,1,2]]
	
	custo,caminho = pd(processo,mudanca)
	recuperaCaminho(custo,caminho)

if __name__ == '__main__':
	main()