Doolhof-algoritme

[Lord Daemon]

Ik kreeg gisteren op onverklaarbare wijze de volgende gedachte:

Stel, je neemt alle binaire gehele getallen (0, 1, 10, 11, 100, 101, 110, 111, 1000, ...) en zet deze achter elkaar. Je krijgt dan een reeks van 1'en en 0'en die als volgt begint: 0110111001011101111000...

Nu vervang je elke 0 door de 'L' van 'Links' en elke 1 door de 'R' van 'Rechts'. Je krijgt dan een opnieuw reeks die als volgt begint: LRRLRRRLLRLRRRLRRRRLLL...

Deze reeks wordt nooit periodiek, dat is het belangrijke aspect ervan.

Neem nu een eindig, twee-dimensionaal doolhof, waarvan alle stukken met elkaar verbonden zijn. (Het is dus in principe mogelijk van elk punt naar elk ander punt te komen.) Stel nu dat je op een willekeurig punt in dit doolhof begint te lopen. Elke keer dat je een kruispunt tegenkomt, kijk je in de reeks. Als er een L staat neem de je de meest linkse weg, als er een R staat neem je de meest rechtse weg. (Als je op een doodlopend punt bent - een 'kruispunt' met 1 uitgang - staan 'L' en 'R' allebei voor omdraaien en terug lopen.) Dan schuif je de reeks 1 stapje op, zodat je bij het volgende kruispunt het volgende getal neemt.

Mijn stelling is: met dit algoritme vindt je altijd binnen eindige tijd de uitgang.

Ik heb hier alleen geen mathematisch bewijs voor. De 'logica' erachter is dat de reeks nooit periodiek wordt, en je dus nooit - lijkt mij - in 1 stuk van het doolhof vast kan komen te zitten. Immers, er moet altijd een 'ontsnappingpunt' R zijn van waaruit je naar een ander stuk van het doolhof kan komen als je uit een bepaalde richting Q1 of Q2 komt, en elke keer als je vanuit Q1 of Q2 bij R aan komt kan je een 'L' of een 'R' hebben. Het lijkt mij dat de niet-periodiciteit ervoor zorgt dat je uiteindelijk altijd een L of een R zal krijgen, afhankelijk van wat je nodig hebt.

Maar dat is niet echt een bewijs, meer een intuitie. Is er iemand die mijn stelling kan bewijzen dan wel ontkrachten?

En minstens even leuk: is er iemand die een sneller algoritme kan verzinnen? Het moet gegarandeerd een oplossing opleveren binnen een eindige tijd, en je mag geen 'kaart' van het doolhof tekenen. Laten we zeggen dat de enige info die je krijgt steeds een getal is dat aangeeft hoeveel wegen er uit het kruispunt gaan. (N = 1, 3, 4, ... ; niet 2, want dat is gewoon een recht stuk.)

[ReallyStupidGuy]

Ik denk dat om uit een doolhof te komen je het beste 1 muur kunt volgen.

Voor een algoritme betekend dat dus dat als het mogelijk is je naar links gaat, zoniet rechtdoor, zoniet rechts, zoniet terug.

Of jou idee werkt?

Ik denk het wel, maar je kan wel errug lang vast zitten in een stukje van het doolhof.

[Anoniem: 22342]

Ik denk dat het weinig met elkaar te maken heeft. Je zult uiteindelijk wel altijd een eind vinden. Er is geen mathematische filosofie aan verbonden denk ik

[Varienaja]

Je algoritme, gebaseerd op een niet-periodieke reeks, is in feite een 'random' algoritme.

Neem bijvoorbeeld het fantastische 'random-sort'. Je neemt de input, zet het in een willekeurige volgorde, kijkt of het alfabetisch is, zoja dan ben je klaar; zonee, dan begin je opnieuw.

De complexiteit van dit algoritme is van orde(oneindig). Het kan na 1 stap klaar zijn, maar ook na oneindig stappen.

Ieder ander algoritme zal minder complex (dus sneller) zijn dat het jouwe.

Op zondag 30 juni 2002 22:26 schreef ReallyStupidGuy het volgende:
Ik denk dat om uit een doolhof te komen je het beste 1 muur kunt volgen.

code:

------------------------
|          
|   -------     |-------
|   |     |     |
| ^ |     |     |
| | -------     |
|          |
-----------------

En dan ga je hier voor de grap eens continu rechtsaf

[Lord Daemon]

Op zondag 30 juni 2002 22:26 schreef ReallyStupidGuy het volgende:
Ik denk dat om uit een doolhof te komen je het beste 1 muur kunt volgen.

Voor een algoritme betekend dat dus dat als het mogelijk is je naar links gaat, zoniet rechtdoor, zoniet rechts, zoniet terug.

Nee, dat werkt niet. Je begint op een willekeurige plaats in het doolhof. Als het doolhof 'eilanden' bevat, en je volgt 1 muur van zo'n eiland, loop je de hele tijd cirkels en kom je nooit bij de utigang (tenzij die naast het eiland ligt). Jouw taktiek werkt wel als je een ingang en een uitgang hebt die allebei aan de rand van het doolhof liggen, maar dat heb ik hier niet gegeven.

Ik denk het wel, maar je kan wel errug lang vast zitten in een stukje van het doolhof.

Ja, maar hopelijk wel maar eindig lang.

Op zondag 30 juni 2002 22:28 schreef Araneae het volgende:
Ik denk dat het weinig met elkaar te maken heeft. Je zult uiteindelijk wel altijd een eind vinden. Er is geen mathematische filosofie aan verbonden denk ik

