Regola di una mano. Come trovare una via d'uscita dal labirinto Il risultato della procedura

Agli incroci, dare la preferenza ai sentieri non segnalati. Ogni volta che arrivi a un incrocio, prenditi un momento per guardare i segnali su ciascun sentiero. Alcuni di essi potrebbero non essere contrassegnati, mentre altri mostreranno che li hai già selezionati una (o due volte). Vale la pena dare la preferenza ai sentieri senza segni. In questo modo è più probabile che tu vada avanti. Se tutti i percorsi sono contrassegnati una volta, scegline uno a caso.

Evita i sentieri segnalati due volte. Se sei costretto a seguire un percorso che hai già segnato una volta, dovresti segnarlo una seconda volta. Secondo l'algoritmo Lucas-Tremaux, un sentiero a doppia marcatura non ti porterà all'uscita. Se trovi un incrocio in cui lo stesso percorso è segnato due volte, prendi sempre l'altro percorso, anche se ciò significa che devi tornare indietro.

Torna indietro se raggiungi un vicolo cieco. Se raggiungi un vicolo cieco, devi tornare all'ultimo incrocio che hai attraversato. Non dimenticare di segnare il percorso in modo da sapere che porta a un vicolo cieco. Una volta raggiunto il bivio, scegli uno dei restanti sentieri e prosegui nel labirinto.

Buon giorno, cara comunità.

sfondo

Un bel giorno, mentre camminavo su Internet, è stato trovato un labirinto. È diventato interessante scoprirne il passaggio e dopo aver girato per la rete, non ho ancora trovato un'implementazione software funzionante, una soluzione al labirinto.

Eccolo:

La giornata di lavoro era noiosa, l'atmosfera era eccellente. L'obiettivo, i mezzi e la volontà ci sono. La conclusione è ovvia, passeremo.

Storia

Per una soluzione conveniente, è necessario portare l'immagine esistente del labirinto al tipo di una matrice bidimensionale. Ogni elemento di cui può assumere uno di 3 valori:

COST MURO=-1; BIANCO=-2; DEADBLOCK=-3;

Innanzitutto, voglio mostrare le funzioni per la scansione dell'immagine del labirinto, seguita dalla scrittura dei dati nell'array e la funzione per generare una nuova immagine basata sui dati dell'array:

Scansione immagine:

varN:intero=600; LABIRINT:matrice di numeri interi; ... varbit:TBitmap; i,j:intero; bit di inizio:=TBitmap.Create; Se OpenDialog1.Execute inizia bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Gratuito; ... fine; fine; ...

Generazione di immagini:

varN:intero=600; LABIRINT:matrice di numeri interi; ... procedura genBitmap; varbit:TBitmap; i,j: intero; bit di inizio:=TBitmap.Create; bit.larghezza:=N+1; bit.Altezza:=N+1; for i:=0 to N do for j:=0 to N do inizia se LABIRINT=BLANK quindi bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL quindi bit.Canvas.Pixels:=clBlack else bit.Canvas .Pixel:=clRosso; fine; bit.SaveToFile("tmp.bmp"); bit.Gratuito; fine; ...

Innanzitutto, è necessario salvare nuovamente l'immagine come bmp monocromatico per avere 2 colori bianco o nero. Se guardi da vicino il labirinto, ha una parete spessa 2 pixel e una strada spessa 4 pixel. Sarebbe l'ideale per rendere lo spessore del muro e della strada 1 pixel. Per fare ciò, è necessario ricostruire l'immagine, dividere l'immagine per 3, ovvero rimuovere ogni 2a e 3a riga e colonna di pixel dall'immagine (questo non influirà sulla correttezza e passabilità del labirinto).

Disegno preparato:

Larghezza e altezza dell'immagine: 1802 pixel.

1. Utilizzare la funzione di scansione delle immagini.
2. Ricostruisci l'immagine:

varN:intero=1801; LABIRINT:matrice di numeri interi; ... procedura ricostruzioneArr2; var i,j:intero; inizia per i:=0 a ((N div 3)) do for j:=0 a ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; fine; ...

3. Generiamo l'immagine ricostruita.

Il risultato della procedura:

Larghezza e altezza dell'immagine: 601 pixel.

E così, abbiamo un'immagine di un labirinto del tipo desiderato, ora la cosa più interessante è la ricerca di tutte le opzioni per passare il labirinto. Cosa abbiamo? Un array con i valori scritti WALL - wall e BLANK - road.

C'è stato un tentativo fallito di trovare il passaggio del labirinto usando l'algoritmo delle onde. Perché senza successo, in tutti i tentativi questo algoritmo ha portato all'errore "Stack Overflow". Sono sicuro al 100% che usandolo, puoi trovare una procedura dettagliata, ma c'era una miccia per trovare qualcosa di più interessante.

L'idea non è venuta subito, ci sono state diverse implementazioni del passaggio, che nel tempo ha funzionato per circa 3 minuti, dopodiché è arrivata un'intuizione: "e se cercassimo non percorsi di passaggio, ma percorsi che non conducano al passaggio del labirinto e contrassegnarli come vicoli ciechi.

L'algoritmo è questo:
Esegui una funzione ricorsiva su tutti i punti stradali del labirinto:
1. Se siamo in piedi sulla strada e ci sono 3 muri intorno a noi, segnaliamo il punto in cui ci troviamo come un vicolo cieco, altrimenti usciamo dalla funzione;
2. Passiamo in un luogo che non è un muro dal punto n. 1 e ripetiamo il punto n. 1;

Implementazione del software:

varN:intero=600; LABIRINT:matrice di numeri interi; ... procedura setBlankAsDeadblockRec(x,y:intero); vark:intero; inizio:=0; se LABIRINT=vuoto allora inizia se LABIRINT<><><><>BIANCO quindi k:=k+1; se k=4 allora LABIRINT:=DEADBLOCK; se k=3 allora inizia LABIRINT:=DEADBLOCK; se LABIRINT=BLANK allora setBlankAsDeadblockRec(x-1,y); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x,y-1); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x+1,y); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x,y+1); fine; fine; fine; procedura setDeadblock; var i,j:intero; iniziare per i:=1 a N-1 fare per j:=1 a N-1 fare setBlankAsDeadblockRec(i,j); fine; ...

Conclusione

Ho un algoritmo funzionante "completo" che può essere utilizzato per trovare tutto il labirinto. Quest'ultimo ha superato tutte le aspettative in termini di velocità. Spero che il mio piccolo lavoro possa giovare a qualcuno o spingere a nuovi pensieri.

Codice del programma e labirinto passato:

//Per favore, non prendermi a calci per il linguaggio di programmazione che ho usato. unità Unità1; l'interfaccia utilizza Windows, grafica, moduli, finestre di dialogo, ExtCtrls, StdCtrls, controlli, classi; cost WALL=-1; BIANCO=-2; DEADBLOCK=-3; digitare TForm1 = classe(TForm) Button1: TButton; OpenDialog1: TOpenDialog; procedura Pulsante1Click(Mittente: TOggetto); privato (Dichiarazioni private) pubblico (Dichiarazioni pubbliche) fine; var Form1: TForm1; N:intero=600; LABIRINT:matrice di numeri interi; implementazione ($R *.dfm) procedura genBitmap; varbit:TBitmap; i,j: intero; bit di inizio:=TBitmap.Create; bit.larghezza:=N+1; bit.Altezza:=N+1; for i:=0 to N do for j:=0 to N do inizia se LABIRINT=BLANK quindi bit.Canvas.Pixels:=clWhite // else if LABIRINT=WALL quindi bit.Canvas.Pixels:=clBlack else bit.Canvas .Pixel:=clRosso; fine; bit.SaveToFile("tmp.bmp"); bit.Gratuito; fine; procedura ricostruzioneArr2; var i,j:intero; inizia per i:=0 a ((N div 3)) do for j:=0 a ((N div 3)) do LABIRINT:=LABIRINT; N:=N div 3; fine; procedura setBlankAsDeadblockRec(x,y:intero); vark:intero; inizio:=0; se LABIRINT=vuoto allora inizia se LABIRINT<>BIANCO quindi k:=k+1; se LABIRINT<>BIANCO quindi k:=k+1; se LABIRINT<>BIANCO quindi k:=k+1; se LABIRINT<>BIANCO quindi k:=k+1; se k=4 allora LABIRINT:=DEADBLOCK; se k=3 allora inizia LABIRINT:=DEADBLOCK; se LABIRINT=BLANK allora setBlankAsDeadblockRec(x-1,y); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x,y-1); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x+1,y); se LABIRINT=BLANK allora setBlankAsDeadblockRec(x,y+1); fine; fine; fine; procedura setDeadblock; var i,j:intero; iniziare per i:=1 a N-1 fare per j:=1 a N-1 fare setBlankAsDeadblockRec(i,j); fine; procedura TForm1.Button1Click(Mittente: TObject); varbit:TBitmap; i,j:intero; bit di inizio:=TBitmap.Create; Se OpenDialog1.Execute inizia bit.LoadFromFile(OpenDialog1.FileName); for i:=0 to N do for j:=0 to N do if bit.Canvas.Pixels=clWhite then LABIRINT:=BLANK else LABIRINT:=WALL; bit.Gratuito; setDeadblock; genBitmap; fine; fine; fine.

