Distanzen mit Brute Force

[sinclair]

hallo leute
folgende Problematik, hoffe auf hilfe.
ich probiere gerade das Problem des reisenden darzustellen, fülle eine liste mit 4 städtte.
Nun weiss ich jetzt nicht wie ich jede Stadtdistanz mittels brute force ermitteln.
allgemein, ich tuh mich schwer algroythmen zu entwickeln, ist das normal am anfang und braucht das seine zeit?
folgend die Methode (lediglich codfragmente)
der andere code ist für die Verständlichkeit unwichtig.

//city 1, city 2
		 int c1 = 0, c2 = 1;
//getMoeglichkeiten, gibt die Möglichkeiten zurück, welche möglich sind (ab, ba, usw...)
		 for (int i = 0; i < getMoeglichkeiten(cityList.size()); i++)
		 {
		 double d = distanceTo(cityList.get(c1), cityList.get(c2));
		 distanzen.add(d);
		 c2++;
		 if (c2 == cityList.size())
		 {
		 c1++;
		 c2 = 0;
		 }
		 if (c2 == c1)
	 {
	 c2++;
 }
		 }
		 
		return distanzen;
	}

meine Idee ist folgende:
jede Distanz wird in eine liste gespeichert, mein Problem wie soll ich sagen, dass z.b Stadt 4-1 ist der kürzesste weg, dann Stadt 2-1 usw?
ich hoffe ihr versteht mich..

 

[Joose]

Bitte Java-Code immer zwische

-Tags schreiben, danke! :)

 

[Gucky]

Ja das ist normal. Irgendwann fängt der Ände sozusagen am mit dir zu sprechen. Dann fällt es dir auch leichter.

Vielleicht wäre es besser, du gäbest jeder Stadt Koordinaten und berechnest mithilfe von Pyhagoras die Entfernungen.

 

[JavaMeister]

Vielleicht wäre es besser, du gäbest jeder Stadt Koordinaten und berechnest mithilfe von Pyhagoras die Entfernungen.

Quatsch. Das sind keine räumlichen Entfernungen, sondern Kosten im Sinne der Graphentheorie.

Zu der Frage an sich kann ich nicht sagen, weil ich die Frage nicht verstanden habe.

 

[sinclair]

Vielleicht wäre es besser, du gäbest jeder Stadt Koordinaten und berechnest mithilfe von Pyhagoras die Entfernungen.

Quatsch. Das sind keine räumlichen Entfernungen, sondern Kosten im Sinne der Graphentheorie.

Zu der Frage an sich kann ich nicht sagen, weil ich die Frage nicht verstanden habe.

hallo
danke für eure schnellen antworten, habt mich positiv überrascht..
was hast du genau an der frage nicht verstanden?

also:
ich habe ein objekt city, da füll ich die x und y kordinaten ein. in der mainklasse, füll ich die einzelnden städtte in eine arrayliste rein.
nun habe ich eine Methode erstellt, welche mir alle Möglichkeiten gibt Beispiel:
wir haben die städtte 1,2,3..
also gibt es 6 Möglichkeiten (1*2*3).
das ging reibungslos von statten.
die andere aufgabe besteht darin mittels brute force, die Distanzen jeder Kombination zu bestimmen.
und damit tuh ich mich gerade schwer, ich habe was ausprobiert, aber dies ist für die katz. ich persönlich glaube aber, ich bin auf dem richtigen weg, nur jemand muss den code mal genauer anschauen und die verbesserung schreiben^^..
danke..

 

[Gucky]

Also doch Pytagoras.

 

[JavaMeister]

Also doch Pytagoras.

Ja sorry, hätte man beim Ausgangspost und Travel Sales Man Problem überhaupt nicht gedacht ;D

 

[arilou]

(Annahme: Die "Koordinaten" der Städte sind Längen- und Breitengrade.)
Eigentlich müsste man Luftlinien-Distanzen auf der Kügeloberfläche berechnen - Zitat Wikipedia: Die kürzeste Verbindung zwischen zwei Punkten auf einer Kugeloberfläche ("Orthodrome") ist immer Teil eines Großkreises.

Vmtl. würde man das am besten rekursiv lösen, à la
"jede Stadt der aktuellen (Rest-)Menge kann nächste Stadt sein" -> for-Schleife
innerhalb dann: (rekursiv) wähle restlichen Weg (basierend auf jeweiliger Restmenge an Städten)
Jeweiliger Methoden-Rückgabewert ist dann kürzesterWeg( Wegstrecke vorige Stadt zu aktueller + Restweg_länge )

