Alquimia e Otimizacao de Receitas - Calculo de Hidrogenio para Producao de Ouro

Os alquimistas se reúnem É época da Grande Convenção dos Alquimistas que acontece a cada 100 anos com muita festa palestras educativas brindes caldeirões borbulhantes e troca de receitas Como sempre o ponto alto da convenção é o jantar de gala onde há muita comilança e é concedido o grande prêmio da Asinha de Morcego Dourada para melhor ideia de receita para produzir ouro As receitas são simples elementos químicos devem ser transformados uns nos outros em várias quantidades até chegar a ouro Na verdade apenas parece simples pois todas as receitas começam com hidrogênio e vão usando quantidades diferentes para produzir outros elementos e assim por diante1 Enfim como as ideias de receitas geralmente fracassam com o passar dos séculos elas foram ficando mais e mais complicadas e o Conselho dos Alquimistas resolveu contratar você para automatizar o trabalho de analisálas e dizer algo muito simples quanto hidrogênio é necessário para realizar a receita Dá pra entender que eles tenham interesse em saber disso pois essa quantidade afeta diretamente os custos Hidrogênio é fácil de encontrar mas não é grátis A figura abaixo ilustra a receita que está ao lado onde os nodos representam os elementos e as quantidades de cada um estão anotadas nas arestas Seu algoritmo deve calcular e apresentar a quantidade de hidrogênio usada para produzir uma unidade de ouro Depois disso você deve entregar seu relatório descrevendo o problema sua solução os resultados para os casos de testes os tempos de execução dificuldades encontradas e conclusões Os alquimistas convencionais tentavam transformar chumbo em ouro mas essa ideia está ultrapassada faz tempo Ninguém mais fala nisso Os alquimistas se reúnem Descrição O problema no PDF fornecido descreve uma situação em que existem elementos que são matériaprima para outros elementos Para formar qualquer elemento que não seja o hidrogênio é necessário combinar 1 ou mais elementos com uma proporção específica O problema foi modelado utilizando um grafo direcionado com pesos nas arestas que representam a quantidade do elemento pai para formar o elemento filho A partir de um nó raiz pedese para calcular a quantidade deste elemento para formar o último elemento que é o ouro Solução Analisando a situação foi possível perceber que o ouro é o nó que possui grau de saída 0 ou seja nenhum elemento é formado a partir dele A partir do hidrogênio é possível formar qualquer elemento sendo então considerado o nó raiz Sabendo disso qualquer caminho que saia do hidrogênio e chegue até o ouro representa uma contribuição do hidrogênio para a formação do ouro por exemplo o caminho do hidrogênio passando pelo cádmio representa uma contribuição de 1x2x4x6 48 Para calcular o resultado total basta calcular a soma do peso de todos os caminhos que saem do hidrogênio e chegam ao ouro para isso foi utilizado o algoritmo Busca em Profundidade a partir do hidrogênio Segue o código abaixo escrito em C include vector include iostream include string include sstream include map include queue using namespace std int dfsint u int custo vectorvectorpairint int grafo if grafousize 0 return custo int c 0 for auto p grafou c dfspfirst custopsecond grafo return c int main mapstring int elementos vectorvectorpairint int grafo int qtdElementos 0 string linha while getlinecin linha string pai stringstream sslinha string filho int peso getliness pai extraindo string antes de ss peso filho if elementosfindfilho elementosend elementosfilho qtdElementos qtdElementos grafopushbackvectorpairint int stringstream ppai string no while p peso no if elementosfindno elementosend elementosno qtdElementos qtdElementos grafopushbackvectorpairint int grafoelementosnopushbackelementosfilho peso cout O custo do ouro é dfselementoshidrogenio 1 grafo endl return 0 Resultados Para o caso de teste fornecido no enunciado O resultado foi Tempos de execução Para a entrada fornecida que era muito pequena o tempo foi insignificante Mas o algoritmo de Busca Em Profundidade implementado percorre todos os caminhos da raiz ao nó folha portanto a complexidade é OVE onde V é o número de vértices e E é o número de arestas Dificuldades Encontradas Uma dificuldade foi decidir qual algoritmo utilizar Inicialmente foi pensado utilizar a Busca em Largura porém a forma como foi implementada não funcionou então foi necessário mudar a abordagem e pensar na Busca em Profundidade que modelada da forma correta forneceu o resultado esperado Conclusão O trabalho se mostrou relevante para melhor entendimento de como a Teoria dos Grafos pode ser aplicada a partir de um desafio de Algoritmos de Busca em Grafos Os alquimistas se reúnem Descrição O problema no PDF fornecido descreve uma situação em que existem elementos que são matériaprima para outros elementos Para formar qualquer elemento que não seja o hidrogênio é necessário combinar 1 ou mais elementos com uma proporção específica O problema foi modelado utilizando um grafo direcionado com pesos nas arestas que representam a quantidade do elemento pai para formar o elemento filho A partir de um nó raiz pedese para calcular a quantidade deste elemento para formar o último elemento que é o ouro Solução Analisando a situação foi possível perceber que o ouro é o nó que possui grau de saída 0 ou seja nenhum elemento é formado a partir dele A partir do hidrogênio é possível formar qualquer elemento sendo então considerado o nó raiz Sabendo disso qualquer caminho que saia do hidrogênio e chegue até o ouro representa uma contribuição do hidrogênio para a formação do ouro por exemplo o caminho do hidrogênio passando pelo cádmio representa uma contribuição de 1x2x4x6 48 Para calcular o resultado total basta calcular a soma do peso de todos os caminhos que saem do hidrogênio e chegam ao ouro para isso foi utilizado o algoritmo Busca em Profundidade a partir do hidrogênio Segue o código abaixo escrito em C include vector include iostream include string include sstream include map include queue using namespace std int dfsint u int custo vectorvectorpairint int grafo if grafousize 0 return custo int c 0 for auto p grafou c dfspfirst custopsecond grafo return c int main mapstring int elementos vectorvectorpairint int grafo int qtdElementos 0 string linha while getlinecin linha string pai stringstream sslinha string filho int peso getliness pai extraindo string antes de ss peso filho if elementosfindfilho elementosend elementosfilho qtdElementos qtdElementos grafopushbackvectorpairint int stringstream ppai string no while p peso no if elementosfindno elementosend elementosno qtdElementos qtdElementos grafopushbackvectorpairint int grafoelementosnopushbackelementosfilho peso cout O custo do ouro é dfselementoshidrogenio 1 grafo endl return 0 Resultados Para o caso de teste fornecido no enunciado O resultado foi Tempos de execução Para a entrada fornecida que era muito pequena o tempo foi insignificante Mas o algoritmo de Busca Em Profundidade implementado percorre todos os caminhos da raiz ao nó folha portanto a complexidade é OVE onde V é o número de vértices e E é o número de arestas Dificuldades Encontradas Uma dificuldade foi decidir qual algoritmo utilizar Inicialmente foi pensado utilizar a Busca em Largura porém a forma como foi implementada não funcionou então foi necessário mudar a abordagem e pensar na Busca em Profundidade que modelada da forma correta forneceu o resultado esperado Conclusão O trabalho se mostrou relevante para melhor entendimento de como a Teoria dos Grafos pode ser aplicada a partir de um desafio de Algoritmos de Busca em Grafos