"Finne beste path"-mest effektive vei.

[Gnurk!]

Ok så her er oppgaven, jeg blir gitt en sekvens med tall, som jeg omprogrammerer til et koordinatsystem noe alle dette:

 

3 3 4

5 6 7

9 3 9

(alltid kvadratisk)

Denne delen går greit, men herifra skal jeg finne veien fra punkt (0,0) til (n,n)

som har minst differanse (altså 3-4 er 1 differanse 6-4 har 2 differanse etc).

 

Og jeg sliter veldig med å finne en måte å finne ut den greiste veien UTEN å måtte kjøre en loop så mange ganger at den til slutt bare må finne den (altså en loop som vil prøve alle mulige obskure veier, og mange ganger ikke sikte mot målet engang)

 

Noen forslag?

 

Kan foresten nevne at det jeg har gjort til nå er å lage en node med 4 pekere og 1 dataelement (høyre, venstre, opp, ned) og tallverdien inni.

Men også en Xkordinat og Ykordinat.

Som jeg da bruker sammen med linjetellere, istedenfor å måtte lage et helt kordinatsystem (så tester jeg bare at de ikke går over linjeteller verdier eller under 0

 

 

 

 

altså det jeg har lagd til nå (har ikke lagd finne raskeste path tingen ennå, fordi jeg finner ingen EFFEKTIV måte å lage denne på:

klassen for noden: den er nokså straight foreward og mest sannsynelig ikke nødvendig å se på engang for å forstå.

 

package oving5;
public class Kordinatpeker {
public Kordinatpeker Venstre;
public Kordinatpeker Hoeyre;
public Kordinatpeker Opp;
public Kordinatpeker Ned;

public int xKordinat;
public int yKordinat;
public int indreVerdi;
public Kordinatpeker(int xkordinat, int ykordinat, int indreverdi){
 xKordinat=xkordinat;
 yKordinat=ykordinat;
 indreVerdi=indreverdi;

 Venstre=null;
 Hoeyre=null;
 Opp=null;
 Ned=null;
}

 public void setVenstre(Kordinatpeker a){
  Venstre=a;
 }
 public void setHoeyre(Kordinatpeker a){
  Hoeyre=a;
 }
 public void setOpp(Kordinatpeker a){
  Opp=a;
 }
 public void setNed(Kordinatpeker a){
  Ned=a;
 }
 public Kordinatpeker getVenstre(){
  return Venstre;
 }
 public Kordinatpeker getHoeyre(){
  return Hoeyre;
 }
public Kordinatpeker getOpp(){
 return Opp;
}
public Kordinatpeker getNed(){
 return Ned;
}
public int getX(){
 return xKordinat;
}
public int getY(){
 return yKordinat;
}
public int getVerdi(){
 return indreVerdi;
}
}

 

 

 

andre klassen:

 

package oving5;
public class Oppgave4 {
public void finn3(int N, int kart){

 //a1 er teller for xkordinat senere for danning, a2 for y.
 int a1=0;
 int a2=0;

 //ordner opp lista og antall linjer (kvadratisk er anntatt)
 double linjeAntall=(double) N;
 linjeAntall=Math.sqrt(linjeAntall);
 int[] pathing=new int[(int)N];
 int[] lista=new int[N];
 for(int i=0; i<=N; i++){
  lista[i]=kart/10^(N-i);
 }


 //her putter vi alt i kordinatpeker klassen som ble laget.
 Kordinatpeker[] kartet=new Kordinatpeker[N];
 for(int i=0;i<=N;i++){
   if(linjeAntall==a1){
 a2++;
 a1=0;
   }
   kartet[i]=new Kordinatpeker(a1,a2,lista[i]);
   a1++;
  }

 //tilordner elementene sine pekere etc, kjoerer 2 loops for oppdatering slik at de peker på riktige elementer med riktige pekere.
 for(int tmp=0;tmp<2;tmp++){
 a1=0;
 a2=0;
 for(int i=0;i<=N;i++){
  if(linjeAntall==a1){
   a2++;
   a1=0;
  }
  if(kartet[i].getX()>0){
   kartet[i].setVenstre(kartet[i-1]);
  }
  if(kartet[i].getX()<linjeAntall){
   kartet[i].setHoeyre(kartet[i+1]);
  }
  if(kartet[i].getY()>0){
   kartet[i].setOpp(kartet[i-1]);
  }
  if(kartet[i].getY()<linjeAntall){
   kartet[i].setNed(kartet[i+1]);
  }
  a1++;
 }
 }


 for(int i=0; i<100000; i++){

 }


 System.out.print(pathing);
}

}

 

 

 

 

Noen forslag til hva slags loop som kan kjøres for å effektivt finne frem til målet, altså (N,N) uten å måtte gjør noe alla en for loop som kjører 100000 ganger og bare tilfeldig velger en vei (opp, ned, venste eller høyre) utifra en math.random*4 funksjon.

Da noe slikt ville ledet til mye overkjøring (det samme på nytt).

Hvis det er eneste løsning så forstår jeg forsåvidt hvordan man lager det, bare lurte på om det fintes en bedre måte?

Endret 1. november 2012 av [email protected]

[etse]

Du kan implementere Dijkstras algoritme for å gjøre et graf-søk etter den beste stien.

Endret 1. november 2012 av etse

[SkoMedHull]

Dijkstras algoritme kombinert med en binærheap er en kjapp og god løsning. Skal se om jeg kan finne frem en gammel implementasjon jeg selv har laget.

[Gnurk!]

Den algoritmen var vel bra, men dette er bare 1/6 av en ukes oppgave, så å lære seg den virker som litt unødig mye å gjør for en slik liten bit? uansett tusen takk for hjelpen, var mest ute etter en simpel løsning dog

En annen ting var og at utifra den formelen hans forsto jeg det som at det var snakk om AVSTAND mellom elementer, noe det ikke er her

 

 

 

det jeg har gjort til nå som løsning er dette:

 

package oving5;
import java.awt.List;
public class Oppgave4 {
public void finn3(int N, int kart){

 //a1 er teller for xkordinat senere for danning, a2 for y.
 int a1=0;
 int a2=0;

 //ordner opp lista og antall linjer (kvadratisk er anntatt)
 double linjeAntall=(double) N;
 linjeAntall=Math.sqrt(linjeAntall);
 Kordinatpeker[] pathing=new Kordinatpeker[(int)(N*N)];
 int[] lista=new int[N];
 for(int i=0; i<=N; i++){
  lista[i]=kart/10^(N-i);
 }


 //her putter vi alt i kordinatpeker klassen som ble laget.
 Kordinatpeker[] kartet=new Kordinatpeker[N];
 for(int i=0;i<=N;i++){
if(linjeAntall==a1){
 a2++;
 a1=0;
}
kartet[i]=new Kordinatpeker(a1,a2,lista[i]);
a1++;
  }

 //tilordner elementene sine pekere etc, kjoerer 2 loops for oppdatering slik at de peker på riktige elementer med riktige pekere.
 for(int tmp=0;tmp<2;tmp++){
 a1=0;
 a2=0;
 for(int i=0;i<=N;i++){
  if(linjeAntall==a1){
a2++;
a1=0;
  }
  if(kartet[i].getX()>0){
kartet[i].setVenstre(kartet[i-1]);
  }
  if(kartet[i].getX()<linjeAntall){
kartet[i].setHoeyre(kartet[i+1]);
  }
  if(kartet[i].getY()>0){
kartet[i].setOpp(kartet[i-1]);
  }
  if(kartet[i].getY()<linjeAntall){
kartet[i].setNed(kartet[i+1]);
  }
  a1++;
 }
 }
 Kordinatpeker current;
 Kordinatpeker prevKord;
 Kordinatpeker[] usedKords=new Kordinatpeker[N*N];
 Kordinatpeker[] bestPath=new Kordinatpeker[N*N];
 long pathTeller=N*N;
 long bestePathTeller=N*N*N*N*N;
 boolean venstreUsed, hoeyreUsed, oppUsed, nedUsed;
 //0=venstre, 1=hoeyre, 2=opp, 3=ned
 //dette er loopen som kjoerer hele banen paa nytt
 for(int i=0; i<N*N*N*N; i++){
  current=kartet[0];
  venstreUsed=false; hoeyreUsed=false; oppUsed=false; nedUsed=false;
  if (pathTeller<bestePathTeller&&(i!=0)){
bestPath=pathing;
bestePathTeller=pathTeller;
  }

  pathTeller=0;
  //dette er loopen som soeker etter en bane
  for(int i3=0; i<N*N;i3++){
  int t=0;
  int rnd=(int)Math.random()*3;

  //tester at ingen av variablene er brukt foer.
  for(int usedInt=0; usedInt<(int)(N*N);usedInt++){
if(usedKords[usedInt]==null){
 usedInt=(N*N);
}
else if(usedKords[usedInt].getX()==current.getVenstre().getX()&&usedKords[usedInt].getY()==current.getVenstre().getY()){
 venstreUsed=true;
}
else if(usedKords[usedInt].getX()==current.getHoeyre().getX()&&usedKords[usedInt].getY()==current.getHoeyre().getY()){
 hoeyreUsed=true;
}
else if(usedKords[usedInt].getX()==current.getOpp().getX()&&usedKords[usedInt].getY()==current.getOpp().getY()){
 oppUsed=true;
}
else if(usedKords[usedInt].getX()==current.getNed().getX()&&usedKords[usedInt].getY()==current.getNed().getY()){
 nedUsed=true;
}
  }
  if(rnd==0&&kartet[t].getVenstre()!=null&&!(venstreUsed)){
pathing[t]=current;
t++;
current=kartet[t].getVenstre();
if(pathTeller>current.getVerdi()) pathTeller=pathTeller-current.getVerdi();
else pathTeller=pathTeller+current.getVerdi();
  }
  else if(rnd==1&&kartet[t].getHoeyre()!=null&&!(hoeyreUsed)){
pathing[t]=current;
t++;
current=kartet[t].getHoeyre();
if(pathTeller>current.getVerdi()) pathTeller=pathTeller-current.getVerdi();
else pathTeller=pathTeller+current.getVerdi();
  }
  else if(rnd==2&&kartet[t].getHoeyre()!=null&&!(oppUsed)){
pathing[t]=current;
t++;
current=kartet[t].getOpp();
if(pathTeller>current.getVerdi()) pathTeller=pathTeller-current.getVerdi();
else pathTeller=pathTeller+current.getVerdi();
  }
  else if(rnd==3&&kartet[t].getNed()!=null&&!(nedUsed)){
pathing[t]=current;
t++;
current=kartet[t].getNed();
if(pathTeller>current.getVerdi()) pathTeller=pathTeller-current.getVerdi();
else pathTeller=pathTeller+current.getVerdi();
  }
  if(current.getX()==linjeAntall&&current.getY()==linjeAntall){
i3=N*N;
  }

 }
 }

 System.out.print(bestPath.toString());
}

}

 

 

En nokså ineffektiv løsning, men håper det skal gå greit -_-

Endret 1. november 2012 av [email protected]

[SkoMedHull]

Det kommer vel litt an på hvor mye du kan fra før, selve dijkstras algoritme er ikke stor og vanskelig. Hvis du ikke er veldig komfortabel med å jobbe med grafer så blir det nok en del å lære.

 

Når det gjelder koden din ellers så ville jeg lært meg til å lage hjelpemetoder, altså dele problemet opp i mindre biter. Det du har der er en kandidat til å være den største metoden jeg har sett i mitt liv, det gjør ting litt vanskelig å lese, til tross for at du ellers skriver ryddig kode.

 

http://pastebin.com/0sRctL0P

 

Der har du min implementasjon av dijkstra, det var egentlig en slags spesialvariant, men har prøvd å gjøre den litt mer generell nå. Hvis du føler for det så kan du ta en titt.

 

Så lenge faget ditt er et programmeringsfag og ikke et algoritmefag så går vel alle løsninger greit så lenge de funker

[etse]

Om du ikke er ute etter noe som Dijkstras slgoritme (som egentlig er veldig simpel å implementere, selv om man må gjerne lese en del for å forstå den), så er egentlig ne bruteforce med å prøve alle alternativer det beste. Bare legge til en bounding og lagre den beste pathen du har funnet, og forkaste stier så fort de har høyere verdi (lengre sti) enn den beste. Da slipper du unna en del, men er fortsatt veldig treg.

[Gnurk!]

Hehe, jeg pleier å dele det opp og heller kalle metoder, men for å dele det opp så må man ha planlagt hvordan man skal lage det på forhånd, men er enig i at slike metoder er helt umulig å lese

(som du ser så er den 4 hodede noden jeg lagde delt opp, men den var mye lettere å planlegge.

 

Så på bruteforce nå, den virket mer praktisk å implementere for meg ja

 

tusentakk for hjelpa folkens, skal sette meg ned og implementere brute force eller værtfall en variant av den.

[etse]

Hehe, jeg pleier å dele det opp og heller kalle metoder, men for å dele det opp så må man ha planlagt hvordan man skal lage det på forhånd, men er enig i at slike metoder er helt umulig å lese

Jeg planlegger sjeldent hvordan koden skal se ut på forhånd. Men bare deler det opp underveis.

[Gnurk!]

Hehe, jeg pleier å dele det opp og heller kalle metoder, men for å dele det opp så må man ha planlagt hvordan man skal lage det på forhånd, men er enig i at slike metoder er helt umulig å lese

Jeg planlegger sjeldent hvordan koden skal se ut på forhånd. Men bare deler det opp underveis.

Ah jeg ble gitt det late-genet så å gå tilbake for å "fikse" no som allerede "fungerer" er kronisk umulig -_-

[etse]

Litt opptopic, men om du ønsker å lære deg programmering ordentlig er det en uvane du må legge fra deg. Når prosjektene blir litt større enn de du holder på med nå vil du virkelig hate deg selv om du ikke deler opp koden din mer. God struktur på koden er en av de viktigste tingene man har, da alle de andre viktige tingene blir så mye lettere om koden er godt strukturert.

 

Og viktig å huske på at kode skrives for å kunne leses av mennesker i første om gang.

Endret 2. november 2012 av etse