Comprensione Backtracking in C ++

Question

Comprensione Backtracking in C ++

#1 da (9 voti)
#2 da (5 voti)

12

Ho una buona conoscenza di base dei fondamenti del C ++, ho anche una comprensione di come funziona anche la ricorsione. Ho trovato alcuni problemi come il classico otto problemi di regine e la risoluzione di un Sudoku con Backtracking.

Mi rendo conto che sono piuttosto persa quando si tratta di questo, non riesco a pensare al concetto di tornare nello stack di ricorsione e ricominciare da capo per risolvere il problema. Sembra facile con carta e penna, ma quando si tratta di scrivere codice per questo, sono confuso su come iniziare ad attaccare questi problemi.

Sarebbe utile se ci fosse un tutorial rivolto ai principianti per tornare indietro o se ci fosse un buon libro in cui questo era coperto. Se qualcuno può far luce su questo argomento o darmi qualche link a riferimenti decenti, sarei davvero grato.

E sì, so che sarebbe più facile nei linguaggi funzionali, ma mi piacerebbe capire l'implementazione anche in linguaggi imperativi.

recursion c++

posta nikhil 28.06.2011 - 23:23

fonte

2 risposte

5

Hai visto un programma per camminare su un albero binario, giusto? Assomiglia a questo:

void walk(node* p){
  if (p == NULL) return;  // this is backtracking
  else if (WeWin(p)){
    // print We Win !!
    // do a Throw, or otherwise quit
  }
  else {
    walk(p->left);   // first try moving to the left
    walk(p->right);  // if we didn't win, try moving to the right
                     // if we still didn't win, just return (i.e. backtrack)
  }
}

C'è il tuo backtracking.

In realtà non hai bisogno di un albero fisico. Tutto ciò di cui hai bisogno è un modo per fare una mossa e poi annullarlo, o dire se hai vinto, o dire se non puoi andare oltre.

risposta data 29.06.2011 - 00:13

fonte

Leggi altre domande sui tag recursion c++

Perché gli array di lunghezza variabile sono stati resi facoltativi in C 2011? Accesso ai repository dal dominio

score 9 · Accepted Answer

... I can't seem to be able to get my mind around the concept of going back in the recursion stack and starting again in order to solve the problem.

Nel backtracking, non stai ricominciando. Invece, si scorre su tutte le opzioni nella situazione attuale.

Pensa a trovare una soluzione per un labirinto. Ad un punto in cui hai due percorsi diversi, provi prima quello sinistro. Se quella sinistra non ti porta all'uscita, torni al punto e prova l'altro percorso. Ecco come funziona il backtracking. In 8 Q e altri problemi in cui è possibile utilizzare il backtracking, la parte confusa si trova nel dominio del problema: come eseguire iterazioni con le opzioni in una determinata situazione in modo deterministico.

EDIT : il seguente è uno pseudo codice che aiuta a comprendere il backtracking.

# depending on the problem, backtracking is not necessarily calling the
# method itself directly. for now, let's just stick with the simple case.

def backtracking(state)
  option_list = state.get_all_options
  option_list.each {|option|
    state.apply option
    return resolved if state.is_resolved
    return resolved if backtracking(state) == resolved
    state.undo option
  }
  return not_resolved
end

Per la domanda 8Q:

state.get_all_options restituirebbe una lista delle possibili posizioni per la prossima regina
state.is_resolved testerebbe se tutte le regine sono sulla scheda e se sono buone l'una con l'altra.
state.apply e state.undo modificheranno la scheda per applicare o annullare un posizionamento.