Per trovare il percorso più breve, si prevede di applicare l'algoritmo dell'onda ai passaggi trovati del labirinto. Sarebbe interessante sapere a cosa possono essere applicati altri algoritmi Presto trovare un modo in un grande labirinto?

Una delle regole più semplici per superare il labirinto è quella di "una mano": muovendoti nel labirinto devi sempre toccarne il muro con la mano destra o sinistra. Questo algoritmo era probabilmente noto agli antichi greci. Dovrai fare molta strada, andando in tutti i vicoli ciechi, ma alla fine l'obiettivo sarà raggiunto. Sebbene questa regola abbia uno svantaggio, ne parleremo più avanti.

Proviamo a descrivere un robot che agisce secondo la regola della "mano destra".

All'inizio del suo lavoro, il robot deve trovare un muro da seguire. Per fare ciò, può semplicemente andare avanti finché non incontra un ostacolo.

Dopo che il robot ha colpito un ostacolo, inizia a muoversi secondo la regola della "mano destra".

Muovendosi lungo il muro, il robot controlla se c'è un passaggio sulla destra. Se c'è un passaggio, il robot deve seguirlo per non staccarsi dalla parete di destra.

Se non c'è passaggio - c'è un muro davanti - il robot gira a sinistra. Se non c'è più passaggio, gira di nuovo a sinistra, girando così di 180 gradi, e va nella direzione opposta.

In figura è mostrato lo schema a blocchi dell'algoritmo per un robot operante secondo la regola della "mano destra".

Proviamo a controllare il funzionamento di questo algoritmo e scriviamo un programma per esso. A questo scopo, passiamo all'ambiente di programmazione. Questo ambiente è uno strumento utile per modellare vari algoritmi relativi al controllo dei robot. Ha una tartaruga esecutrice, che al suo interno non è altro che un vero robot. La tartaruga ha una serie di comandi molto comoda: avanti, destra, sinistra, indietro. Inoltre, al centro della tartaruga è presente un sensore che assume un valore da 0 a 100, a seconda del tono della superficie su cui si trova.

Il dialetto della lingua Logo che useremo è molto semplice e simile al Basic. Puoi familiarizzare con i comandi della lingua. Un download gratuito dell'ambiente di programmazione GameLogo - . La dimensione della distribuzione è piccola: solo 1 Mb.

L'archivio di GameLogo contiene sfondi con labirinti, uno dei quali utilizzeremo.

All'inizio del programma, daremo il comando alla tartaruga di alzare la piuma (per impostazione predefinita, la tartaruga lascia una scia dietro di sé).

La dimensione del campo è 800 x 600 punti. La posizione di partenza per la tartaruga è alle coordinate 115, 545 (quadrato bianco).

Il colore delle tracce del labirinto è chiaro, su di esse il sensore assumerà valori maggiori di 50. Il colore delle pareti del labirinto è scuro, il valore del sensore sarà inferiore a 50. L'uscita dal labirinto è rappresentata da un quadrato nero, il valore del sensore al di sopra del quale sarà uguale a 0.

Dichiariamo una variabile flag, con l'aiuto della quale controlleremo se è stata raggiunta l'uscita dal labirinto.

Scriviamo un programma ed eseguiamolo usando il grande pulsante rosso etichettato "Esegui".

Bandiera di sfondo variabile = maze1.gif alza il punto della penna 115, 545 "cerca il primo muro ripetere fino a calibro > 50 (avanti 12) "regola della mano destra ripetere fino a flag = 0 (destra 90 avanti 12 se sensore = 0 quindi flag = 1 altrimenti se sensore

Se è noto che il labirinto non ha muri separati, cioè non ci sono percorsi chiusi lungo i quali è possibile tornare al punto di partenza, allora tale labirinto si chiama semplicemente connesso e si può sempre aggirare completamente applicando il " regola con una mano”.

Se il labirinto contiene pareti autoportanti, allora, usando la regola "una mano", non è sempre possibile attraversare tutti i corridoi e i vicoli ciechi. I labirinti con pareti separate e percorsi chiusi sono chiamati moltiplicati collegati. Allo stesso tempo, i labirinti multipli collegati possono essere divisi in due gruppi: senza un "anello" attorno all'obiettivo (un percorso chiuso non passa attorno all'obiettivo) e con un "anello" chiuso attorno all'obiettivo (l'obiettivo può essere aggirato lungo un percorso chiuso).

