Handige tips

Hoe een uitweg uit het doolhof te vinden

Pin
Send
Share
Send
Send




Van oudsher droegen labyrinten een gevoel van mysterie en mysterie. Een van de eerste labyrinten die de mensheid kent, beschrijft Herodotus - het was een Egyptisch labyrint waarin 5.000 kamers waren. Na verloop van tijd verloren de labyrinten hun religieuze en mystieke betekenis en werden ze objecten van amusement, die tuinen en parken veranderden in de vorm van groene hagen met een complexe configuratie.

Het oplossen van de doolhoven is altijd een fascinerende activiteit geweest, maar nog spannender is het maken van machines die door het labyrint kunnen gaan.

Een van de eenvoudigste regels om door een doolhof te gaan, is de regel met één hand: als je door een doolhof gaat, moet je de muur altijd met je rechter- of linkerhand aanraken. Dit algoritme was waarschijnlijk bekend bij de oude Grieken. Je moet een lange weg gaan, naar alle doodlopende wegen gaan, maar uiteindelijk zal het doel worden bereikt. Hoewel deze regel één nadeel heeft, zullen we er later over praten.

Laten we proberen een robot te beschrijven die handelt in overeenstemming met de regel van de "rechterhand".

Aan het begin van zijn werk moet de robot de muur vinden waarlangs hij zal volgen. Om dit te doen, kan hij eenvoudig vooruit gaan tot hij een obstakel tegenkomt.

Nadat de robot een obstakel is tegengekomen, begint hij te bewegen in overeenstemming met de regel van de "rechterhand".

Bewegend langs de muur, controleert de robot of er een doorgang aan de rechterkant is. Als er een doorgang is, moet de robot erlangs lopen om zichzelf niet van de muur naar rechts te scheuren.

Als er geen doorgang is - voor de muur - draait de robot naar links. Als er geen doorgang meer is, draait deze weer naar links, draait dus 180 graden en gaat in de tegenovergestelde richting.

Het blokdiagram van het algoritme voor een robot die werkt volgens de "rechterregel" wordt in de figuur getoond.


Laten we proberen de werking van dit algoritme te controleren en er een programma voor te schrijven. Voor dit doel wenden we ons tot de programmeeromgeving GameLogo. Deze omgeving is een handig hulpmiddel voor het modelleren van verschillende algoritmen met betrekking tot robotbesturing. Het heeft een uitvoerende schildpad, die in wezen niets meer is dan een echte robot. De schildpad heeft een zeer handige set commando's - vooruit, rechts, links, terug. Bovendien is er in het midden van de schildpad een sensor die een waarde van 0 tot 100 aanneemt, afhankelijk van de toon van het oppervlak waarop hij zich bevindt.

Het taaldialect van het logo dat we zullen gebruiken is heel eenvoudig en lijkt op Basic. U kunt hier kennis maken met de taalopdrachten. Een gratis download van de GameLogo-programmeeromgeving is hier. De grootte van de verdeling is klein - slechts 1 Mb.

In het archief met GameLogo zijn achtergronden met labyrinten, waarvan we er een zullen gebruiken.

Helemaal aan het begin van het programma geven we de opdracht aan de schildpad om de veer op te heffen (standaard laat de schildpad een spoor achter).

De grootte van het veld is 800 bij 600 pixels. De startpositie voor de schildpad bevindt zich op coördinaten 115, 545 (wit vierkant).

De kleur van de paden van het doolhof is licht, de sensor daarop heeft waarden groter dan 50. De kleur van de wanden van het doolhof is donker, de waarde van de sensor zal minder zijn dan 50. De uitgang van het doolhof wordt weergegeven door een zwart vierkant, de sensorwaarde erboven is 0.

We zullen een variabele vlag declareren, waarmee we zullen bepalen of de uitgang van het doolhof is bereikt.

We zullen het programma schrijven en starten met behulp van de grote rode knop met het opschrift "Uitvoeren".

Als bekend is dat het labyrint geen afzonderlijke muren heeft, dat wil zeggen dat er geen gesloten routes zijn waarlangs u kunt terugkeren naar het startpunt, dan wordt zo'n labyrint eenvoudigweg verbonden genoemd en kan het altijd volledig worden omzeild door de "one-handed" -regel toe te passen.

Als het labyrint vrijstaande muren bevat en vervolgens de regel met één hand toepast, is het niet altijd mogelijk om door alle gangen en doodlopende wegen te gaan. Labyrinten met afzonderlijke muren en met gesloten routes worden multiply connected genoemd. In dit geval kunnen de meervoudig verbonden labyrinten worden verdeeld in twee groepen: zonder een "lus" rond het doel (een gesloten route loopt niet rond het doel) en met een gesloten "lus" rond het doel (het doel kan worden omzeild door een gesloten route).

In de meervoudig verbonden labyrinten van de tweede groep werkt de regel met één hand niet en is het onmogelijk om het doel te bereiken. Maar zelfs deze labyrinten kunnen worden overwonnen door te vertrouwen op een exact algoritme.

De oplossing voor het probleem van dergelijke labyrinten behoort tot een relatief late tijd, en het begin werd gelegd door Leonard Euler. Euler geloofde niet zonder reden dat een uitweg uit een doolhof kan worden gevonden, en bovendien op een relatief eenvoudige manier.

