Hi,
ich muss für die Schule ein Backtracking Programm schreiben, dass das Spiel ,,Reise" (kürzesten Weg von A nach B suchen) implementiert.
Bis jetzt habe ich zwar ein Programm, dieses funktioniert aber nur mit der Klasse ,,Graph". Siehe hier:
Ich soll es aber wie bei unserem 8-Damen Programm machen, was wir bekommen haben. Siehe hier:
Wenn ihr mir helfen könntet wäre ich euch sehr verbunden.
mfg
ich muss für die Schule ein Backtracking Programm schreiben, dass das Spiel ,,Reise" (kürzesten Weg von A nach B suchen) implementiert.
Bis jetzt habe ich zwar ein Programm, dieses funktioniert aber nur mit der Klasse ,,Graph". Siehe hier:
Java:
public class Graph
{
private List myGraph; //Liste von GraphNodes;
public Graph()
{
myGraph = new List();
}
public void insertNode (String pName)
{
GraphNode node = new GraphNode(pName);
myGraph.insertBehind(node);
}
public List nodes ()
{
return myGraph;
}
public void connectNodes (String pName1, String pName2, double pWeight)
{
GraphNode node1 = searchNode(pName1);
GraphNode node2 = searchNode(pName2);
Edge edge1 = new Edge (node1, pWeight);
node2.insertEdge(edge1);
//Einfügen von edge1 in die Kantenliste von GraphNode node2
Edge edge2 = new Edge (node2, pWeight);
node1.insertEdge(edge2);
//Einfügen von edge2 in die Kantenliste von GraphNode node1
}
public GraphNode searchNode (String pName)
{
if(myGraph.isEmpty()== false)
{
myGraph.toFirst();
while(!(((GraphNode)myGraph.getItem()).name().equals(pName)))
{
myGraph.next();
if(myGraph.isBehind()==true)
{
return null;
}
}
return (GraphNode)myGraph.getItem();
}
return null;
}
public boolean track(GraphNode pStart, GraphNode pGoal)
{
List yourList = pStart.edges();
boolean a = false;
if(!yourList.isEmpty())
{
yourList.toFirst();
while(!yourList.isBehind())
{
if(pGoal.name().equals(((Edge)yourList.getItem()).neighbour().name()))
{
return true;
}
else
{
if( (((Edge) yourList.getItem()).neighbour()).isMarked()==false)
{
(((Edge) yourList.getItem()).neighbour()).mark();
a = track( ((Edge)yourList.getItem()).neighbour(),pGoal);
}
if (a==true)
{
return true;
}
}
yourList.next();
}
return false;
}
return false;
}
}Ich soll es aber wie bei unserem 8-Damen Programm machen, was wir bekommen haben. Siehe hier:
Java:
public class Search
{
private int dim = 8;
private MainWindow mainWindow; // Fenster fuer Ausgabe
private boolean[][] belegt; // gibt an, ob auf Feld x,y eine Dame steht
public Search( MainWindow win )
{
mainWindow = win;
// Thread starten
}
// Hauptfunktion des Threads
public void sucheNext() // Muss unbedingt public sein !!!
{
erfolgreich = false;
belegt = new boolean[dim][dim]; // Arrays initialisieren
for (int x=0; x<dim; x++)
{
for (int y=0; y<dim; y++)
belegt[x][y] = false;
}
recSearch(0); // Suche starten
}
// rekursive Suche Backtracking
private boolean erfolgreich = false;
private void recSearch(int spalte)
{
int zeile = -1;
while (zeile < dim-1 && !erfolgreich)
//weitere wahl möglich und noch nicht erfolgreich
{
zeile++;
if (isFieldOk (spalte, zeile))
//wahl annehmbar
{
setQueen (spalte, zeile);
//lösungsversuch aufzeichnen
if (spalte < dim-1)
//weitere wahl möglich
{
recSearch (spalte + 1);
//rekursiver aufruf auf tieferer stufe: trial
if (!erfolgreich)
// kein erfolg auf tieferer stufe: error
clearQueen (spalte, zeile);
//rücknahme des lösungsversuches
}
else
//keine weitere wahl möglich, also lösung gefunden
{
erfolgreich = true;
}
}
}
}
// Test, ob auf Feld x,y eine Dame platziert werden darf
boolean isFieldOk(int x, int y)
{
int zaehler = 0;
while (zaehler<=x)
{
if (belegt[x][zaehler] || belegt[zaehler][y])
return false; // Bedrohung senkrecht bzw. waagerecht
if (y-(x-zaehler)>=0 && y-(x-zaehler)<dim)
if (belegt[zaehler][y-(x-zaehler)])
return false; // Bedrohung diagonal von links oben
if (y+(x-zaehler)<dim && y+(x-zaehler)>=0)
if (belegt[zaehler][y+(x-zaehler)])
return false; // Bedrohung diagonal von links unten
zaehler++;
}
return true; // keine Bedrohung gefunden, Feld erlaubt
}
// Dame auf Feld setzen und Array anpassen
void setQueen( int x, int y )
{
if (!belegt[x][y])
{
belegt[x][y] = true;
mainWindow.setQueen(x ,y); // Grafik-Ausgabe
}
}
// Dame von Feld entfernen und Array anpassen
void clearQueen(int x, int y)
{
if (belegt[x][y])
{
belegt[x][y] = false;
mainWindow.clearQueen(x ,y); // Grafik-Ausgabe
}
}
}Wenn ihr mir helfen könntet wäre ich euch sehr verbunden.
mfg