Nei labirinti multiconnessi del secondo gruppo, la regola "una mano" non funziona e, utilizzandola, è impossibile raggiungere l'obiettivo. Ma anche questi labirinti possono essere superati basandosi su un algoritmo esatto.

La soluzione del problema di tali labirinti appartiene a un'epoca relativamente tarda e fu iniziata da Leonhard Euler. Eulero, non senza ragione, credeva che si potesse trovare una via d'uscita da qualsiasi labirinto, e per di più, in modo relativamente semplice.

L'algoritmo universale per attraversare qualsiasi labirinto fu descritto solo un secolo dopo nel libro del matematico francese E. Luc "Recreations matematiques", pubblicato nel 1882. È interessante notare che, nel descrivere l'algoritmo, Luca ha indicato il primato di un altro matematico francese, M. Tremaux. Pertanto, l'algoritmo divenne noto come Algoritmo Lucas-Tremo.

Tremo propone le seguenti regole: lasciando un punto qualsiasi del labirinto, devi tracciare un segno sul suo muro (croce) e spostarti in una direzione arbitraria verso un vicolo cieco o un incrocio; nel primo caso torna indietro, metti una seconda croce, indicando che il sentiero è stato percorso due volte - avanti e indietro, e vai in una direzione mai percorsa, né percorsa una volta; nel secondo - vai in una direzione arbitraria, segnando ogni incrocio all'ingresso e all'uscita con una croce; se c'è già una croce all'incrocio, allora dovresti prendere una nuova strada, in caso contrario, allora il sentiero percorso, segnandolo con una seconda croce.

Conoscendo l'algoritmo di Tremo, puoi correggere il comportamento del leggendario Teseo. Ispirato dal dono della sua amata Arianna, cammina con sicurezza attraverso il labirinto. Improvvisamente, gli appare davanti un passaggio, lungo il quale è già stato teso un filo... Cosa fare? In nessun caso non attraversarlo, ma tornare lungo il percorso già noto, raddoppiando il filo, fino a quando non ci sarà un altro movimento non percorso.

Utilizzando una variante dell'algoritmo Tremo, il padre della teoria dell'informazione, Claude Elwood Shannon, ha costruito uno dei primi robot ad autoapprendimento. Shannon gli diede il nome sonoro "Theseus", ma nella storia "Theseus" divenne meglio conosciuto come il "topo" di Shannon. Il "topo" ha prima esplorato l'intero labirinto e poi (per la seconda volta) è andato tutto molto più veloce, evitando sezioni che erano state superate due volte.

Alla prima Russian Robot Olympiad si svolgevano delle gare il cui scopo era di superare una sorta di labirinto: nel più breve tempo possibile, muovendosi attraverso le "porte aperte" nelle pareti, il robot doveva arrivare dall'inizio alla finire. Il robot poteva controllarne il movimento lungo le linee nere disegnate sul pavimento del labirinto.

Questa immagine sta circolando ora su Internet. Questo è spesso accompagnato dal seguente testo: L'intelligence militare israeliana ha un'unità speciale in cui prestano servizio ragazzi e ragazze, affetti da vari disturbi dello spettro autistico. Le persone autistiche analizzano principalmente mappe e fotografie aeree che appaiono sugli schermi dei computer. A causa delle peculiarità del loro pensiero, prestano attenzione ai minimi dettagli, la cui considerazione nella preparazione delle operazioni militari a terra consente di prevenire possibili perdite di personale. In questo modo, gli esploratori autistici salvano la vita dei soldati".

Hai provato questo labirinto?

Scopriamo di più su questo problema.

anche alla menzione di questo labirinto si precisa che " Una persona autistica è in grado di elaborare informazioni visive e testuali molte volte più velocemente di una persona che non soffre di disturbi dello spettro autistico. Questa loro caratteristica si è rivelata indispensabile nell'alta tecnologia. Presso Specialisterne, una società di consulenza tecnologica danese, il 75% dei suoi dipendenti è autistico e ha la sindrome di Asperger, anch'essa nello spettro dell'autismo. Si differenziano dai normali lavoratori per la loro incredibile attenzione ai dettagli, concentrazione sovrumana e capacità di elaborare rapidamente enormi quantità di informazioni. Queste abilità sono particolarmente utili per i tester di software. La qualità del lavoro delle persone autistiche impegnate in questo lavoro è molte volte superiore alla qualità del lavoro della gente comune. Le persone autistiche possono controllare 4.000 pagine di documentazione tecnica 10 volte più velocemente delle persone normali e non sbagliare mai un solo errore".