Oder so ähnlich.

 

[sinclair]

hallo leute

sorry, das ich erst jetzt antworte, aber heute steht wider Java auf dem Programm (für mich).
es gibt eine gute Nachricht:
ich habe das Problem gelöst:

for (int c1 = 0; c1 < cityList.size(); c1++)
        {
            for (int c2 = c1 + 1; c2 < cityList.size(); c2++)
            {
                double d = distanceTo(cityList.get(c1), cityList.get(c2));
        }
        }

cityList stellt die liste da, welche der Methode übergeben wird. in dieser liste sind 10 städte mit Distanzen zu finden.
das funktioniert, meine frage:
ich möchte das gerne rekosiv lösen, geht das überhaupt? wenn ja, habt ihr mir einen Ansatz?
kann man eigentlich immer Sachen rekosiv lösen- die man auch mittels schleife lösen kann?
thx für eure antwort^^.
kleine Anmerkung:
ich probiere das in Java-tags zu verpacken, das nächste mal klappts sicher....

 

[Gucky]

Die Java Tags kanndt du einfach tippen. Ich benutze zum Beispiel nie die Schaltfläche.

 dein Code [ /JAVA] ohne Leerzeichen im Tag.

Man kann alles, was sich iterativ (mit Schleife) lösen lässt auch rekursiv lösen.
Das rekursiv zu lösen wird dir außer Wissenszuwachs nichts bringen aber vermutlich ist das dein Plan. :D

Einen Ansatz habe ich leider nicht für dich, weil ich selber keine Ahnung habe :D
Ich müsste noch ein bisschen überlegen.

 

[sinclair]

hallo^^
die Problematik meiner Meinung nach ist in dieser Methode, dass ich vor der schleife eine liste erstelle, in dieser verpack ich die Distanzen, siehe code:

