Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking, Onde se aplica, Características - Coggle Diagram
Backtracking
Backtracking é um algoritmo que busca, por força bruta, soluções possíveis para problemas computacionais.
De maneira incremental, busca por candidatos à soluções e abandona cada candidato parcial C quando C não pode resultar em uma solução válida.
Quando sua busca chega a uma extremidade da estrutura de dados, como um nó terminal de uma árvore, o algoritmo realiza um retrocesso tipicamente implementado através de uma recursão.
-
Características
-
-
Representam um ponto onde o algoritmo não pôde mais ir adiante (failure) sem ferir alguma pré-condição para que a solução gerada até então seja válida. Ex.: Caminho encontrado até agora é muito longo, embora ainda existam vértices por percorrer.
-
Dados do subconjunto de dados que ainda não forma incluídos na entrada são ótimos candidatos. Pode ser que todos sejam e pode existir uma restrição (constraint) reduzindo o número de candidatos.
O algoritmo pode tentar uma chamada recursiva para cada um dos candidatos (solução para pesquisa exaustiva). Ex.: O Caixeiro Viajante tenta todos os caminhos.
-
O processo de busca cria uma árvore de chamadas recursivas. Ex.: Todos os caminhos parciais do caixeiro viajante.