Ma lasciamo da parte le persone autistiche e scopriamo alla fine come puoi superare questo labirinto! Ecco come...

Il compito è irrisolvibile! Abbiamo 3 stanze con un numero dispari di porte (analogia con i disegni "senza alzare la matita"). Affinché il problema abbia una soluzione, è necessario che non ci siano più di 2 punti (nel nostro caso, stanze) con un numero dispari di righe (nel nostro caso, passaggi)

Se costruiamo un grafico di questo labirinto, vedremo che questo è il percorso di Eulero, poiché ha 3 vertici con un numero dispari di archi (porte), e possono essercene solo due per soddisfare le condizioni di test.

Il problema dei sette ponti di Königsberg o Il problema del ponte di Königsberg(Tedesco Konigsberger Brucken problema) è un vecchio problema matematico che chiedeva come fosse possibile attraversare tutti e sette i ponti di Königsberg senza attraversarne nessuno due volte. Fu risolto per la prima volta nel 1736 dal matematico tedesco e russo Leonhard Euler.

Per molto tempo, un tale enigma è stato comune tra gli abitanti di Königsberg: come attraversare tutti i ponti (attraverso il fiume Pregolya) senza attraversarne nessuno due volte. Molti Königsberger hanno cercato di risolvere questo problema sia teoricamente che praticamente durante le passeggiate. Tuttavia, nessuno potrebbe provare o smentire la possibilità dell'esistenza di un tale percorso.

Nel 1736, il problema dei sette ponti interessò l'eminente matematico, membro dell'Accademia delle scienze di San Pietroburgo, Leonhard Euler, di cui scrisse in una lettera del 13 marzo 1736 al matematico e ingegnere italiano Marioni. In questa lettera, Eulero scrive di essere riuscito a trovare una regola con la quale è facile determinare se è possibile passare su tutti i ponti senza superarne nessuno due volte. La risposta è stata "no".

In un diagramma semplificato, parti della città (grafico) corrispondono a ponti con linee (archi del grafico) e parti della città corrispondono a punti di connessione di linee (vertici del grafico). Nel corso del ragionamento, Eulero è giunto alle seguenti conclusioni:

• Il numero di vertici dispari (vertici a cui conduce un numero dispari di archi) deve essere pari. Non può esistere un grafo che abbia un numero dispari di vertici dispari.


• Se tutti i vertici del grafico sono pari, puoi disegnare un grafico senza sollevare la matita dal foglio e puoi iniziare da qualsiasi vertice del grafico e terminarlo nello stesso vertice.


• Un grafico con più di due vertici dispari non può essere disegnato con un solo tratto.

La teoria dei grafi creata da Eulero ha trovato un'applicazione molto ampia nei sistemi di trasporto e comunicazione (ad esempio, per studiare i sistemi stessi, compilare percorsi ottimali per la consegna di merci o instradare dati su Internet).

Nel 1905 fu costruito il Ponte Imperiale, poi distrutto durante i bombardamenti della seconda guerra mondiale. C'è una leggenda secondo cui questo ponte fu costruito per ordine dello stesso Kaiser, che non riuscì a risolvere il problema dei ponti di Königsberg e rimase vittima di uno scherzo giocato con lui dalle menti dotte che erano presenti al ricevimento secolare (se si aggiunge l'ottavo ponte, allora il problema diventa risolvibile). Il Ponte del Giubileo è stato costruito sui supporti del Ponte Imperiale nel 2005. Al momento ci sono sette ponti a Kaliningrad e il grafico costruito sulla base delle isole e dei ponti di Kaliningrad non ha ancora un percorso di Eulero

Ecco un'altra soluzione offerta da xlazex

Diamo un'occhiata alla foto 1: circonderemo ogni parte separata con quadrati, escluderemo i punti "extra", ad es. quei punti, il cui uso aumenterebbe il numero possibile di percorsi, e la cui esclusione non influirà sul numero di porte attraversate dalla linea e sulla chiusura del contorno. Per l'inizio del percorso, prendi, ad esempio, il punto 2 .
Diamo un'occhiata alla foto 2: su di essa ho rappresentato lo stesso contorno, ma in modo tale che i collegamenti del punto di partenza con quelli successivi fossero più visibili. L'immagine mostra chiaramente che la parte del contorno delineata in blu non può essere chiusa una volta, ad es. anche se questa parte del contorno fosse l'unica, non ci sarebbero percorsi lungo i quali sarebbe possibile costruire una linea chiusa.
In conclusione: il problema non ha soluzione in un sistema di coordinate bidimensionale.

Ma c'è una soluzione in 3D :-)

Va bene, scherzo, scherzo...