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
