Optimierungsproblem

C

ceyf

Mitglied
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

Java:
 
Zuletzt bearbeitet:
S

SlaterB

Gast
- 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

Landei

Top Contributor
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.
 
S

SegFault

Bekanntes Mitglied
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.
 
M

Marco13

Top Contributor
C

ceyf

Mitglied
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!
 
M

Marco13

Top Contributor
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.
 
S

SlaterB

Gast
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
 
J

javimka

Top Contributor
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.
 
Y

Yamato

Aktives Mitglied
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:

Java: 
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.
 
J

JohannisderKaeufer

Gast
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.
 
C

ceyf

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

ceyf

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

Yamato

Aktives Mitglied
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.
 

Aktuelle Jobs

Neue Themen


Oben