Come implementare il backtracking per verificare se tutti i campi sono stati attraversati

Question

Come implementare il backtracking per verificare se tutti i campi sono stati attraversati

#1 da (1 voti)
#2 da (0 voti)

1

Ho imparato gli algoritmi e sto cercando di risolvere i problemi e ora ho il seguente problema:

In una matrice 4x4 e contiene campi con altezza. C'è un campo di inizio con una data altezza anche l'altezza massima che può avere un campo. Per poter passare da un campo all'altro, l'altezza del campo corrente deve essere maggiore o uguale al campo che vogliamo percorrere. Ci sono anche campi non contrassegnati senza altezza assegnata a loro, il che significa che possiamo cambiarlo. L'obiettivo è attraversare tutti i campi con una determinata altezza modificando l'altezza dei campi non marcati ? . Perché una soluzione conti come valida, tutto il dato ? deve avere un'altezza assegnata. Penso che questo richiederà la bruta forzatura di tutte le combinazioni possibili dei campi ? .

Esempio:

2 2
xx*x
x1?1
x?1x
xxxx

L'altezza minima che può avere un campo è 0. La prima cifra rappresenta l'altezza del * e il secondo, l'altezza massima che può avere un campo. Quindi * rappresenta il punto iniziale e ha altezza 2 (in questo caso abbiamo 2 come altezza massima), da lì dobbiamo passare agli altri campi con i numeri, cambiando il valore dei campi ? . Dobbiamo trovare quante varianti sono valide. In questo caso ci sono: 6. Poiché ? sulla 3a riga non ha importanza se viene attraversato o meno, ecco le soluzioni:

xx*x      xx*x      xx*x      xx*x     xx*x      xx*x     
x121      x121      x121      x111     x111      x111
x21x      x11x      x01x      x21x     x11x      x01x 
xxxx      xxxx      xxxx      xxxx     xxxx      xxxx

I nodi che contano sono stati attraversati in entrambi i casi. Usiamo Larghezza Prima ricerca per attraversare tutti i nodi. Il ? nella 3a riga non viene attraversato in alcuni casi perché questo campo non si trova nel gruppo dei campi obiettivo e la sua altezza non influisce sul raggiungimento di nessuno dei campi di destinazione.

algorithms

posta aurel 23.05.2016 - 00:57

fonte

2 risposte

Leggi altre domande sui tag algorithms

Dovremmo cercare di essere indipendenti dalla tecnologia il più possibile? Trovare le parole ambigue più lunghe con un determinato set di lettere

score 1 · Answer 1

Penso che mentre tenterai di descrivere la situazione in modo più chiaro, emergerà un approccio.

Il backtracking suddivide una ricerca (albero) in tracciati, che sono accettati, rifiutati o nessuno dei due. In entrambi i casi, continui a costruire un percorso più lungo; nel caso rifiutato "esegui il backup" per costruire ulteriormente sull'ultimo percorso non rifiutato.

Per utilizzare il backtracking, devi identificare le tue funzioni di accettazione e rifiuto. E, naturalmente, si deve anche identificare la funzione che si aggiunge al percorso, allungandolo di uno. Questa funzione richiederà uno stato per indicare quale delle prossime opzioni immediate ha già provato. Questo potrebbe essere semplice come un intero che indica il numero di figlio provato l'ultima volta (o da provare successivamente). Poiché avrai bisogno di questo stato in ogni nodo del percorso, avrai bisogno di una pila di qualche tipo per mantenere il percorso corrente (che indica anche ciò che è già stato e non è ancora stato cercato). L' articolo di Wikipedia mostra l'uso della ricorsione per questo, ma puoi usare invece uno stack esplicito.

Quindi, il nocciolo di ciò è che devi decomporre il tuo problema in parti più piccole, e se il backtracking è appropriato, questi pezzi più piccoli implicheranno chiaramente la possibilità di aggiungerne uno al percorso corrente, essere in grado di accettare ed essere in grado di rifiutare il percorso corrente.

Se la scomposizione non si adatta a questo, allora puoi usare qualcos'altro. Ad esempio, se non esiste una struttura di ricerca, ma piuttosto una semplice lista di ricerca, non è necessario utilizzare il backtracking (ma potresti farlo se hai insistito perché una lista è una forma di albero).

score 0 · Answer 2

Quanto segue non deve essere interpretato come una risposta adeguata alla tua domanda. Invece è un'eccezione alla tua domanda.

Sei stato molto bravo nel rispondere alle domande nei commenti ma anche dopo aver provato a mettere insieme le regole del tuo problema, non vedo come tu arrivi a queste 6 soluzioni. I problemi rimanenti vanno oltre ciò che posso spiegare in un campo di commento.

Ecco le regole che hai fornito (compresi i tuoi commenti) mentre le capisco:

Data la seguente griglia di altezze:

xx*x
x1?1
x?1x
xxxx

Ignora x. Iniziare a *. Supponiamo che l'altezza di * sia 2, la massima (si presume che 0 sia il minimo ma non lo si dichiari mai come una regola). L'obiettivo è visitare ogni campo che attualmente ha un valore di altezza numerico. La visita viene effettuata spostandosi dal campo al campo adiacente, in orizzontale o verticale. Puoi muoverti solo se la tua nuova altezza sarà inferiore o uguale alla tua vecchia altezza. Ovvero, lo spostamento segue queste regole di transizione:

Regole di transizione basate sull'altezza

Strumento grafico: illuminations.nctm.org

Una volta per soluzione, può essere scelta per ogni altezza, tra il minimo e il massimo (incluso)? campo. Questa scelta non ti obbliga a visitare il? campo.

Queste sono le regole del gioco perché le capisco. Non capisco appieno come producano queste 6 soluzioni:

Soluzioni fornite da OP (ricorda * = 2)

Cosanoncapisco:

Nellesoluzionida1a3,sevisitoABCcomefaccioaotteneredaCaE?QuandoBè2nonc'èmododivisitaretuttigli1.
PerchédovreipreoccuparmididareaFunvalorequandononlousoomiinteressavisitarlo.Sembrasolofarsaltareinariailnumerodisoluzionisenzaunabuonaragione.
Perché*nonpuòessereunnumero2.Sipuòsemplicementeaffermarechel'inizioèlaterzacolonnanellaprimariga.Saràunproblemacon*nellalogicadelcodice.

Lamiasoluzione

B=1eFèappenalasciatocome?dalmomentochenonènecessario.

OrapossiamovederecheBinEsono strongmente connessi . Poiché possono essere raggiunti dall'inizio (A), possono essere tutti visitati e contrassegnati. B non ha bisogno di essere contrassegnato ma non può ferire.

Riguardo a backtracking :

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

Per un esempio con queste poche altezze sconosciute con min e max entro 2 unità l'una dall'altra andrei solo con la forza bruta.

Probabilmente non è quello che vuoi sentire. In tal caso, considera di riscrivere la tua domanda con regole più precise e comprensibili. Sospetto che la risposta alla tua domanda stia nel formulare una "soluzione parziale per candidati". Il "test relativamente rapido" è probabilmente uno degli algoritmi menzionati nella pagina wiki strongmente connessa .

Se vuoi riscrivere completamente la tua domanda a questo punto, non ti biasimo. Sentiti libero di invalidare questa risposta se riesci a scrivere una domanda migliore. Lo eliminerò / modificherò e riproverò. A questo punto questo è il meglio che posso fare. Spero che almeno ti aiuti a migliorare la tua domanda.