Wat bedoel je? Als je willekeurig rond gaat lopen heb je geen garantie dat je ooit de uitgang vindt. Dat lijkt me dus geen correct algoritme.

[Lord Daemon]

Op zondag 30 juni 2002 22:30 schreef Varienaja het volgende:
Je algoritme, gebaseerd op een niet-periodieke reeks, is in feite een 'random' algoritme.

Nee. Een volledig random-algoritme kan, in principe, beginnen met een oneindig aantal maal 'L'. Je hebt geen garantie dat dit niet zo is.

De complexiteit van dit algoritme is van orde(oneindig). Het kan na 1 stap klaar zijn, maar ook na oneindig stappen.

Als je mij kan laten zien dat het mogelijk is dat het oneindig stappen duurt, gooi ik mijn algoritme het raam uit.

[Confusion]

Lord Daemon schreef:
Mijn stelling is: met dit algoritme vindt je altijd binnen eindige tijd de uitgang.
[..]
Maar dat is niet echt een bewijs, meer een intuitie. Is er iemand die mijn stelling kan bewijzen dan wel ontkrachten?

Vanaf een bepaald punt, zou je altijd de uitgang vinden als je de deelreeksen afzonderlijk zou uitproberen (waarbij alle 'te korte' reeksen automatisch niet tot de uitgang leiden), omdat je in essentie alle mogelijke permutaties van L en R van reeksen met willekeurige lengte gaat proberen.

Ik kan niet goed overzien of dit ook opgaat wanneer de beginplaats voor een deelreeks telkens verandeert (doordat je dus eerst een andere deelreeks uitvoert), maar ik denk het wel, omdat elke deelreeks die geweest is later weer terugkomt in een langere deelreeks. Op een zeker moment heb je vanaf iedere plek iedere deelreeks < x geprobeerd (waarbij je dan de reeks met lengte x^(aantal kuispunten) ofzo aan het proberen bent).

Ik heb het gevoel dat je gelijk hebt en dat deze reeks betreffende dit probleem wel random is, omdat elke mogelijke permutatie van L en R uiteindelijk vanaf iedere plek in het doolhof geprobeerd zal zijn. Ik sluit niet uit dat er een soort anti-algoritme verzonnen kan worden, volgens welke het doolhof gemaakt kan worden, omdat het algoritme niet daadwerkelijk random is. Mijn pogingen met een 4x4 doolhof met 1 uitgang werden echter altijd opgelost net

[Varienaja]

Op zondag 30 juni 2002 22:34 schreef Lord Daemon het volgende:
Nee. Een volledig random-algoritme kan, in principe, beginnen met een oneindig aantal maal 'L'. Je hebt geen garantie dat dit niet zo is.

Ok, random <> niet-periodiek.

Ik heb grafentheorie gehad. Stel je een doolhof voor als een graaf, waarbij het gewicht van lijn de lengte voorstelt van punt a tot punt b. Met behulp van het kortste-pad-algoritme kan je heel vlot uitrekenen wat de kortste weg van de ingang naar de uitgang van het doolhof is.

In jouw situatie weet je niets van het doolhof en omdat je geen kaart mag maken, mag je dus ook niets onthouden (kortste-pad-algoritme valt hierbij af). Om dan nog steeds naar buiten te kunnen komen moet je bij elk keuzemoment dus 'zomaar wat' doen, maar om te voorkomen dat je in een oneindige lus terechtkomt moet je wel iedere keer wat anders doen. Daaruit volgt dan inderdaad dat je een niet-periodieke reeks nodig hebt.

De complexiteit is dan van grote orde(nⁿ), waarbij n het aantal punten van je graaf (keuzemomenten in je doolhof) voorstelt. 'Grote orde' betekent dat de opgegeven waarde een bovengrens aangeeft. Het kan zijn dat je de oplossing eerder vindt.

Zonder kennis over het doolhof op te slaan, is het volgens mij niet mogelijk om dit efficiënter te doen.

[Lord Daemon]

Op zondag 30 juni 2002 22:52 schreef Varienaja het volgende:
In jouw situatie weet je niets van het doolhof en omdat je geen kaart mag maken, mag je dus ook niets onthouden

Nee, je mag wel wat onthouden! Je mag zelfs twee reeksen onthouden, X_n en Y_n. Hierbij is X steeds een getal dat aangeeft welke weg je in bent geslagen (meest links is 1, volgende is 2, etcetera), en Y is het aantal wegen van het kruispunt.

Ik gebruik Y niet in mijn algoritme, maar dat mag dus wel.

[Yoozer]

ik denk dat het interessant is om op een of andere manier een dergelijk doolhof te genereren - ook, volledig random. je moet wel in de gaten houden dat je reeks bij 2^n-getallen bijvoorbeeld n maal 0 of 1 kan bevatten - dus een paar honderd keer naar links, of naar rechts - wat dus ad infinitum gewoon een herhalende reeks zou worden. wat je wel zou kunnen doen is op basis van een transcedent getal (pi/e) een algoritme kunnen schrijven - pi is namelijk een goede pseudorandom generator.

vooralsnog lijkt het me niet zinnig een doolhofalgoritme te schrijven zonder een mate van geheugen - al is het maar 'waypoints' om complex in-de-rondte-draaien te voorkomen. op dergelijke kruispunten en t-splitsingen zou het niet verboden moeten worden een merkteken aan te brengen bestaande uit het kruispunt-nummer (een simpele counter per kruispunt), en een 'vorige beslissing' - als blijkt dat men na een cirkelgang weer op een kruispunt uitkomt, moet men natuurlijk een andere beslissing nemen.