private List<Double>getBestDistanze(ArrayList<City> cityList)
	{
		List<Double> Distanzen =new ArrayList<Double>();
//wieso ist es besser, wenn man Interface list gerade verwendet und man nicht direkt ArrayList?
	
		for (int c1 = 0; c1 < cityList.size(); c1++)
		{
			for (int c2 = c1 + 1; c2 < cityList.size(); c2++)
			{
				double d = distanceTo(cityList.get(c1), cityList.get(c2));
				
		}
}

meiner Meinung nach:
wenn ich die Methode rekosiv aufrufe, erstellt es mir ja ständig eine neue liste, oder?

 

[Gucky]

Du kannst entweder die Restliste übergeben, was speicherplatztechnisch ein Desaster wäre, sobald du mehr Städte verwalten möchtest oder du übergibst eine Referenz auf die Liste und den aktuellen Index. Dann könntest du aber auch iterativ bleiben.

 

[arilou]

Wenn man es rekursiv lösen möchte, so muss man Permutationen der Städtemenge abbilden.
Und in den Zwischenschritten muss man wissen, welche Städte schon "weg sind", und welche noch "zur Verfügung stehen". Das ohne veränderliche Listen anzustellen, ist eine Herausforderung.

 

[sinclair]

hallo leute^^
mit anderen worten, in diesem fall- sollte ich das rekursive lassen und mir als Übung ein anderes Problem suchen..
nun gut, eigentlich ist das ja leider nur ein zwischenschritt zur lösung meines Problems, die aufgabe war eigentlich- alle Möglichkeiten mittels brute force zu testen und dann die beste rausfinden.
folgende Überlegung: wir haben drei städtte:
jetzt muss ich alle Kombinationsmöglichkeiten rausfinden d.h:
1-2, 1-3, 2-1, 2-3, 3-2, 3-1
der unterschied zum anderen ist dieser, dass ich jetzt auch zurückdenken muss, sprich: 3-2, 3-1
sorry, ist ein wenig schwierg zu erklären, aber ich glaube, ihr habt mich verstanden^^..
was habe ich bis jetzt- eine Methode, die mir alle Möglichkeiten ausrechnet, die möglich sind, diese möchte ich irgendwie als abbruch Bedingung diffenieren:

public int getMoeglichkeiten(int groesse)
	{
if (groesse > 1)
		{
			return groesse * getMoeglichkeiten(groesse - 1);
		} else
		{
			return 1;
		}

und da endet mein latain, ich habe überhaupt keine Ahnung, wie ich die städte mittels brute force ermitteln soll. hatte schon bei der ersten aufgabe ziemlich viel Schwierigkeiten, da scheint es mir fast unmöglich zu sein, selber auf eine lösung zu kommen.
gut, das positive ist, ich habe noch dieses Wochenende zeit

 

[arilou]

Zuerst musst du mal sauber (gedanklich und im Programm) trennen zwischen

• Matrix der Einzeldistanzen zwischen jeweils 2 Städten UND
• Liste einer Besuchsreihenfolge.

Die Matrix erstellt man natürlich vorab, aber "per Brute-Force die kleinste finden" bezieht sich auf zweiteres.

Stichwort "Permutation ohne Wiederholung".

Ich bin mir nicht sicher, ob Gucky das Problem verstanden hat. Sofern die Anzahl der Städte variabel bleiben soll (d.h. das Programm soll genauso für 5, 6 oder 8 Städte funktionieren), wird eine iterative Lösung wohl nicht ganz einfach ; es ist eben ein NP-Problem, kein P.

Genauer:
Für 4 Städte könnte man (4-1) verschachtelte Schleifen bauen:

for( position pA der ersten Stadt = 1..4 ) --> 4 Iterationen
  for( position pB der zweiten Stadt = 1..4 ohne den bereits belegten Platz pA ) --> 3 Iterationen
    for( position pC der dritten Stadt = 1..4 ohne pA, ohne pB) --> 2 Iterationen
      platziere vierte Stadt an letzter freier Position --> "1 Iteration"

Summa summarum 4*3*2*1 Durchläufe.
Problem: Für 5 Städte braucht man eine for-Schleife zusätzlich --> Programmcode-Änderung
Und für 6 Städte, 7, 8, ...
D.h. man muss iterativ mit Listen arbeiten, was Guckys Einwand "speicherplatztechnisch ein Desaster" vmtl. egalisiert. Wie man das genau hinkriegt, müsst' ich jetzt länger drüber nachdenken.

 

[sinclair]

hallo

sorry, aber das gedanklich trennen verstehe ich nicht so recht..
ich habe mal was gemacht:

double distanzen = 0; //Adition der gesammtstrecke
	int c1 = 0, c2 = 1; //stellt die Städtte da
		

int durchgaenge =0; //soll die abbruchbedingung difinieren, sprich wieviel Variationen möglich sind
		while (durchgaenge < getMoeglichkeiten(cityList.size())) //Methode welche die Möglichkeiten zurückgibt
		{
			distanzen += distanceTo(cityList.get(c1), cityList.get(c2)); //Stadt1 und zwei, Distanz wird ausgerechnet und addiert
			c2++;
			
			if(c2==c1) //dieses if kann man erst verstehen, wenn man das andere if angeschaut hat. 
			{
				c2++; //wenn c2 und c1 gleich sind, dann setze c2 um eins hoch.
			}

			if (c2 >= cityList.size()) //Wenn c2 das ende der Liste erreicht hat, dann setze c1 hoch 
			{
				c1++; //c1 hat jetzt den eintrag von c2 (2)
c2=c1-1; //c2 hat jetzt den eintrag von c1 (1)
			}
durchgaenge++;
		}

	}

ich weiss jetzt nicht, ob man das versteht..^^
was denkt ihr? es sieht ein wenig unübersichtlich aus, aber so müsste es doch funktionieren, oder?

 

[arilou]

ich weiss jetzt nicht, ob man das versteht..

Dann ist entweder

• das Programm schlecht dokumentiert, oder
• (wahrscheinlich) hast du selbst noch nicht ganz verstanden, was du eigentlich zu tun hast.

Vielleicht solltest du noch mal ganz neu anfangen, und erst mal nur (grobe) Kommentare schreiben, welche logischen Schritte eigentlich tatsächlich nötig sind (siehe Top-down). "Überschriften".

 

[sinclair]

hallo

sorry, vergisst ganz schnell was ich euch gesagt habe.. ich habe wirklich- die aufgabe nicht verstanden.
die Idee ist, es muss ein pfad sein.
meine Überlegung mit:
12, 13 usw.. war für die katz:
es müsste wie folgt sein:
bei 3 städtte:
123/213/231, sprich jede Stadt kommt einmal vor.
Gott, ich bin ein *****^^..
und gerade wollte ich die aufgabe einschicken

 

[jgh]

alle Fragen geklärt?

 

[arilou]

Nun, zumindest hat er ja das Wochenende noch Zeit
Und wenn er's jetzt richtig verstanden hat, kommt auch die Lösung in Reichweite.

 

[sinclair]

lass mal den thread offen, ich probiere das Problem zu lösen..
wenn jemand gerade was schnell hingeschnipsselt hat, nicht bescheiden sein, ihr könnt es mir zeigen^^..
spass bei seite:
ich wäre ehrlich gesagt froh, wenn jemand mir unter die arme greifen könnte.. die Erklärung auf Wikipedia habe ich ehrlich gesagt nicht so verstanden.. aber war vermutlich zu blöd für das..

 

[sinclair]

hallo leute

des lösungs Problem will ich euch nicht enthalten..
zu meiner schande muss ich sagen, dass das eine diskret kopierter code vom netz ist^^..
meiner Meinung nach- hervorragend. ich wäre in den nächsten 2000 jahren nicht drauf gekommen, gut 2000 ist ein wenig übertrieben, vermutlich würden auch 1000 reichen..

public List<List<City>> bruteForceFindPerm(List<City> cityList)
	{
		if (cityList.size() == 0)
		{
			List<List<City>> resultat = new ArrayList<List<City>>();
			resultat.add(new ArrayList<City>());
			return resultat;
		}
		City firstElement = cityList.remove(0);
		List<List<City>> returnValue = new ArrayList<List<City>>();
		List<List<City>> permutations = bruteForceFindBestWay(cityList);
		for (List<City> smallerPermutated : permutations)
		{
			for (int index = 0; index <= smallerPermutated.size(); index++)
			{
				List<City> temp = new ArrayList<City>(smallerPermutated);
				temp.add(index, firstElement);
				returnValue.add(temp);
			}
		}

		return returnValue;

}

frage an die Anwender, die im beruf stehen:
nach wieviel Monaten konntet ihr reibungslos programmieren?

 

[JavaMeister]

}

