# Optimierungsproblem



## ceyf (1. Jan 2010)

hallo
ich habe problem mit tsp. ich habe ein programm geschriben, das der kürzeste tour von anfangsknoten bis wieder zu anfangsknoten findet. es funktioniert bei kleinen graphen, bei großen nicht. wie kann ich das Programm ändern,damit es eine optimierte lösung findet. hier ist proramm code.ich bin für jeden Hilfe dankbar. lg


```

```


----------



## SlaterB (1. Jan 2010)

- Beispielgraph der funktioniert angeben (den muss man doch mühevoll Knoten per Knoten programmieren, denkst du das macht jemand?)
- Beispielgraph der nicht funktioniert angeben
- erklären was der Algorithmus machen soll, wie er vorgeht, quasi die Beispiele per Hand nachrechnen, welcher Knoten wann warum gewählt wird

-> dann könntest du eigentlich auch schon selber im Programm mitloggen, was stattdessen passiert,
und normalerweise mühelos die Unterschiede erkennen

----

oder fragst du unabhängig von deinem Programm nach einen neuen korrekten Algorithmus?


----------



## Landei (1. Jan 2010)

Zusätzlich zu den Tipps meines Vorredners: Mach den Graphen, der geht, schrittweise größer, bis er nicht mehr geht. Daran sieht man meistens, woran es scheitert.


----------



## SegFault (1. Jan 2010)

Klingt wie das Travelling Salesman Problem. Dort die optimale Tour zu finden ist eh enorm schwierig da immer alle fälle durchprobiert werden müssen um die optimalste Route zu garantieren. Das ist bei größeren Graphen zu aufwendig.


----------



## Marco13 (1. Jan 2010)

ceyf hat gesagt.:


> hallo
> ich habe problem mit tsp.





SegFault hat gesagt.:


> Klingt wie das Travelling Salesman Problem.



Könnte man meinen, ja 

Es gibt natürlich Algorithmen, die die optimal(st?)e Tour finden, auch OHNE wirklich alle Kombinationen durchzuprobieren, und jede Menge Heuristiken. Die könntest du verwenden. Du willst ja nach eigener Aussage nur eine _optimierte_ (und nicht DIE optimale) Lösung...


----------



## ceyf (1. Jan 2010)

hallo leute, 
vielen dank mal vorab für eure Antworten. Ich glaube ich hab mich nicht so gut ausgedrückt. Also ich habe im Anhang eine Grafik hinzugefügt. Ja das stimmt, ich versuch nicht die optimalste, sondern eine optimale Lösung. 

Also so etwas möchte ich programmieren. In unserem Fall gibt es 5 Knoten, die mit gewichteten Kanten verbunden sind. Das ganze ist ein vollständiger Graph. Mein Startknoten ist immer 0. Jetzt sollte das Programm alle Nachbarknoten betrachten und den Knoten,  mit dem kleinesten Kantengewicht davon finden. Also müsste er den Knoten 3 wählen, danach wieder weiter schauen, die kleinste Kante nehmen usw. und somit den günstigen Weg vom Startknoten zu allen Knoten finden ohne Zurückgehen. 

Mein Progr. arbeitet folgendermaßen: Er gibt zwar kein Fehler aus, aber liefert auch nicht das richtige Ergebnis. Mein Algorithmus findet alle möglichen Wege, und wählt dann den Weg mit den geringsten Kosten. 

Das war nur mal mein Programmierversuch, ich würde mich auch über andere Ansätze freuen. Vielen Dank!


----------



## Marco13 (1. Jan 2010)

Erstmal dazu Adjektiv: Steigerung: keine Steigerungsformen

Ansonsten wäre ein KSKB schon hilfreich (siehe SlaterBs erste Antwort). Ich gehe nämlich davon aus, dass deine Beschreibung nach "Mein Progr. arbeitet folgendermaßen:" eigentlich hinter einem Satz wie "Als ich mein Programm geschrieben habe, wollte ich, dass es folgendermaßen Arbeitet" stehen müßte.


----------



## SlaterB (1. Jan 2010)

ja, ein Graph als Bild ist schon ganz praktisch für die Übersicht, ebensowichtig wären aber die 20 Zeilen Code im Programm,
du hast das doch schon getestet, muss alles vorhanden sein, auch die Klasse Edge


----------



## javimka (1. Jan 2010)

Welche Datenstruktur repräsentiert denn deinen Graphen? Wie verhinderst du, dass der Algorithmus einen Knoten zwei mal besucht? 

Als Representation würde sich eine (symmetrische) Matrix bzw. int[][] array anbieten. Wenn du dann einen Knoten p besuchst und wieder verlässt, müsstest du die ganze p-te Zeile und p-te Spalte auf unendlich setzen, damit dieser Weg auf keinen Fall mehr genommen wird.

Kann man davon ausgehen, dass alle Wege einen positiven Wert Wert haben?