[Lord Daemon]

Op zondag 30 juni 2002 23:05 schreef Yoozer het volgende:
vooralsnog lijkt het me niet zinnig een doolhofalgoritme te schrijven zonder een mate van geheugen

Ik heb al eerder gezegd: je hebt geheugen in de vorm van de hierboven gedefinieerde reeksen X en Y. Daar kan je vast iets mee.

Als je markers neer mag gaan zetten is het simpel. Het is dan bijna triviaal om een algoritme te bepalen waarme je een doolhof altijd uitspeelt. Ik had ooit een spelletje dat ultiem grote doolhoven kon genereren, met 3 verdiepingen. Daar mocht je met je muis doorheen lopen, en je musi liet een spoor van 'broodkruimeltjes' na. Het was zeer gemakkelijk om elk doolhof uit te spelen - het koste wel veel tijd, maar goed.

[Anoniem: 958]

Ik geloof dat ik wel een redelijk intuitief bewijs heb verzonnen . Het bewijs gaat als volgt:

Nummer de plaatsen waar je kan zijn met 1, 2, 3 etc.. Dezelfde plaatsen, maar waar je met je neus een andere kant op staat, krijgen ook een apart nummer.
Er is een rij van L-en en R-en om vanuit 1 naar de uitgang te komen. Noem deze weg met x_1.

Als je begint in 1 dan is x_1 de juiste weg. Als je echter in 2 begint, dan kom je na het volgen van de instructies van x_1 over het algemeen ergens anders uit, zeg in y. Er is ook een rij instructies om van y naar de uitgang te komen. Noem die rij x_2 en zet deze rij achter de rij instructies x_1 en je hebt een rij instructies x_1 x_2 die zowel vanuit 1 als vanuit 2 werkt.

Stel nu dat je in 3 begint. Volg vanuit 3 de rij instructies x_1 x_2 en kijk waar je uitkomt, zeg in z. Er is nu wederom een rij instructies om vanuit z naar de uitgang te komen. Noem die rij x_3 en plak hem achter x_1 x_2 om een rij te krijgen die vanuit 1, 2 en 3 werkt.

Herhaal dit net zolang tot je alle plekken in het doolhof gehad hebt. Je hebt nu een rij instructies die je vanuit ieder willekeurig punt in het doolhof naar de uitgang leidt. Deze rij instructies komt overeen met een binair getal, dus zal altijd een keer voorkomen als je alle binaire getallen afloopt.

[Lord Daemon]

* Applaus *

Wat een mooi bewijs!

[Varienaja]

Op zondag 30 juni 2002 22:56 schreef Lord Daemon het volgende:
Nee, je mag wel wat onthouden! Je mag zelfs twee reeksen onthouden, X_n en Y_n. Hierbij is X steeds een getal dat aangeeft welke weg je in bent geslagen (meest links is 1, volgende is 2, etcetera), en Y is het aantal wegen van het kruispunt.

Ik gebruik Y niet in mijn algoritme, maar dat mag dus wel.

Daar heb je geen fluit aan, want je mag niet 'een streepje op de muur tekenen', zodat je weet waar je al geweest bent. Met die X_n en Y_n reeksen kan je eventueel teruggaan naar waar je vandaan kwam, maar je kan er niet een 'kaart' mee maken.

kaart == korste-pad-algoritme, geen kaart == zomaar wat doen.

Je hebt dus gelijk dat je 'iets' mag onthouden, maar je hebt volgens mij geen gelijk dat je daarmee dan een sneller algoritme kunt bedenken. (Met sneller bedoel ik: van een lagere orde)

[Lord Daemon]

Op zondag 30 juni 2002 23:13 schreef Varienaja het volgende:
kaart == korste-pad-algoritme,

Nee. Het kortste-pad algoritme gaat er van uit dat je de hele kaart aan het begin al weet, terwijl in een doolhof geldt dat op het moment dat je de hele kaart hebt geexploreerd, je sowieso bij de uitgang bent geweest en dus al hebt gewonnen. Aan het kortste-pad algoritme heb je dus niets.

geen kaart == zomaar wat doen

Kan je dat bewijzen?

[RickN]

De reeksen x en y die je hebt gedefineerd geven je teveel informatie om het te kunnen vergelijken met het algoritme dat jij voorstelt. Alleen reeks y, plus voor elk kruispunt waar ik aankom informatie over het aantal wegen van dat kruispunt (dus niet eens een reeks zoals x) geven me genoeg informatie om een kaart van dat deel van het doolhof waar je al bent geweest te reconstrueren. Je reeks y is dus niets anders dan een (bijzonder inefficiente) manier om een kaart van het doolhof op te slaan, terwijl dat juist niet je bedoeling was.

[Yoozer]

het 'zomaar wat doen' kan ook resultaten opleveren.

OT : heeft trouwens iemand 'the cube' gezien? daar heb je nog eens 'n doolhof dat lastig te kraken is.

verder zit je ook aan de fysieke limiet. sandalf's bewijs is erg mooi, maar niet als je er 40GB voor nodig hebt om het op te slaan. verder wil ik graag weten of zijn bewijs in gemodificeerde vorm ook werkt in een 3-dimensionaal doolhof (wat hoogstwaarschijnlijk niet het geval is omdat je dan op z'n minst 6 keuzes moet hebben), en hoe je het dan zou moeten ombouwen.

