Hamilton Pfad ??

[Morbo]

Hallo!

vielleicht kann mir jemand von euch weiterhelfen!? ..ich haeng schon seit ner gewissen Zeit am rumprogrammieren um alle moeglichen Pfade (von eingelesenen Knotpunkten) durchzugehen. Das Ganze ist in Java und ich bin absolut am verzweifeln weil ich nicht weiss was da falsch laeuft.

Naja vielleicht weiss einer von euch Bescheid und kann mir nen guten Tipp geben?

Waer auf jeden Fall sehr dankbar dafuer !

ciao,

Timm

[Klotzkopp]

Das Ganze ist in Java und ich bin absolut am verzweifeln weil ich nicht weiss was da falsch laeuft.

Dann zeig doch mal deinen Code und erkläre, wie sich das "falsch laufen" darstellt. Das ist sicher einfacher, als hier komplett neu anzufangen.

Falls es um ein sprachspezifisches Problem geht, bist du womöglich im Java-Forum besser aufgehoben, aber auch das können wir erst am Code erkennen.

[Morbo]

Ja du hast Recht, vielleicht ist das praktischer. Ich habe hier eine Form von dem Code (hab mindestens 6 verschiedene und jedes Mal was Neues probiert). Ach so und es ist auf niederlaendisch, aber ich schreib mal dazu was da so theoretisch passieren sollte:

import java.io.*;

import java.util.*;


public class Hamilton

{

    public static int[][]weg;

    public static int[]pad;

    public static  int lengte;


    public static void main(String[] args)

    {

        weg = new int[18][3];   //die verschiedenen Wege werden darin gesp. 

        pad = new int[0];         // hier wird der jetzige Pfad gesp.

        try{  

            inlezen("graafhamilton.txt");

        } catch(Exception e) {}

    }


    public static void inlezen(String invoer) // liest den Text mit den Wegen ein

        throws Exception

    {

        File file = new File(invoer);

        Scanner scanner = new Scanner(file);


        while(scanner.hasNext())

        {

            int a, b, c;

            a = scanner.nextInt();

            b = scanner.nextInt();

            c = scanner.nextInt();


            weg[a][b] = c;

            weg[b][a] = c;

        }

        zoekPad(1,0); // Pfad beginnt immer bei 1, und Laenge ist erstmal 0

    }


    public static void zoekPad(int begin, int lengte) //sucht einen Pfad

    {

        if(pad.length == 13) // ein Pfad besteht aus 13 Punkten, dann 

        {                          // ausdrucken

            print();

            pad = new int[1];  // neuer Pfad

            begin = 1;

            pad[0] = begin;

            lengte = 0;

        }


        for(int eind = 0; eind < 18; eind++) // geht alle Reihen im Array durch

        {

            if(feasible(begin,eind))  // schaut ob der Pfad ueberhaupt besteht

            {

                registreer(eind);     // speichert den Pfad in nem anderen Array

                zoekPad(eind, lengte+weg[begin][eind]); // rekursiv, ruft die   

                                             // Methode wieder auf mit dem neuen Punkt

                //deregistreer(eind); // falls der weg nicht zuende gefuehrt 

        }                                  // werden kann, muss der Punkt wieder 

    }                                    // aus dem Array raus. Mein groesstesProblem!

    }

    public static void registreer(int nieuwPunt) // registreert den Pfad

    {

        int[] nieuwPad = new int[pad.length+1];

        for(int i = 0; i< pad.length;i++)

        {

            nieuwPad[i] = pad[i];

        }

        nieuwPad[nieuwPad.length-1] = nieuwPunt;


        pad = new int[pad.length+1];

        for(int i = 0; i < pad.length;i++)

        {

            pad[i] = nieuwPad[i];

        }

    }


    public static boolean feasible(int begin, int eind) 

    {

        for(int i = 0; i<pad.length;i++) // checkt obs den Punkt im Pfad schon gibt

        {

            if(pad[i] == eind)

            {

                return false;

            }

        }


        if(weg[begin][eind] == 0) //checkt obs den Weg zw. den Punkten ueberhaupt gibt

       { 

        return false;

        }


         return true;

    }


    public static void print()

    {

        for(int i = 0; i < pad.length; i++) // druckt den Pfad aus

        {

            System.out.print(pad[i]);

        }

        System.out.println(lengte); // und die Laenge

    }    

}

Ja also es ist vll nicht ganz uebersichtlich. Ich glaub,dass es nen Logikfehler ist, aber ich komm da einfach nicht dahinter.

Wenn du ne Idee hast, waer ich dir sehr dankbar.

ciao

Timm

[Klotzkopp]

Du schreibst zwar im Kommentar, dass der Pfad bei Punkt 1 beginnt, aber der erste Punkt, der durch registreer eingetragen wird, ist der, den du von Punkt 1 aus erreichen kannst. Das könnte z.B. Punkt 0 sein, je nachdem, was in der Textdatei steht. Es ist jedenfalls nicht Punkt 1.

Überhaupt ist deine Behandlung für pad.length == 13 problematisch. Du kannst nicht einfach tief in der Rekursion das Array wegwerfen. Die Rekursion sollte von selbst das Array schön wieder abbauen (deregistreer), mehr als ein Aufruf von print sollte da gar nicht notwendig sein.

Ist es sicher, dass es immer 13 Punkte und 18 Verbindungen sind?

[Morbo]

Hey danke fuer die Antwort.

Ich habs im Endeffekt Sonntag morgen um 6 Uhr hinbekommen! ... ich hatte vorher echt voll den Denkfehler drin...

ciao,

Timm