Brug for algoritme

Du får lige pseudo koden:

forbundet = false;
for(i=0;i<række.length-1;i++){
  if(række[i]==1 && række[i+1]==1)
    forbundet = true;
}

Hvad så hvis du har:

1 0 0 0
1 0 0 1
0 0 0 1

- er række 1 og 3 så forbundne? De er jo hverisær forbundne med række 2.

boolean testForbundet( int rekkeNr1, int rekkeNr2 ) {
    int sojleNr;
    for ( sojleNr=0; soejlenr<ditArray[].length; sojleNr++ ) {
        if ( ditArray[rekkeNr1][sojleNr] & ditArray[rekkeNr2][sojleNr] == 1 ) {
            return true;
        }
    }
    return false;            // ingen forbindelse fundet
}//endMethod testForbundet

->esbenp: Forstår ikke din kode-stump i forhold til mit eks.
->nielle: Ja, 1 og 3 er forbundne, fordi:
- række 1 og række 2 er forbundne via søjle 1
- søjle 1 og søjle 3 er forbundne via række 2
- række 2 og række 3 er forbundne via søjle 3
->jokoba: Forstår ikke din kode-stump i forhold til mit eks. Undersøger du ikke bare, om to rækker har 1 i en eller anden søjle? Det giver ikke, at række(0) og række(1) i mit eks. er forbundne, så vidt jeg kan se.

I jokob's kode står der: ditArray[rekkeNr1][sojleNr] & ditArray[rekkeNr2][sojleNr] == 1

Det ene & betyder "logisk og" hvilket betyder begge værdier skal være 1

Dit spørgsmål er et spørgsmål inden for den matamatiske diciplin som kaldes for "grafteori" (Graph Theory), og opgaven kan derfor løses hvis du downloader en af de mange java grafteori biblioteker der findes.

http://www.google.dk/search?hl=da&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=%22graph+theory%22+java+library&spell=1

På hvilken måde er det grafteori?

Tegn et antal punkter på et stykke papir – et punkt for hver række i dit 2-dimentionelle array. Du forbinder nu hvert punkt med en streg hvis de tilsvarende rækker er ”naboer”. Det du nu har tegnet, kaldes for en ”graf” og det er den slags grafer som graf teori handler om. En graf er altså ikke i denne sammenhæng noget med x- og y-søjler.

http://www.utm.edu/departments/math/graph/

Grafteori handler om egenskaber ved grafer. Bl.a. kan man spørge om hvor mange sammenhængs komponenter en given graf består af (connected components). Og det er faktisk netop det som dit spørgsmål går ud på.

>> ->nielle: Ja, 1 og 3 er forbundne, fordi:
>> - række 1 og række 2 er forbundne via søjle 1
>> - søjle 1 og søjle 3 er forbundne via række 2
>> - række 2 og række 3 er forbundne via søjle 3

uha, så er den sværere, nu skal der 2 metoder til:


  // tester om to rækker er umiddelbart forbundet med hinanden uden mellemled
  //
boolean testDirekteForbundet( int rekkeNr1, int rekkeNr2 ) {
    int sojleNr;
    for ( sojleNr=0; soejlenr<ditArray[].length; sojleNr++ ) {
        if ( ditArray[rekkeNr1][sojleNr] & ditArray[rekkeNr2][sojleNr] == 1 ) {
            return true;
        }
    }
    return false;            // ingen forbindelse fundet
}//endMethod testDirekteForbundet



  // tester om to rækker er forbundet med hinanden via gudved hvormange mellemled
  //
boolean testIndirekteForbundet( int rekkeNr1, int rekkeNr2 ) {

    int antalRekker = ditArray[].length;
    boolean[] forbundne = New boolean[antalRekker];
                          // husker alle rækker rekkeNr1 er forbundet med
    boolean[] tested    = New boolean[antalRekker];
                          // husker de rækker hvis forbindelser er blevet tested
    for (int i=0; i<antalRekker; i++ ) {
        forbundne[i] = false;
        tested[i] = false;
    }
    forbundne[rekkeNr1] = true;    // rekkeNr1 er pr definition forbundet med sig selv.

    do {
      boolean nyTest = false;
      for (int rNr1=0; rNr1<antalRekker; rNr1++ ) {
          if ( forbundne[rNr1] && ! tested[rNr1] ) {
              nyTest = true;          // vi har fundet en række hvis forbindelser skal testes
              for (int rNr2=0; rNr2<antalRekker; rNr2++ ) {
                  if ( ! forbundne[rNr2] ) {
                      forbundne[rNr2] = testDirekteForbundet( rNr1, rNr2 );
                  }
              }
              tested[rNr1] = true;    // den rækkes forbindelser er nu tested
          }
      }
    } while ( nyTest );

    return forbundne[rekkeNr2];    // hvis den er sand er der en forbindelse

}//endMethod testIndirekteForbundet