frage an die Anwender, die im beruf stehen:
nach wieviel Monaten konntet ihr reibungslos programmieren?

Als ich angefangen habe als Student nebenbei zu arbeiten, konnte ich kein oop und hatte nur ein wenig PHP wissen. Nach einem Monat habe ich selbstständig in Java in einem kommerziellen Produkt gearbeitet.

 

[arilou]

"reibungslos"? Kommt auf die Definition dieses Begriffs an.
Ich programmier' nun seit 31 Jahren, davon 15 in Java, und noch immer gibt's Seiten an Java, über die ich noch was lernen kann.

 

[Gucky]

Es kommt auch darauf an, was du programmieren willst. Ein Programmierer, der für Epic am Raytracing System der Unreal Engine arbeitet, wird vermutlich beim Programmieren einer Anwendung für Banken (Mathematik, Sicherheit) kläglich versagen.

Damit meine ich, dass du in einem Bereich vielleicht gut wirst aber in Anderen wirst du nicht so "reibungslos" programmieren können.

 

[sinclair]

danke für eure antworten^^..
eine kleine frage habe ich aber noch, kann man folgenden rekursiven aufruf in einem thread verpacken?
[Java]
public static List<List<City>> bruteForceFindBestWay(List<City> cityList)
{
if (cityList.size() == 0)
{
List<List<City>> resultat = new ArrayList<List<City>>();
resultat.add(new ArrayList<City>());
return resultat;
}
City firstElement = cityList.remove(0);
List<List<City>> returnValue = new ArrayList<List<City>>();
List<List<City>> permutations = bruteForceFindBestWay(cityList);
for (List<City> smallerPermutated : permutations)
{
for (int index = 0; index <= smallerPermutated.size(); index++)
{
List<City> temp = new ArrayList<City>(smallerPermutated);
temp.add(index, firstElement);
returnValue.add(temp);
}
}

return returnValue;

}
[/code]

 

[arilou]

Ich hab' obigen Code nur kurz überflogen, aber mir scheint:
a) Dass obiger Code nur Permutationen erzeugt; es werden nirgends Distanzen gerechnet/aufsummiert und mit anderen Wegen verglichen.
b) Natürlich kann man das Ganze in _einen_ Thread packen, z.B. damit eine GUI nicht blockiert wird. Alternativ: für den rekursiven Aufruf jeweils einen neuen Thread aufmachen. Geht natürlich auch, aber gibt viel zu viele Threads. Das müsste man auf die ersten 1-2 "Tiefen-Stufen" beschränken.

 

[sinclair]

hallo

sorry, es ist natürlich nur eine Methode, die die permotationen/Möglichkeiten ausrechnet.. habe nicht den ganzen code reinkopiert..
habe mich mal kurz informiert:
es gibt irgend eine Fork und Join klasse, ich weiss allerdings nicht, wie ich sie für mein Beispiel benutzen könnte???