Het universele algoritme voor het passeren van labyrinten werd pas een eeuw later beschreven in het boek van de Franse wiskundige E. Luke "Recreations matematiques", gepubliceerd in 1882. Interessant is dat Luke bij het beschrijven van het algoritme wees op het primaat van een andere Franse wiskundige M. Tremot. Zo werd het algoritme bekend als het Luc-Tremo-algoritme.

Tremo biedt de volgende regels: verlaat een willekeurig punt van het labyrint, maak een markering op de muur (kruis) en beweeg in een willekeurige richting naar een doodlopende weg of kruispunt, ga in het eerste geval terug, plaats een tweede kruis, wat aangeeft dat het pad twee keer is afgelegd - heen en weer , en ga in een richting die nog nooit is afgelegd of in de tweede - ga in een willekeurige richting, markeer elke kruising bij de ingang en uitgang met één kruis, als er al één kruis aan het kruis is, dan moet je een nieuwe weg gaan als niet t - dat doorkruiste pad, het markerend met een tweede kruis.

Als je het Tremo-algoritme kent, kun je het gedrag van de legendarische Theseus aanpassen. Geïnspireerd door het geschenk van zijn geliefde Ariadne, loopt hij vol vertrouwen door het doolhof. Plots is er een beweging waarlangs een draad al is uitgerekt. Wat te doen In geen enkel geval kruist u het, maar keert u terug op het reeds bekende pad, waarbij u de draad verdubbelt, totdat u nog een onvervulde beweging vindt.

Met behulp van een variant van het Tremo-algoritme bouwde de vader van de informatietheorie, Claude Elwood Shannon, een van de eerste zelflerende robots. Shannon gaf hem de sonore naam "Theseus", maar in de geschiedenis van "Theseus" is beter bekend geworden als de "muis" van Shannon. De "muis" onderzocht eerst het hele doolhof en ging toen (voor de tweede keer) veel sneller, en vermeed de gebieden die tweemaal werden gepasseerd.

Tegenwoordig nemen robots die door het labyrint gaan deel aan een van de meest interessante competities van denkmachines, die in verschillende landen van de wereld plaatsvindt. Deze competities worden gezamenlijk Micromouse-competitie genoemd en behoren tot de leiders van robotsporten in termen van hun technische innovaties.

Competities werden gehouden op de eerste Russische Olympiade van Robots, die bedoeld was om door een soort doolhof te gaan: in de kortste tijd, door de "open deuren" in de muren, moest de robot van het startpunt naar de finishplaats gaan. De robot kon zijn beweging besturen langs zwarte lijnen die op de vloer van het doolhof waren getekend.

REGEL VAN EEN HAND

Er is een heel eenvoudige manier om een ​​doolhof binnen te gaan zonder bang te zijn dat je erin verdwaalt. Met deze regel kunt u altijd een uitweg vinden uit elk labyrint, ongeacht hoe verward de overgangen zijn. Hier is de regel voor veilig wandelen in doolhoven:

Het is noodzakelijk om door het doolhof te lopen en de muur constant met dezelfde hand aan te raken.

Dit betekent dat je bij de ingang van het labyrint de muur met één hand (allemaal hetzelfde, rechts of links) moet aanraken en op het moment dat je erin wandelt de muur met dezelfde hand blijft aanraken.

Probeer - om deze methode uit te proberen - de "eenhandige regel" toe te passen voor een mentale wandeling langs het Hampton Maze-plan. Stel je gewapend met een lucifer voor dat je dit tuinlabyrint binnengaat en de hele tijd de muren met één hand aanraakt. Je komt vrij snel van de buiteningang naar het midden van het doolhof. Laat je hand hier niet zakken, blijf doorgaan en raak hem aan met de muren, en je komt weer nauwkeurig uit zijn hoekjes naar de buiteningang.

Waar komt deze handige regel vandaan? We zullen proberen dit te begrijpen. Stel je voor dat je geblinddoekt een kamer binnenkomt met slechts één ingang. Wat moet je doen om het allemaal te omzeilen en er weer uit te komen? De eenvoudigste manier is om langs de muren te lopen zonder je handen van de muur af te halen, dan zul je zeker de deur bereiken waardoor je bent binnengekomen. Hier is de rationaliteit van de "one-hand rule" vanzelfsprekend. Stel je nu voor dat de muren van de kamer uitsteeksels hebben, zoals getoond in Fig. 4 en 5. Voordat je geen eenvoudige kamers meer bent, maar echte doolhoven. Maar de "regel met één hand" moet natuurlijk en in deze gevallen zijn kracht behouden en u op betrouwbare wijze terugleiden naar de uitgang van het gebouw.

De "regel van één hand" heeft zijn ongemak. Als je het gebruikt, kun je elk labyrint betreden en er zeker uitkomen. Maar dit betekent niet dat je zonder uitzondering alle hoeken van het doolhof zult doorlopen. Je zult alleen die plaatsen bezoeken waarvan de muren op een of andere manier verbonden zijn met de buitenmuur van het labyrint - als het ware de voortzetting ervan. Maar je komt langs die delen van het labyrint waarvan de muren geen verbinding hebben met de buitenmuren. In het labyrint van de Hampton-tuin is er zo'n plek, en daarom kunt u, met behulp van de regel met één hand, niet alle paden van dit labyrint doorlopen: één pad blijft onbekend. In fig. 6 stippellijnen tonen het pad langs de wanden van de heg, als u de "regel met één hand" gebruikt, en de asterisk markeert die steeg, die tegelijkertijd onopgemerkt blijft.

Pin
Send
Share
Send
Send