[RickN]

Op zondag 30 juni 2002 23:20 schreef Yoozer het volgende:
verder zit je ook aan de fysieke limiet. sandalf's bewijs is erg mooi, maar niet als je er 40GB voor nodig hebt om het op te slaan.

Je begrijpt het niet. Het is niet de bedoeling dat je Sandalfs recept echt gaat opvolgen, het is alleen een bewijs dat er een reeks instructies bestaat die vanuit elke positie naar de uitgang leidt. Daarnaast is het triviaal om te laten zien dat elke reeks instructies voorkomt in Lord Daemons reeks en dus lost Lord Daemon's algoritme elk doolhof op.

verder wil ik graag weten of zijn bewijs in gemodificeerde vorm ook werkt in een 3-dimensionaal doolhof (wat hoogstwaarschijnlijk niet het geval is omdat je dan op z'n minst 6 keuzes moet hebben), en hoe je het dan zou moeten ombouwen.

Daar werkt het ook voor.

[Lord Daemon]

Op zondag 30 juni 2002 23:19 schreef RickN het volgende:
Je reeks y is dus niets anders dan een (bijzonder inefficiente) manier om een kaart van het doolhof op te slaan, terwijl dat juist niet je bedoeling was.

Nee. Stel, X is: L, L, L, L. Y is: 4, 4, 4, 4.

Je kunt nu concluderen dat je een vierkantje hebt gelopen.

Dit zou waar kunnen zijn. Het zou ook onwaar kunnen zijn. Je hebt namelijk geen info over de hoeken waaronder de wegen staan (let wel: L betekent 'neem de meest linkse weg, dus niet 'ga 90 graden naar links') en de lengte van de wegen. Je kan dus geen kaart construeren.

Op zondag 30 juni 2002 23:20 schreef Yoozer het volgende:
verder zit je ook aan de fysieke limiet. sandalf's bewijs is erg mooi, maar niet als je er 40GB voor nodig hebt om het op te slaan.

Dit is wiskunde - het gaat niet om praktische oplossingen. Toch? "Theoretical mathematics... may it never be of any use to anyone!"

verder wil ik graag weten of zijn bewijs in gemodificeerde vorm ook werkt in een 3-dimensionaal doolhof (wat hoogstwaarschijnlijk niet het geval is omdat je dan op z'n minst 6 keuzes moet hebben), en hoe je het dan zou moeten ombouwen.

Ja. Neem ipv L en R acht verschillende mogelijkheden: LO, LB, RO, RB, OL, OR, BL, BR. BL staat bijvoorbeeld voor: neem de uitgang die het meest rechtsboven zit; is die er niet, dan de uitgang die het meest boven zit; is die er niet, dan de uitgang die het meest rechts zit. (Dit zou op elk kruispunt een beslissing moeten opleveren.) Neem ipv een 2-tallig stelsel een 8-tallig stelsel, en de rest ligt voor de hand.

[Yoozer]

heeft een kubus niet 6 vlakken? - vooruit, achteruit, links, rechts, boven, beneden?

[Varienaja]

Op zondag 30 juni 2002 23:16 schreef Lord Daemon het volgende:
[..]

Kan je dat bewijzen?

Je moet dus 'zomaar' wat doen.

Als je een doolhof hebt, waarbij je in n stappen naar buiten kunt, dan moet je hooguit alle permutaties van n L-letjes en R-retjes uitproberen om gegarandeerd het rijtje van n R-retjes en L-letjes te vinden waarmee je naar buiten kunt.

bewijs:
Stel, je probeert 1 permutatie (de goede) niet uit. Je komt dan niet bij de uitgang.

kanttekening:
let op het woordje 'hooguit', het kan natuurlijk zomaar zijn dat de eerste permutatie meteen de goede is. Omdat je dus hooguit alle permutaties moet uitproberen, kwam ik op de vergelijking met random-sort uit m'n eerste reply.

Het woordje 'zomaar' is een beetje ongelukkig gekozen, ik bedoel niet dat je random door je doolhof moet, maar dat je alle mogelijkheden uit moet proberen. (idem bij random-sort).

[Yoozer]

Op zondag 30 juni 2002 23:27 schreef RickN het volgende:

[..]

Je begrijpt het niet.

ik begrijp het wel, en ik zie ook in dat een grote oplossing verdomd lang kan zijn.

Het is niet de bedoeling dat je Sandalfs recept echt gaat opvolgen, het is alleen een bewijs dat er een reeks instructies bestaat die vanuit elke positie naar de uitgang leidt.

als dit een bewijs is dat aan daemon's originele aannames voldoet, waarom zou je het dan NIET opvolgen?

Daarnaast is het triviaal om te laten zien dat elke reeks instructies voorkomt in Lord Daemons reeks en dus lost Lord Daemon's algoritme elk doolhof op.

dat had ik ook wel door. het ging me vooral om het geheugen-probleem dat niet gelijk duidelijk voor me was.

[RickN]

Op zondag 30 juni 2002 23:37 schreef Yoozer het volgende:

[..]

ik begrijp het wel, en ik zie ook in dat een grote oplossing verdomd lang kan zijn.
[..]

als dit een bewijs is dat aan daemon's originele aannames voldoet, waarom zou je het dan NIET opvolgen?
[..]

dat had ik ook wel door. het ging me vooral om het geheugen-probleem dat niet gelijk duidelijk voor me was.

Er is niks om op te volgen, behalve de reeks die Lord Daemon gaf. Sandalf bewijs garandeerd je dat in Lord Daemons reeks op een gegeven moment een subreeks komt die je naar de uitgang leidt, vanuit een willekeurig punt op het bord. Je hoeft die reeks niet te construeren, hoe lang of kort hij ook is, want je hebt de garantie dat je em in LD's reeks uiteindelijk toch wel tegen komt. Daarnaast is het construeren van een reeks en die volgen iets heel anders dan het simpel weg volgen van de statisch gedefineerde reeks die LD voorstelt, dus nog maals er is geen recept om wel of niet op te volgen.

[RickN]

wacht ff, er gaat ineens een lichtje branden...

Op zondag 30 juni 2002 23:32 schreef Lord Daemon het volgende:

[..]

Nee. Stel, X is: L, L, L, L. Y is: 4, 4, 4, 4.

Je kunt nu concluderen dat je een vierkantje hebt gelopen.

Dit zou waar kunnen zijn. Het zou ook onwaar kunnen zijn. Je hebt namelijk geen info over de hoeken waaronder de wegen staan (let wel: L betekent 'neem de meest linkse weg, dus niet 'ga 90 graden naar links') en de lengte van de wegen. Je kan dus geen kaart construeren.
[..]

Idd. Ik had ff iets te kort gedacht . Sterker nog, zelfs al ligt het doolhof wel op een "Manhattan" grid, dan nog kan het niet wat ik zei. In een spiraal met hoeken van 90 graden kun je makkelijk 4 keer links gaan zonder te kunnen zeggen dat je een rondje bent gelopen. Het komt erop neer dat je nooit de conclusie kunt trekken dat je ergens bent waar je al geweest bent. Met dat in m'n achterhoofd denk ik nu dat de reeksen x en y je geen nuttige info verschaffen.

[Xanthus]

Ik vraag me wel af hoe snel deze zal zijn. Voor een doolhof met 1 weg van elk punt naar elk punt, dus geen circeltjes mogelijk, is rechts aanhouden genoeg.

[Anoniem: 29081]

Voor een kubus werkt het ook, al zou je dan de instructiereeks natuurlijk iets anders moeten interpreteren (niet alleen maar L en R). Je zou bijvoorbeeld steeds groepjes van 3 bits kunnen nemen, waarbij 0 t/m 5 = de 6 richtingen die je steeds opkan. 6 en 7 kun je opvatten als "niets doen", en als in de reeks een richting voorkomt waar je niet heen kunt (bijvoorbeeld "naar boven" terwijl je huidige cubische positie dichtzit van boven) doe je ook niets.

Sandalfs bewijs werkt dan evengoed: er is nog steeds een eindig aantal startsituaties in het doolhof. Op precies dezelfde wijze kun je de oplossing voor situatie 1 uitbreiden tot een oplossing voor situatie 1 en 2, door de oplossing voor situatie 2 (althans, voor situatie 2 na permutatie met oplossing 1, dus dwz de oplossing voor de situatie waarin je vanuit situatie 2 na het uitvoeren van oplossing 1 terecht komt) er achteraan te plakken, enz.

[udenjpg]

Als je een recursie maakt die waarbij je doorgeeft hoevaak je N/E/S/W bent gegaan en geef dit recursief door aan alle mogelijke paden behalve terug, kom je er, als N-S == 0 && W-E == 0 of er geen keuze is mag de recursie uitsterven, De recursies die de uitgang vinden komen terug met de oplossing. Kies daaruit degene met de laagste N+E+S+W en je hebt het kortste pad.

Wel een beetje geheugen-intensief

update:: gaat fout als er 2 of meer eilanden in zitten. Je moet ook nog de volgorde van de richting meegeven (String ofzo) Dan van achteren beginnen te tellen of N-S == 0&& W-E == 0 zich voordoet, dan werkt het altijd.

[Xanthus]

Als je bij een plat doolhof alleen links en rechts gaat (dus nooit rechtdoor bij een kruispunt) is het logisch als je bij een 3d doolhof alleen links rechts boven beneden gaat, dus niet naar achter of voren. Dat zijn dus maar 4 mogelijkheden.

[Confusion]

Sandalf schreef:
Er is een rij van L-en en R-en om vanuit 1 naar de uitgang te komen. Noem deze weg met x_1.

Als je begint in 1 dan is x_1 de juiste weg. Als je echter in 2 begint, dan kom je na het volgen van de instructies van x_1 over het algemeen ergens anders uit, zeg in y. Er is ook een rij instructies om van y naar de uitgang te komen. Noem die rij x_2 en zet deze rij achter de rij instructies x_1 en je hebt een rij instructies x_1 x_2 die zowel vanuit 1 als vanuit 2 werkt.

Stel nu dat je in 3 begint. Volg vanuit 3 de rij instructies x_1 x_2 en kijk waar je uitkomt, zeg in z. Er is nu wederom een rij instructies om vanuit z naar de uitgang te komen. Noem die rij x_3 en plak hem achter x_1 x_2 om een rij te krijgen die vanuit 1, 2 en 3 werkt.

Mooi bewijs, maar niet erg efficient
Meestal sta je niet op de goede plek staat op het moment dat een 'goede reeks' (goed voor een beperkt aantal plekken) aan bod komt.

Wanneer je op plaats v staat wanneer reeks x_1 x_2 x_3 x_4 aan bod komt, die je vanaf 1, x, y en z had thuisgebracht, komt je op plaats w terecht. Pas wanneer je de reeksen met lengte langer dan x_1 x_2 ... x_n, waarbij n het aantal doolhofpunten is, bereikt, weet je zeker dat er op een zeker moment een algoritme gaat komen dat je thuisbrengt. Een doolhof met slechts 9 kruispunten en 4 keerpunten per gemiddelde oplossing, komt dan al op tenminste 36 bits, waarbij je dus al 2²⁵ oplossing hebt moeten proberen....

[Dido]

Op maandag 01 juli 2002 13:27 schreef Fused het volgende:
Mooit bewijs, maar niet erg efficient

Het bewijs is imho heel erg efficient, het bewijst namelijk de stelling dat het in de openingspost genoemde algoritme je altijd uit het doolhof haalt.
Of het in de openingspost genoemde algoritme efficient is, is een tweede.
De eerste vraag was of het werkte en dat is bewezen.
Wat is eigenlijk de effincientie van een bewijs? Is een bewijs niet simpelweg juist of onjuist (en in dat laatste geval dus geen bewijs) ?

[Anoniem: 29081]

Wat is eigenlijk de effincientie van een bewijs? Is een bewijs niet simpelweg juist of onjuist (en in dat laatste geval dus geen bewijs)?

Hoe korter, strakker, of 'eleganter' c.q. minder kunstmatig/gedrongen een bewijs, hoe efficiënter. Lijkt me.

Hoe effeciënt de methode is die wordt bewezen, staat er compleet los van. Sandalfs bewijs is efficiënt, vind ik

En trouwens, dit lijkt wel een ontzettend inefficiente methode, maar als we naar de 'voorwaarden' kijken dan valt het nog best mee. Probeer maar eens zonder kennis van het doolhof een reeks moves te verzinnen die altijd werkt. Veel meer dan domweg 'alle mogelijkheden proberen' kan volgens mij niet, en dan kom je al gauw op de reeks van Lord Daemon uit. Overigens is deze reeks in praktische zin natuurlijk nogal lang, maar aan de andere kant is hij wel kinderlijk eenvoudig te onthouden.

[Confusion]

Dido schreef:
Wat is eigenlijk de efficientie van een bewijs?

Ik heb geen idee, want dat bedoelde ik niet

Hoewel je je natuurlijk kan voorstellen dat een bewijs in minder redenatie-stappen efficienter is. Alleen moeten we dan gaan discussieren over wat precies een redenatie-stap is

[Diadem]

Ik wil niet vervelend zijn, maar ik twijfel aan Sandalf's bewijs. Of eigenlijk aan een aanname die hij maakt in zijn bewijs.

Hij neemt aan dat er vanuit ieder punt in de doolhof een pad is dat naar de uitgang leidt.

Echter als je alleen rechtsaf en linksaf kunt slaan zou ik die aanname niet zonder meer durven maken. Voor 2 dimensies wil ik het nog wel geloven, maar voor 3 dimensies vind ik het dubieus worden.

Lord Daemon's aanvulling met een 8-voudige codering is een oplossing, maar in dat geval wil ik een bewijs zien dat elke mogelijke subreeks dan voorkomt in LD's nieuwe reeks.

[Lord Daemon]

Op maandag 01 juli 2002 17:19 schreef Diadem het volgende:
Echter als je alleen rechtsaf en linksaf kunt slaan zou ik die aanname niet zonder meer durven maken. Voor 2 dimensies wil ik het nog wel geloven, maar voor 3 dimensies vind ik het dubieus worden.

Het ging ook over 2 dimensies. Voor meer dimensies kom je er natuurlijk niet met links en rechts.

Lord Daemon's aanvulling met een 8-voudige codering is een oplossing, maar in dat geval wil ik een bewijs zien dat elke mogelijke subreeks dan voorkomt in LD's nieuwe reeks.

Ik ook, dat lijkt me nog niet zo gemakkelijk. Misschien ook wel, maar ik heb het in die post iig niet bewezen, daar ben ik me volledig van bewust.

[Jace / TBL]

Lord Daemon's aanvulling met een 8-voudige codering is een oplossing, maar in dat geval wil ik een bewijs zien dat elke mogelijke subreeks dan voorkomt in LD's nieuwe reeks.

Zijn algoritme is het achter elkaar zetten van alle natuurlijke getallen in het betreffende talstelsel. Of je nu 2-tallig (binair, dus R en L) of 8-tallig (octaal, dus die 8 richtingen van LD) werkt, door alle natuurlijke getallen in dit talstelsel te schrijven en achter elkaar te plakken kom je elke (eindige) reeks tegen.

Verzin maar een subreeks (dwz een aantal van die 8-richtingen achter elkaar), interpreteer dit als een octaal getal waaruit volgt welk natuurlijk getal dit is, en je weet niet alleen dat het in de reeks staat, maar zelfs waar.

Overigens snap ik niet waar (in geval van een 3D doolhoof) die 8 richtingen precies op slaan, 6 lijkt me logischer

[FCA]

Een onbewezen aanname van Sandalfs bewijs is idd de aanname dat er vanuit ieder punt een pad bestaat dat alleen maar uit links en rechts gaan bestaat. Zeker met doolhoven waar meer dan 4 wegen op elkaar komen, is het zeker niet duidelijk dat het goed gaat. En met 3-D doolhoven, waar er gangen over elkaar heen kunnen gaan, gaat het vreselijk fout.

Verder is het algoritme vreselijk inefficient, maar dat was natuurlijk allang duidelijk

edit:
Ik denk dat een soort van backtrack matrix methode beter werkt, maar of dat efficienter is weet ik niet.

Gaat als volgt:
Neem een n x n matrix, met n het aantal kruispunten van het doolhof. Dan zet je 1tje op de (a,b) plek van de matrix, als je in 1 stap van a naar b kunt lopen. Dan ga je de matrix met zichzelf vermenigvuldigen, net zo lang totdat je een pad van je beginpositie naar de uitgang hebt, met een getal m. Dit getal m is de kortste route van je beginpositie naar de uitgang (bewijs hiervan is triviaal, schrijf stappen op). Echter niet welke route dat is.

Die valt te achterhalen door te kijken naar de verschillende matrices. Je gaat kijken waarvandaan je naar de uitgang kunt komen in 1 stap, en waar je naar toe kunt komen vanaf je beginpositie in m-1 stappen. Dat is je voorlaatste punt. Etc.

Voordeel: Minder lopen dan LD methode
Waarschijnlijk nadeel: Meer rekenen dan LD's methode.

Kan iemand misschien een grootte van orde schatting geven voor mijn methode?

[Lord Daemon]

Op maandag 01 juli 2002 17:58 schreef JaceTBL het volgende:
Overigens snap ik niet waar (in geval van een 3D doolhoof) die 8 richtingen precies op slaan, 6 lijkt me logischer

Ik ben er nog niet uit hoeveel je er nodig hebt, maar een eerste intuitie is, als D de dimensionaliteit is, 2^D-1 * (D-1)!

Je hebt in een D-dimensionale ruimte namelijk D-1 hoeken die de relatieve plaatsen van de uitgangen bepalen. Als je bij alk van die hoeken zowel de kleinste ('L') als de grootste ('R') wilt kunnen kiezen heb je dus al 2^D-1 richtingen. Echter, je moet ook nog elke willekeurige volgorde om die hoeken af te gaan apart nemen, anders zou je bijvoorbeeld bij een 'verdiepingen'-doolhof waar ladders naar boven en beneden alleen op kruispunten hangen, nooit omhoog of omlaag gaan. Dit levert nog een extra factor (D-1)! op.

Of je dan altijd een weg hebt van A naar B? Intuitief denk ik van wel, maar ik heb het nog niet bewezen.

Op maandag 01 juli 2002 18:21 schreef FCA het volgende:
Een onbewezen aanname van Sandalfs bewijs is idd de aanname dat er vanuit ieder punt een pad bestaat dat alleen maar uit links en rechts gaan bestaat. Zeker met doolhoven waar meer dan 4 wegen op elkaar komen, is het zeker niet duidelijk dat het goed gaat.

Gaat wel goed. Ik zou even moeten nadenken over een bewijs, maar probeer maar eens een tegenvoorbeeld te verzinnen. (Heb ik al even mee zitten spelen.)

[marcusk]

Gaat wel goed. Ik zou even moeten nadenken over een bewijs, maar probeer maar eens een tegenvoorbeeld te verzinnen. (Heb ik al even mee zitten spelen.)

doodlopende weg? :

code:

    |---|
    | ^ |
-----   -----

-------------

(btw, sluit je sup eens af )

[Anoniem: 37240]

Op maandag 01 juli 2002 20:26 schreef Lord Daemon het volgende:
Gaat wel goed. Ik zou even moeten nadenken over een bewijs, maar probeer maar eens een tegenvoorbeeld te verzinnen. (Heb ik al even mee zitten spelen.)

Bewijs is simpel je kunt elke n>3-splitsing opdelen in n-2 drie-splitsingen dus je hoeft alleen maar rechts of links.
Ook doodlopende gangen zijn te beschouwen als een drie-splitsing door 2 van de 3 wegen met elkaar te verbinden.

code:

  |
--X  viersprong
   \
    X--
    |

     _
    / \
---X  |  doodlopend
    \_/

[Lord Daemon]

Op maandag 01 juli 2002 20:38 schreef marcusk het volgende:
doodlopende weg?

Zoals ik in mijn openingspost schreef:

(Als je op een doodlopend punt bent - een 'kruispunt' met 1 uitgang - staan 'L' en 'R' allebei voor omdraaien en terug lopen.)

Op maandag 01 juli 2002 20:38 schreef borganism het volgende:
Bewijs is simpel je kunt elke n>3-splitsing opdelen in n-2 drie-splitsingen dus je hoeft alleen maar rechts of links.

Hier snap ik niets van? Ik kan op een kruispunt met 4 wegen in mijn algoritme expliciet niet rechtdoor. Wil ik toch die weg inslaan, dan moet ik eerst uit een van de andere twee wegen komen, zodat die weg links of rechts ligt ipv rechtdoor.

[Aaargh!]

Op zondag 30 juni 2002 22:20 schreef Lord Daemon het volgende:
En minstens even leuk: is er iemand die een sneller algoritme kan verzinnen? Het moet gegarandeerd een oplossing opleveren binnen een eindige tijd

Gewoon een depth-first of width-first search doen ?

[Lord Daemon]

Op maandag 01 juli 2002 21:00 schreef Aaargh! het volgende:
Gewoon een depth-first of width-first search doen ?

Uh... een wat?

[RickN]

depth-first en breadth-first zijn manieren om door een boom te itereren. Met wat aanpassingen kun je er ook mee door een willekeurige graaf itereren en zo b.v. een spanning-tree opzetten. Deze aanpassingen houden echter in dat je een geschiedenis gaat bijhouden over waar je al bent geweest (om zo te voorkomen dat je gaat cyclen) en daarmee is de methode dus niet toepasbaar in de situatie die LD heeft geschetst.

[Knutselsmurf]

Op maandag 01 juli 2002 18:21 schreef FCA het volgende:
Een onbewezen aanname van Sandalfs bewijs is idd de aanname dat er vanuit ieder punt een pad bestaat dat alleen maar uit links en rechts gaan bestaat. Zeker met doolhoven waar meer dan 4 wegen op elkaar komen, is het zeker niet duidelijk dat het goed gaat. En met 3-D doolhoven, waar er gangen over elkaar heen kunnen gaan, gaat het vreselijk fout.

Verder is het algoritme vreselijk inefficient, maar dat was natuurlijk allang duidelijk

edit:
Ik denk dat een soort van backtrack matrix methode beter werkt, maar of dat efficienter is weet ik niet.

Gaat als volgt:
Neem een n x n matrix, met n het aantal kruispunten van het doolhof. Dan zet je 1tje op de (a,b) plek van de matrix, als je in 1 stap van a naar b kunt lopen. Dan ga je de matrix met zichzelf vermenigvuldigen, net zo lang totdat je een pad van je beginpositie naar de uitgang hebt, met een getal m. Dit getal m is de kortste route van je beginpositie naar de uitgang (bewijs hiervan is triviaal, schrijf stappen op). Echter niet welke route dat is.

Die valt te achterhalen door te kijken naar de verschillende matrices. Je gaat kijken waarvandaan je naar de uitgang kunt komen in 1 stap, en waar je naar toe kunt komen vanaf je beginpositie in m-1 stappen. Dat is je voorlaatste punt. Etc.

Voordeel: Minder lopen dan LD methode
Waarschijnlijk nadeel: Meer rekenen dan LD's methode.

Kan iemand misschien een grootte van orde schatting geven voor mijn methode?

Even snel uit mijn hoofd: Het vermenigvuldigen van een n*n matrix is orde n^2. Als er dus m stappen nodig zijn om de uitgang te bereiken, zal de rekentijd tus m*n^2 zijn. Omdat m kleiner is dan n (Als niet, dan kom je meer da 1 keer in een kruispunt en dat is onzinnig, kun je dus zeggen dat de orde van dit probleem dus n^3 is ,met n het aantal kruispunten/T-splitsingen in de doolhof.

[Knutselsmurf]

Op maandag 01 juli 2002 21:03 schreef Lord Daemon het volgende:

[..]

Uh... een wat?

Even een voorbeeldje:

Stel het volgende stukje doolhof voor:

code:

xxxxx
I123x
xxx4x
x765x
x8x9U
xxxxx

I is ingang, U is uitgang.
Alle beschikare posities zijn genummerd 1-9. Bij depth-first gebruik je een zogenaamde stack, waar je telkens bovenaan de stapel een positie inleest, dan bepaalt welke andere posities daarvandaan beschikbaar zijn, en die nieuwe posities weer bovenop de stapel legt.

Om even bij het voorbeeld te blijven:
de nummers 1-4 zijn triviaal, bij positie 5 is er pas een keuze:
De stapel ziet er dan als volgt uit: 1-2-3-4-5. Om even het ongelukkige voorbeeld te nemen, kijken we eerst of er naar beneden een mogelijkheid is, en daarna naar links( netjes met de klok mee).

Daarmee wordt de stack dus: 1-2-3-4-5-9-6. Daarna kijken we bij positie 6( de laatste op de stapel, wat de mogelijkheden zijn. Dat is er maar 1, dus de stack wordt 1-2-3-4-5-9-6-7, en daarna 1-2-3-4-5-9-6-7-8. Daarna kunnen we niet verder, dus de laatste wordt weggegooid, waarna we weer op 1-2-3-4-5-9-6-7 zitten en we geen andere mogelijkheden hebben. datzelfde geldt voor 1-2-3-4-5-9-6, zodat uiteindelijk we een stack hebben van 1-2-3-4-5-9, waarna de enige mogelijkheid ook de juiste is. Nadeel van deze methode is, dat we, zodra we een fout pad ingaan, we dit pad ook helemaal tot aan het einde moeten volgen.

Bij de width-first methode, gebruiken we geen stack maar een zogenaamde queue. Deze wordt niet van achter naar voren, maar van voren naar achter gelezen.

Om weer ons voorbeeld te gebruiken: Na de triviale 1-2-3-4-5 worden 6 en 9 toegevoegd, zodat de queue er als volgt uitziet: 1-2-3-4-5-6-9. Daarnaaast is er bijgehouden dat we op dit moment op positie 5 zitten. Vervolgens wordt er van het volgende punt in de queue gekeken wat de mogelijkheden zijn, zodat, met punt 6 meegenomen, de queue er als volgt uitziet: 1-2-3-4-5-6-9-7 en onze huidige positie is 6. Vervolgens is punt 9 aan de beurt, waarna de uitgang gevonde wordt. Let er wel op, dat nu dus niet duidelijk is, hoe punt 9 bereikt is. Daarvoor zal dus op dezelfde manier verder gekeken moeten worden, waarbij punt 9 als eindpunt beschouwd wordt.

Ik hoop dat het een beetje duidelijk is. Zo niet, geef dan please an op welke punten ik onduidelijk ben, dan probeer ik die punten beter uit te leggen.