Trova la prossima soluzione usando l'algoritmo di backtracking

2

Non spiegherò che cos'è il backtracking, Wikipedia l'articolo lo fa abbastanza bene.

Il solutore del backtracking viene solitamente implementato utilizzando la funzione ricorsiva che attraversa un albero di potenziali candidati che viene scoperto contemporaneamente.

Ora questa funzione può tornare presto quando trova la prima soluzione o attraversa l'intero albero e restituisce tutte le soluzioni contemporaneamente.

Ma cosa succede se voglio trovare la prima soluzione e poi magari chiedere la prossima?

Per quanto ne so, non esiste alcuna funzione nei linguaggi di programmazione comuni che consenta il ritorno della funzione e allo stesso tempo la possibilità di riprenderla in un secondo momento.

Suppongo che possa essere facilmente emulato con i thread:

  1. La funzione di risoluzione viene eseguita su un thread separato.
  2. Quando trova una soluzione lo memorizza in alcune variabili esterne e mette in pausa il thread (fondamentalmente il thread è usato per memorizzare uno stack di chiamate).
  3. Quando l'utente ha bisogno della prossima soluzione, riprende semplicemente il thread.

Purtroppo non tutti gli ambienti sono multi-thread. Cosa posso fare quando i thread non sono disponibili? Devo modificare la mia funzione per memorizzare in modo esplicito la copia di uno stack di chiamate che viene poi restituito con la soluzione e per ricreare manualmente l'albero di ricorsione quando viene chiamata la funzione per una prossima soluzione?

    
posta mrpyo 06.06.2016 - 22:19
fonte

2 risposte

5

Fortunatamente, c'è un approccio molto più semplice rispetto alla tua alternativa multi-threading: implementa il tuo backtracking usando code o stack, invece di ricorsività .

In questo caso, quando il tuo stato superiore è una soluzione, puoi restituirlo. E puoi riprendere il backtracking per trovare la soluzione successiva elaborando lo stato successivo in coda / in pila.

Questo articolo potrebbe interessarti: "Backtracking" Descrive la versione ricorsiva e non ricorsiva.

    
risposta data 06.06.2016 - 23:18
fonte
1

Potresti utilizzare un semi-co-routine o generatore . Non esistono in tutte le lingue e non sempre consentono direttamente la ricorsione. Ma la capacità di farlo e la disponibilità di semicoroutine non dipendono dalla disponibilità di thread (concessi, sono molto più facili da implementare con thread o fibre , quindi sono probabilmente più prontamente disponibili su alcuni piattaforme rispetto ad altre).

Questo è per gli scenari in cui le soluzioni sono esplorate in modo iterativo ma senza una particolare gerarchia. In questo caso ottieni una soluzione dopo l'altra e se il chiamante vuole la prossima soluzione, richiama semplicemente la funzione, che "ricomincerà" la ricerca.

Nella maggior parte dei casi hai uno scenario leggermente diverso in cui l'algoritmo di ricerca della soluzione esplora una parte (più o meno grande) dello spazio delle fasi e classifica le possibili soluzioni, restituendo il migliore secondo alcuni metrica. Chiamando di nuovo la funzione che non vuoi un'altra soluzione, vuoi il secondo migliore (e così via). In tal caso, tranne nei casi specifici in cui la struttura del problema potrebbe esserti d'aiuto, la funzione deve mantenere uno "stack" delle soluzioni trovate finora nel ramo di scelta corrente (invece di restituire semplicemente il migliore di un dato ramo di scelta), che complica in qualche modo i requisiti di memoria. Inoltre, la funzione dovrà restituire un array. Potrebbe essere necessario specificare la profondità dello stack restituito, ad esempio venti, e accettare di poter chiamare il semicoroutine diciannove volte al massimo, prima di ottenere un errore (o ottenere tutte e venti le soluzioni in un colpo solo, ma non di più). La routine dovrà anche unire e ordinare la pila dei suoi figli di chiamata (ad esempio in un albero, la ricorsione a sinistra restituirà venti soluzioni, la ricorsione giusta un'altra quindicina e il chiamante si unirà, ordinandole in una nuova pila di venti, e decidere se cederne uno o passare i venti indietro).

Potresti quindi finire (invece di ottenere la soluzione 1 nel tempo T, la soluzione 2 nel tempo 0,2T e così via) ottenendo venti soluzioni in 10 volte il tempo, cioè 10 volte è il tempo necessario per la restituzione della prima soluzione.

La soluzione di cui sopra può essere implementata più facilmente a partire da una funzione ricorsiva, invece di chiamare

var a := findSolution(phaseSpace)

avresti

var a[] := findSolutions(phaseSpace, 20)

Infine, in alcuni scenari la ricorrenza converge sulla soluzione migliore, e gli altri sono "lasciati indietro" in modo tale che non è facile recuperarli, né ci si può aspettare che salvi l'intero stato di stack della funzione per tutti i rami possibili. Per affrontare questo caso è necessario passare alla funzione ricorsiva un elenco di quelle soluzioni già restituite, che devono essere considerate come invalidate, e la funzione dovrà quindi ricominciare da capo ogni volta , ciascuna tempo potenzialmente esplorando diversi rami di scelta. E ottieni 20 soluzioni, ad esempio, 30 volte il tempo (ma il tempo per la prima soluzione è ancora 1T).

    
risposta data 06.06.2016 - 23:00
fonte

Leggi altre domande sui tag