Ein anderer Ansatz wäre übrigens das Branch-And-Bound-Verfahren. Es findet den allerbesten Pfad.


----------



## Yamato (2. Jan 2010)

Wie schon kurz angesprochen ist die Berechnung der besten Tour NP-vollständig und daher nach jetzigem Kenntnisstand nicht in Polynomialzeit lösbar.

Man kann aber "fast" optimale Touren berechnen, z. B. mit der folgenden allgemeinen Lösungsmethode:


```
import java.util.*;
import java.io.*;

public class TSP
{
	public static int[] solve_TSP(double[][] dist)
	{
		int n = dist.length, i, j, i00, i01, i10, i11, swap;
		int[] tour, solution = null;
		double length, best = 0, cut;
		boolean condition = true;
		Random rnd = new Random();
		
		for (int round = 0; round < n; round++)
		{
			tour = new int[n];
			for (i = 0; i < n; i++)
				tour[i] = i;
			if (n < 4) return tour;
			for (i = n - 1; i > 0; i--)
			{
				j = rnd.nextInt(i + 1);
				swap = tour[j];
				tour[j] = tour[i];
				tour[i] = swap;
			}
			length = 0;
			for (i = 0; i < n - 1; i++)
				length += dist[tour[i]][tour[i + 1]];
			length += dist[tour[n - 1]][tour[0]];
			while (condition)
			{
				condition = false;
				i00 = 0;
				i01 = 1;
				while (i00 < n - 2)
				{
					i10 = i01 + 1;
					i11 = i10 + 1;
					while (i10 < n)
					{
						if (i11 == n)
						{
							if (i00 == 0) break;
							i11 = 0;
						}
						cut = (dist[tour[i00]][tour[i01]] + dist[tour[i10]][tour[i11]])
							- (dist[tour[i00]][tour[i10]] + dist[tour[i01]][tour[i11]]);
						if (cut > 0)
						{
							condition = true;
							i = i01;
							j = i10;
							while (i < j)
							{
								swap = tour[j];
								tour[j] = tour[i];
								tour[i] = swap;
								i++;
								j--;
							}
							length -= cut;
							break;
						}
						i10++;
						i11++;
					}
					if (condition) break;
					i00++;
					i01++;
				}
			}
			if ((solution == null) || (length < best))
			{
				solution = tour;
				best = length;
			}
		}
		
		return solution;
	}
}
```

Im Array dist[][] stehen die Entfernungen zwischen den Knoten (also dist_[j] = Entf. zwischen Knoten i und j). Im von der Methode zurückgegebenen int-Array stehen die Nummern der zu besuchenden Knoten in der entsprechenden Reihenfolge. Die Tour beginnt aber nicht zwangsweise mit 0, sodass du die Indizes entsprechend verschieben musst._


----------



## Marco13 (2. Jan 2010)

@Yamato: Hat diese Methode auch einen Namen?

@Topic: Es ist ja tatsächlich so, dass man, um die optimale Lösung zu finden, "nur" alle Permutationen der Liste von Knoten durchprobieren, jeweils die Kosten berechnen und die Permutation mit den Minimalen Kosten speichern muss. (Das könnte man z.B. mit dem PermutationIterable von http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html machen).


----------



## JohannisderKaeufer (2. Jan 2010)

Aus n Knoten -> n-1 Kanten

Man nehme die kürzesten n-1 Kanten und summiere diese auf.
Nun hat man das "minimum" erreicht.

Nimmt man jetzt einen Brute-Force-Ansatz, so kann man daraus ein Abbruchkriterium herleiten.

Bei der Auswahl der n-1 Kanten, kann man auch Restriktionen, wie nur die kürzesten 2 Kanten, die zu einem Knoten führen, zuzulassen.


----------



## javimka (2. Jan 2010)

Ein Kreis mit n Knoten braucht auch n Kanten, nicht n-1.


----------



## ceyf (2. Jan 2010)

@Yamato: Welche Algorithmus ist das? Kannst du vielleicht dein Programm ein bisschen erklären? ich habe nicht so gut verstanden.danke.lg


----------



## Yamato (2. Jan 2010)

Es handelt sich um eine Heuristik, siehe k-Opt-Heuristik ? Wikipedia
Daneben gibt es noch andere interessante Heuristiken, z. B. Ameisenalgorithmen: Wapedia - Wiki: Ameisenalgorithmus.


----------



## ceyf (4. Jan 2010)

hallo, Yamato
bei deinem programm habe ich nicht gesehen, dass das Anfangsknoten wieder am Ende kommt. oder habe ich falsch gesehen.
lg


----------



## Yamato (6. Jan 2010)

Der Anfangsknoten ist hier auch der Endknoten. Das wird nur nicht explizit gespeichert, da es (implizit) klar ist. Die Tour geht vom letzten Knoten der Liste zurück zum ersten.


----------

