Nächsten Nachbar berechnen

Pylo

Mitglied
Hi, hab die Aufgabe einen Nächsten-Nachbar-Algorithmus zu implementieren. Will wissen, wie ich mit diesem Algorithmus 4 Knoten durchlaufen muss. Habe dazu 4 Funktionen gebaut:

Eine Main mit einer Beispielinstanz, die...
..die Funktion NearestNeighbor aufruft,welche den nächsten Nachbar zurückgeben soll, indem sie ...
..die Funktion minwert aufruft, welche den Index des Minimums eines Arrays zurückgibt und...
...die Funktion Routentest aufruft,welche testen soll,ob der nächste Nachbar schon auf der Route liegt.
Die Funktion Routentest will allerdings nicht wirklich und in meiner Route kommen Orte doppelt vor, was nicht sein soll.


Könnte mir da jemand helfen :)


Hier mein Code:
Java:
public class Nachbar {

private static int stadt =0;

private static int route[]=new int[5];


public static void main(String []args){
	
	//Beispielinstanz
	int array[][]=new int[4][4];
	int start= 0;
	array[0][0] = 9999;
    array[0][1] = 4;
    array[0][2] = 3;
    array[0][3] = 7;
    array[1][0] = 4;
    array[1][1] = 9999;  
	array[1][2] = 5;
    array[1][3] = 9;
    array[2][0] = 3;
    array[2][1] = 5;
    array[2][2] = 9999;  
    array[2][3] = 1;
    array[3][0] = 7;  	
    array[3][1] = 9;
    array[3][2] = 1;  
    array[3][3] = 9999;
   
  
   route[0]= start;
   System.out.println(route[0]);
   for(int i =1;i<route.length-1;i++){
  
   route[i]=NearestNeighbor(array);
   
   System.out.println(route[i]);
   }
   
 }
   
//Gibt nächsten Nachbar zurück   
   
   
   public static int NearestNeighbor(int matrix[][]){
	
    	
		int naechstestadt= Minwert(matrix[stadt]);
	   
            stadt = naechstestadt;
           
                    	
	
	return stadt; 
}	


   
//Berechnet das Minimum eines Arrays und gibt dessen Index zurück
   
   public static int Minwert(int[] arrays)
		{
			int minwertindex = 0;
			
			for( int i = 0; i < arrays.length; i++ )
			{
				if ( arrays[minwertindex] > arrays [ i ] && Routentest(route,i)==false )
				{
					
					minwertindex = i;
			}
			
		}
		return minwertindex;
	}
   
 //Routentest gibt an, ob sich eine Stadt bereits auf dem Weg befindet

 public static boolean Routentest(int[] route, int x) {
                for(int i = 0; i < route.length; i++) {
                        if(route[i] == x) {
                                return true;
                        }
                }
                return false;
       
}  
   
   
}
 
S

SlaterB

Gast
beschreibe doch bitte was die Zahlen in deiner Matrix konkret bedeuten
und welcher Nachbar denn der näheste ist von einem konkreten Beispiel-Knoten(?) aus gesehen,
wie löst du das ungefähr im Kopf/ auf Papier, was ist zu bedenken?
keine Idee zur Umsetzung dazu?
 

Pylo

Mitglied
Also array [j] gibt die Entfernung von Knoten i zum Knoten j an. Vom Knoten 0, wäre beispielsweise Knoten 2 der nächste, also sollte die Funktion NearestNeighbor 2 zurück geben.

Auf dem Papier würde ich es so lösen:Ich habe eine Knotenmenge K aus der ich einen Startknoten k1 wähle. Dann suche ich in einer Menge K' = K\{k1} den nächsten Nachbarn ki und speichere die Kante zwischen k und ki. Dann wird in einer Menge K'= K'\{ki} nach dem nächsten Nachbarn von ki gesucht.

In Java würde ich es theoretisch so machen, dass ich K durch ein Array darstelle, und dann aus K den neuen Array mit den Elementen von K ohne k1 erstelle. Allerdings weiß ich nicht , wie das in Java gehen sollte. Wenn da jemand nen Tipp hätte, wäre das Problem etwas einfacher zu lösen ;).
 
S

SlaterB

Gast
habe mir jetzt erst dein Programm genauer angeschaut, das sieht doch sehr gut aus, du kommst doch ziemlich weit?
es wird schon eine Route 0, 2, 3 gefunden, danach geht es allerdings wieder zu 0,
(edit: ok, so stehts fast auch im ersten Posting, dann hast du meine grundlegende Nachfrage ja stoisch ertragen ;) )

von 3 aus wäre 2 das kürzeste, aber 2 ist schon in der Route, wird nicht akzeptiert, gut,
1 wird abgelehnt weil das weiter Weg als 0 ist,
dabei wird aber davon ausgegangen dass 0 als Endwert ok ist, was allerdings nicht stimmt, da 0 ja in der Route ist,

starte mit
int minwertindex = -1;
und baue in der Schleife die Abfrage um, erst checken ob bereits in der Route,
von den möglichen Zielen das erste gefundene (minwertindex ist noch -1) als erstes min setzen, ansonsten vergleichen
 

Pylo

Mitglied
Hab mich jetzt nochmal dran versucht, es passt allerdings immer noch nicht ganz.
Meine Minwert-Funktion sieht jetzt folgendermaßen aus:

Java:
 public static int Minwert(int[] arrays)
		{
			int minwertindex = -1;
		    int i;
			for( i = 0; i < arrays.length; i++ )
			{
				if (Routentest(route,i)==false )
				{
					minwertindex =i;
					break;
				}
				
			}
			for(int j=i+1;j<arrays.length-1;j++)
                        {
					if (arrays[minwertindex]>arrays[j]){
					
						minwertindex=j;
					}
                         }
	return minwertindex;
}

Die erste Schleife soll den Ort suchen,der als erster noch nicht auf auf der Route liegt und wird verlassen, sobald einer gefunden wurde. Die zweite Schleife sucht dann ob es noch einen Ort gibt der noch näher liegt als der erste gefunde Ort.

Ergebnis ist 0,2,1,3 sollte aber 0,2,3,1 sein. Ich schätze mal die erste Schleife dürfte passen, aber die zweite macht noch nicht ganz das was sie soll. Hättest du da noch ne Idee Slater?
 
S

SlaterB

Gast
der Fehler ist natürlich in Sekunden zu sehen, aber da du so gut mitarbeitest nochmal Lehr-Versuch:
hast du kein Interesse daran, den Fehler systematisch selber zu finden?
du hast doch alle Array-Informationen vorliegen und einfachen Schleifen-Code, schaue dir doch ganz genau an was passiert,
wenn nicht direkt, dann z.B. unterstützt durch Debugger oder System.out.println()

erstelle dir ein Log a la
"untersuche Array ..., route ist bisher .."
"suche nun nach ersten Wert"
Schleife: "suche nach ersten Wert, Schleife, wir sind bei i = .., Erkenntnisse zu i = .. sind .., daher Folgerung (min gesetzt, Schleife Ende/ es geht weiter)"

"suche nun nach weiteren Werten in zweiter Schleife"
usw.

eigentlich banal, aber so kannst du millimetergenau verfolgen, wieso z.B. beim dritten Durchgang 1 statt 3 gewählt wird

-----------


Fehler sind:
- for(int j=i+1;j<arrays.length-1;j++)
hier ignorierst du per Arraygrenze -1 ohne Grund den letzten Arraywert, also die 3

- hier kein Problem aber allgemein wahrscheinlich fatal:
in der zweiten Schleife überprüfst du überhaupt nicht mehr, ob Element j schon in der Route drin ist

baue lieber nur eine Schleife:
Java:
for ..
   if schon in route ..
   else
      if erstes Element oder kleiner als min ..
fertig
 
Zuletzt bearbeitet von einem Moderator:

Pylo

Mitglied
Habe da vorhin etwas den Überblick verloren, so n Log ist da ne gute Idee. Sorry aber ich hab leider nicht viel mit Java zu tun, daher tu ich mich da etwas schwer. Auf jeden Fall vielen Dank für deine Geduld.:)


Hatte es vorhin auch schon mit einer Schleife versucht, allerdings bin ich da nicht auf die Bedingung gekommen, wie ich unterscheide ob ich einen Ort zum ersten Mal auswähle oder nicht (Auf minwertindex != 1 kommt man ja auch nicht so leicht:oops:)

Auf jeden Fall läufts jetzt und ich probier es mal an einer großen Instanz aus.

Danke Slater:toll:
 

Neue Themen


Oben