// de syntaksfejl der evt er er en gratis gave til dig.

Det er det rene bruteforce, så jeg vil vædde på at når i alle har givet jeres bud kommer instruktor med en smuk simpel og elegant løsning der er meget, meget hurtigere :-))

Jeg havde lidt om grafteori for et års tid siden, og dengang lavede jeg et program i C# med mulighed for minimal spanning trees, etc. - og også en metode til at finde om to punkter var forbundet.

public bool FindLink(int a, int b, int from)
{
    if (this.IsEdge(a,b))
    {
        return true;
    }
    ArrayList edges = new ArrayList();
    for (int i=0;i!=this.CountVertices() ;i++)
    {
        if (i!=from && this.IsEdge(a,i))
        {
            edges.Add(i);
        }
    }
    for (int i=0;i!=edges.Count;i++)
    {
        if (FindLink((int)edges[i],b,a))
            return true;
    }
    return false;
}

Det kan ikke DIREKTE bruges på dit problem, da dette som sagt refererer til punkter - men hvis nu vi laver lidt om på den, og jeg lige laver en hurtig konvertering til Java:

public bool FindLink(int a, int b, Vector from) //from er tom i dit første kald, a er din startrække og b din slutrække
{
    if (this.IsEdge(a,b)) //check om vi har en forbindelse lige her
    {
        return true;
    }
    Vector edges = new Vector(); //Opret en collection...
    for (int i=0;i!=antal_raekker ;i++) //lav en for-løkke der løber igennem alle dine rækker
    {
        if (!from.contains(i) && this.IsEdge(a,i))
        {
            edges.add(i); //... og føj de forbindelser der er til denne
        }
    }
        from.add(i); //Tilføj vores nuværende række til from, så vi ikke ender i et uendeligt loop
    for (int i=0;i!=edges.count;i++) //løb nu igennem vores collection
    {
        if (FindLink((int)edges[i],b,from)) //og kør denne metode med tallet fra vores collection som værdi for a
            return true;
    }
    return false;
}

Du skal så også lave en IsEdge metode, der checker om der er en direkte forbindelse fra a til b - den må så ligne jakoba's testDirekteForbundet.

Bemærk dog lige at oversættelsen der ikke er testet, men det burde være til at få op at køre uden alt for meget arbejde :)

Den direkte overdættelse af koden ser sådan her ud:

    public boolean FindLink(int a, int b, int from) {
        if (this.IsEdge(a, b)) {
            return true;
        }
        ArrayList<Integer> edges = new ArrayList<Integer>();
        for (int i = 0; i != this.CountVertices(); i++) {
            if (i != from && this.IsEdge(a, i)) {
                edges.add(i);
            }
        }
        for (int i = 0; i != edges.size(); i++) {
            if (FindLink(edges.get(i), b, a)) {
                return true;
            }
        }
        return false;
    }

Som man måske kan ane så er C# syntaksen inspireret *meget* af Java.

jespersahner> Hvad med noget respons?

->nielle: Jeg beklager den urimeligt lange svartid fra min side. Jeg har været travlt optaget af halvårsregnskab på mit arb., så derfor..

Jeg er helt enig i din bemærkning omkring grafteori. Selv har jeg faktisk fulgt et kursus i dette på 1. eller 2. år af mit studium, men det er en del år siden nu (jeg husker dog f.eks. 4-farve problemet :-)). Det viser sig i øvrigt, at problemstillingen nok er noget mere kringlet, end jeg lige havde forestillet mig i første omgang, så jeg skal lige tilbage og fundere lidt videre over det, inden jeg evt. vender tilbage.

Tak for de mange input, det er altid en fornøjelse!

Smid gerne et svar en eller flere af jer.

Jeg afstår nu fra point på denne her ... lad dem bare gå til dem som har postet egentlig kode. :^)

Jeg ved ikke om du mener jeg bør have point, men smider da lige et svar så du selv kan vælge :)