Random walks, checka om man varit på samma ruta förrut
Hej, se på min Walker:
Jag vill ta reda på om/när walken går på en ruta den redan varit på. Det kan jag enkelt göra genom att checka om hela min "history" lista vid varje steg, men det har kvadratisk komplexitet vilket är detrimentalt för min kod.
Jag har skapat ett attribut till Walkern som loggar antal upp-, ner-, höger- och vänstersteg den har tagit. Jag tror att det behövs för att kunna skapa en check funktion i linjär komplexitet (eller kanske konstant), men jag vet inte hur.
Eller ännu bättre: jag kan spara en lista [u, p, p, v, h, h, u...] för alla tagna steg. Det enda jag behöver ta reda på är om summan av upp/ner och höger/vänster över [ i sista elementen ] blir noll för något 0<i<n vilket kostar konstant tid om jag sparar resultaten för alla föregående steg?
Jag antar att du har ett plan din 'walker' kan röra sig runt på?
Och din O(n^2) kommer ifrån att du har två nestade for-loopar som kollar igenom varje "ruta" en i taget?
Kan du inte bara kolla om list[m][n]=visited?
Dracaena skrev:Jag antar att du har ett plan din 'walker' kan röra sig runt på?
Ja, eller, oändligt stor, inga gränser.
Och din O(n^2) kommer ifrån att du har två nestade for-loopar som kollar igenom varje "ruta" en i taget?
Menar inte så!
Kan du inte bara kolla om list[m][n]=visited?
Jo, men det blir ju kvadratkomplext beroende på steglängd, eftersom jag behöver checka en n lång lista efter att ha gått n steg, vid varje steg, det känns onödigt.
Edit: Jag missuppfattade vad du menade, det löser problemet superenkelt, tack!
