Changes

Backtracking é um método que pode ser usado para achar soluções para resolver problemas que poderiam ser impráticos de se resolver solucionar usando técnicas de busca excessiva, . O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos como usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de , que consiste em posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em visa encontrar um subconjunto de um conjunto de inteiros cuja soma é um inteiro dado inteiro.

O primeiro problemas problema que nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde sendo n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudocódigo para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn: