Ska traversera så många celler som möjligt

Trädvy Permalänk
Medlem
Plats
Skåne
Registrerad
Jan 2011

Ska traversera så många celler som möjligt

Har en programmerings uppgift som jag inte är helt säker på hur jag ska börja med. Jag skapar ett rutnät med hjälp av en 2D array, så varje kolumn och rad bildar tillsammans en koordinat. I rutnätet kommer vissa celler vara "förbjudna att besöka". Sedan ska en orm(snake) börja på position 0,0 och traversera så många celler som möjligt, utan att besöka de förbjudna cellerna. Output ska vara antalet celler som är besöka samt rätt ordning på traverseringen. Här är en bild för all illustrera vad som menas: https://imgur.com/a/qzxZv

Min initiala tanke var att detta kan ju liknas med en graf och att jag bör använda depth eller breadth first traversering på något sätt, men jag är inte säker. Hade varit uppskattat om någon kunde ge mig lite idéer på vad jag skulle kunna göra. Har lekt runt lite med stack och queue också, men inte helt säker på vad implementationen blir. För tillfället har jag kod som traverserar alla celler i ordning, bara för att börja någonstans.

private void testRun() { System.out.println("Beginning testRun"); Stack stack = new Stack(); ArrayList<String> result = new ArrayList<String>(); // Each column for (int i = 0; i < brickArray.length; i++) { // Each row for (int j = 0; j < brickArray[i].length; j++) { Brick tempBrick = brickArray[i][j]; if (!tempBrick.isVisited() && !tempBrick.isObstacle()) { brickArray[i][j].setVisited(); result.add(i + "," + j); stack.push(String.valueOf(i) + "," + String.valueOf(j)); } } } System.out.println(result.size()); System.out.println(result); System.out.println("Stack " + stack); } Output: 13 [0,0, 0,1, 0,2, 0,3, 1,0, 1,3, 2,0, 2,1, 2,3, 3,0, 3,1, 3,2, 3,3]

Stationär:Asrock P67 Extreme 4 | i5 2500K@4.5Ghz | Asus GTX 970 black Överklockad | Samsung Evo 960 1TB, 2x WD blue 5TB | 8GB Corsair XMS3 + 8GB Hyper x Fury | EVGA Supernova G2 750W Gold | Silverstone FT02
Laptop: Dell XPS 15 2017
Mobil: Oneplus 6 128GB

Trädvy Permalänk
Medlem
Registrerad
Apr 2014

Wikipedia sidan för Pathfinding har information om åtminstone två vanliga metoder för att hitta snabbaste vägen. Dessa borde du kunna skriva om för att ge dig ditt resultat.

-- Citera mig om ni vill få återkoppling --

Trädvy Permalänk
Medlem
Plats
-
Registrerad
Sep 2004

Får du göra en lösning som jobbar "iterativt" dvs kör om samma lösning med olika val, tills den hittar längsta lösningen?

maybe i'm a one trick pony
but i ride it ride it ride it ride it
ride it honey

Trädvy Permalänk
Medlem
Plats
Skåne
Registrerad
Jan 2011
Skrivet av dopedog:

Wikipedia sidan för Pathfinding har information om åtminstone två vanliga metoder för att hitta snabbaste vägen. Dessa borde du kunna skriva om för att ge dig ditt resultat.

Läste artikeln, ser defintivit ut som något jag kan använda! Ska kolla närmare på detta.

Skrivet av Roger W:

Får du göra en lösning som jobbar "iterativt" dvs kör om samma lösning med olika val, tills den hittar längsta lösningen?

Japp, men lösningen bör vara så effektiv som möjligt. Ska klara ett ganska stor rutnät utan att det tar för lång tid. Men har inte fått något exakta instruktioner för detta.

Stationär:Asrock P67 Extreme 4 | i5 2500K@4.5Ghz | Asus GTX 970 black Överklockad | Samsung Evo 960 1TB, 2x WD blue 5TB | 8GB Corsair XMS3 + 8GB Hyper x Fury | EVGA Supernova G2 750W Gold | Silverstone FT02
Laptop: Dell XPS 15 2017
Mobil: Oneplus 6 128GB

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Okt 2006

A* är poppis och det bör finnas väldigt många exempel att kolla på, det är också en ganska bra algoritm.

Trädvy Permalänk
Medlem
Plats
skåne
Registrerad
Apr 2010

som jag tolkar uppgiften så är det längsta vägen det handlar om (besöka så många celler som möjligt). jag hade googlat efter en befintlig algoritm att implementera och om det inte bar frukt så hade jag försökt med en brute force typ så här:

för nuvarande koordinat så har du ett antal giltiga rutor att besöka (ej förbjuden, har inte redan besökt den). besök den första. rinse and repeat till du hamnar i ett läge där du inte har några giltiga rutor att gå till. spara undan resultatet om du inte redan har en längre lösning.

backa till förra rutan och se om du har några andra alternativ du inte provat där. om nej, fortsätt backa. till slut har du backat ända till starten och har inga alternativ där du inte har provat och det betyder att du provat alla alternativ.

kanske inte så tydligt, men jag vill inte skriva kod eftersom det är en skoluppgift

cheers

Trädvy Permalänk
Medlem
Plats
Norrköping
Registrerad
Jul 2006

R5-1600X, GA-AB-350M-G3, 16GB DDR4 @ 2666, RX580 8GB, Corsair CX650M Rev2

Trädvy Permalänk
Medlem
Plats
Zion
Registrerad
Apr 2004

A* hittar kortaste vägen mellan två punkter den vandrar inte så som uppgiften ska lösas utan redig modifikation

[ i5-6600K @ 4.7Ghz || Corsair H110 GTX || 16GB DDR4 || ASUS Z170 Pro Gaming || Asus ROG 1080 Strix @ 2100+/11Ghz+ ]
Unigine Superposition 1080p; 17487 @ Medium; 4594 @ Extreme
"One is always considered mad, when one discovers something that others cannot grasp."
- Ed Wood

Trädvy Permalänk
Medlem
Plats
Skåne
Registrerad
Jan 2011
Skrivet av helmet:

som jag tolkar uppgiften så är det längsta vägen det handlar om (besöka så många celler som möjligt). jag hade googlat efter en befintlig algoritm att implementera och om det inte bar frukt så hade jag försökt med en brute force typ så här:

för nuvarande koordinat så har du ett antal giltiga rutor att besöka (ej förbjuden, har inte redan besökt den). besök den första. rinse and repeat till du hamnar i ett läge där du inte har några giltiga rutor att gå till. spara undan resultatet om du inte redan har en längre lösning.

backa till förra rutan och se om du har några andra alternativ du inte provat där. om nej, fortsätt backa. till slut har du backat ända till starten och har inga alternativ där du inte har provat och det betyder att du provat alla alternativ.

kanske inte så tydligt, men jag vill inte skriva kod eftersom det är en skoluppgift

cheers

Skrivet av Ferrat:

A* hittar kortaste vägen mellan två punkter den vandrar inte så som uppgiften ska lösas utan redig modifikation

Läste på en del om A* och ja den gör ju det jag är ute efter fast med viss modifikation, jag vill ju ha den längsta vägen som är möjlig. Jag har försökt i ca 2 timmar att modifiera en befintlig A* algoritm men blev bara fel Får söka leta vidare.

Stationär:Asrock P67 Extreme 4 | i5 2500K@4.5Ghz | Asus GTX 970 black Överklockad | Samsung Evo 960 1TB, 2x WD blue 5TB | 8GB Corsair XMS3 + 8GB Hyper x Fury | EVGA Supernova G2 750W Gold | Silverstone FT02
Laptop: Dell XPS 15 2017
Mobil: Oneplus 6 128GB

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Sep 2008

Skriver just ni från mobilen så du får ett mer abstrakt svar, men ska försöka hjälpa grundligare när jag är hemma ikväll (om du inte löser det förstås).

A* är djikstra's algoritm, men istället för att sätta värdet av alla möjliga vägar till 0 så sätter du en vikt på varje väg. Exenpelvis om du tar väg B så är du 3 uppskattad ifrån mål medan tar du väg C är du 5 uppskattad från mål (notera att uppskattningen är viktig då det är vad som bestämmer nästa väg varesig uppskattningen är rätt eller fel).
Sedan slänger du i alla närliggande vägar från en redan upptäck nod i en heap (prioritetskö) som sedan plockar ur den vägen som nuvarande har bästa chans att ta dig mellan A och B. Det du vill göra är tvärtom, vilket betyder att du vill få fram den vägen som är minst lämplig mellan A och B. det gör du genom att implementera en compare som istället för att ge dig den minsta av två ting vid en jämförelse istället ger dig det längsta och såleddes prioriterar heapen den längsta vägen.

Om något känns oklart, så kan du skriva det så försöker jag hjälpa till ikväll!

Skickades från m.sweclockers.com

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Sep 2008

Sedan vill jag även tillägga att A* star tar ut snabbaste vägen mellan två givna noder.
Om du använder djikstra's algoritm så får du ut hela nätet och hur långt det är mellan olika noder, vilket kan vara användbart.

Skickades från m.sweclockers.com

Trädvy Permalänk
Medlem
Plats
Skåne
Registrerad
Jan 2011
Skrivet av Razki:

Skriver just ni från mobilen så du får ett mer abstrakt svar, men ska försöka hjälpa grundligare när jag är hemma ikväll (om du inte löser det förstås).

A* är djikstra's algoritm, men istället för att sätta värdet av alla möjliga vägar till 0 så sätter du en vikt på varje väg. Exenpelvis om du tar väg B så är du 3 uppskattad ifrån mål medan tar du väg C är du 5 uppskattad från mål (notera att uppskattningen är viktig då det är vad som bestämmer nästa väg varesig uppskattningen är rätt eller fel).
Sedan slänger du i alla närliggande vägar från en redan upptäck nod i en heap (prioritetskö) som sedan plockar ur den vägen som nuvarande har bästa chans att ta dig mellan A och B. Det du vill göra är tvärtom, vilket betyder att du vill få fram den vägen som är minst lämplig mellan A och B. det gör du genom att implementera en compare som istället för att ge dig den minsta av två ting vid en jämförelse istället ger dig det längsta och såleddes prioriterar heapen den längsta vägen.

Om något känns oklart, så kan du skriva det så försöker jag hjälpa till ikväll!

Skickades från m.sweclockers.com

Skrivet av Razki:

Sedan vill jag även tillägga att A* star tar ut snabbaste vägen mellan två givna noder.
Om du använder djikstra's algoritm så får du ut hela nätet och hur långt det är mellan olika noder, vilket kan vara användbart.

Skickades från m.sweclockers.com

Jo jag misstänkte att jag kan använda Djikstras algoritm, kolla alla vägar och ta den med högst vikt? Läste även att Bellman–Ford algorithmen kan vara till hjälp. Annars hittade jag precis det här; http://www.dsalgo.com/2013/02/find-longest-path-in-maze.html

Stationär:Asrock P67 Extreme 4 | i5 2500K@4.5Ghz | Asus GTX 970 black Överklockad | Samsung Evo 960 1TB, 2x WD blue 5TB | 8GB Corsair XMS3 + 8GB Hyper x Fury | EVGA Supernova G2 750W Gold | Silverstone FT02
Laptop: Dell XPS 15 2017
Mobil: Oneplus 6 128GB

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Sep 2008
Skrivet av Baxtex:

Jo jag misstänkte att jag kan använda Djikstras algoritm, kolla alla vägar och ta den med högst vikt? Läste även att Bellman–Ford algorithmen kan vara till hjälp. Annars hittade jag precis det här; http://www.dsalgo.com/2013/02/find-longest-path-in-maze.html

Glömde att svara!

Hoppas det har löst sig. Personligen är jag inte förtjust i algoritmer/lösningar som använder sig av explicita arrayer eller matriser. Dels för att koden blir mer svårförståelig, då den använder mer datorvänliga termer. Men även för att felen går från exception till error.

Trädvy Permalänk
Medlem
Plats
Skåne
Registrerad
Jan 2011
Skrivet av Razki:

Glömde att svara!

Hoppas det har löst sig. Personligen är jag inte förtjust i algoritmer/lösningar som använder sig av explicita arrayer eller matriser. Dels för att koden blir mer svårförståelig, då den använder mer datorvänliga termer. Men även för att felen går från exception till error.

Hej, lite sent svar här också, har inte haft tid.

Nej jag har inte lyckats lösa det ännu.

Stationär:Asrock P67 Extreme 4 | i5 2500K@4.5Ghz | Asus GTX 970 black Överklockad | Samsung Evo 960 1TB, 2x WD blue 5TB | 8GB Corsair XMS3 + 8GB Hyper x Fury | EVGA Supernova G2 750W Gold | Silverstone FT02
Laptop: Dell XPS 15 2017
Mobil: Oneplus 6 128GB