Please enable JavaScript.

Coggle requires JavaScript to display documents.

M15 (Levitin) - Coggle Diagram

- - - - Backtracking
        
        Consiste na geração de conjuntos "candidatos" a solução, analisando-os um de cada vez e destrinchando em mais casos conforme a necessidade
        
        Dada uma "solução parcialmente construída", se for possível existir uma solução para o problema a partir desse conjunto, então é avaliado o subcaso viável mais próximo. Se não há como satisfazer o problema a partir desse subcaso candidato (por exemplo, ele já viola as restrições do problema), então nenhum subcaso deste precisa ser analisado, de maneira que o algoritmo retorna para o caso que lhe deu origem e analisa os seguintes possíveis subcasos
        
        Devido a essa relação de hierarquia entre casos e subcasos candidatos, é conveniente implementar o algoritmo como uma árvore enraizada, denominada state-space tree, em que a raiz representa o estado inicial antes de ser começada a análise de casos e cada nó é um caso tendo como filhos os seus subcasos. Ou seja, os filhos são nós cujos estados foram gerados de escolhas a partir do estado do nó pai. Porém, um novo filho só é gerado se e somente se não foram encontradas soluções suficientes a partir dos filhos anteriores
        
        Um nó é dito "promissor" se a partir dele ainda é possível encontrar um nó descendente que satisfaça o problema. Caso contrário, são chamados de "não promissores". Como a busca é realizada analisando preferencialmente o primeiro filho promissor de um nó analisado, até chegar em um descendente sem filhos promissores e retornar para seu pai (ou até encontrar um conjunto solução viável), essa busca é na prática um DFS sobre a state-space tree
        
        Dessa forma, as folhas são nós não promissores ou nós cuja união com seus antepassados representa um conjunto solução válido para o problema
        
        De maneira geral, a saída de um backtracking pode ser apresentada como um n-upla ordenada em que cada coordenada de índice i é um elemento de um conjunto o qual contém os outros possíveis candidatos para essa específica coordenada i
        
        Algumas informações adicionais relacionadas ao problema podem ser usadas de forma inteligente a fim de reduzir a quantidade de casos a serem analisados. Ou ainda, uma pré-estruturação da entrada pode permitir ao backtracking começar investigando os casos que tem mais chance de satisfazer os problema
  - - - Branch-and-Bound
        
        Analisa "candidatos" a solução, tal qual o backtracking, porém durante essa análise também é realizada comparações entre o resultado mais "otimizado" possível a partir de um estado e o resultado mais otimizado encontrado até então
        
        Semelhantemente ao backtracking, pode ser implementado como uma state-space tree, estruturada da mesma forma. No entanto, para um nó ser considerado promissor é necessário não só que seja possível gerar um descendente capaz de satisfazer o problema mas também que esse resultado seja mais otimizado que o resultado mais otimizado encontrado até então
        
        Além disso, diferentemente do backtracking, a ordem em que os nós são visitados geralmente não segue uma DFS, mas prioriza aqueles cujo valor esteja mais próximo de alcançar o resultado mais otimizado desejado. Por exemplo, se é um problema de minimização, pode-se visitar preferencialmente os nós com estados de menor valor, pois há uma maior expectativa que estas soluções parcialmente construídas levem a solução com menor valor de estado possível para aquela entrada. Nesse exemplo, a busca heurística usada é chamada "melhor-primeiro"
        
        Dessa forma, as folhas são nós que não eram promissores quando foram analisados, ou nós cuja união com seus antepassados representa um conjunto solução que fornece o valor mais otimizado desejado, ou ainda nós que não violam as restrições do problema, mas não apresentam o estado mais otimizado possível para a entrada
        
        Em alguns problemas específicos, como o problema da mochila, pode ser útil considerar cada nó interno promissor como possível solução para o problema, independente de seus subcasos filhos (pois para esse tipo de problema, por exemplo, um dos subcasos descendente é aquele em que mais nenhum elemento é adicionado a mochila). Com isso, demais nós podem ser mais rapidamente "exterminados" (ou pruned) da busca
        
        Muito mais do que no backtracking, é de extrema valia coletar informações adicionais a respeito do problema para reduzir radicalmente o tamanho da state-space tree. É de suma importância, por exemplo, a definição de limites iniciais a partir da entrada, mesmo que eles não representem os verdadeiros limites possíveis dadas as restrições do problema (algo que provavelmente irá ser descoberto pelo próprio algoritmo), o que chamado de função delimitadora
        
        Além disso, essa função delimitadora pode ser atualizada para cada nó promissor considerando seus subcasos restantes, ou ainda atualizada globalmente para todos os casos quando um caso mais otimizado é encontrado
        
        No entanto, é preciso que haja um certo balanceamento a fim de que as informações/funções extras não prejudiquem a complexidade computacional do algoritmo