3. TSP in c++

TSP in c++

  • K

    Schäfchen schrieb:

    Ich verspreche hiermit auch feierlich.."Ich werde mich in Zukunft mehr mit C++ beschäftigen"

    wenns so knapp ist, hättest du das wohl früher tun müsse n;)

    Schäfchen schrieb:

    ein Beipiel code würde mir ja reichen...um es zu verstehen..

    wenn du das prinzip nict verstanden hast, dann hilft dir der algorithmus implementiert noch viel weniger, den wirst du dann wahrscheinlich garnicht verstehen.

    aber hier mal ein paar interessante links zu tsp:
    http://de.wikipedia.org/wiki/Traveling_Salesman_Problem
    http://de.wikipedia.org/wiki/Hamiltonkreisproblem
    http://www.tsp.gatech.edu/
    da wird das eigentlich recht anschaulich erklärt. wenn dus verstanden hast, sollte die implementierung nicht mehr so schwer sein, es wird ja nicht grad die schnellste verlangt werden...

    0
  • ?

    Aha du hast es also versucht aber bist mangels C++-Kenntnissen gescheitert.

    Wenn du mir jetzt nen (guten!) Grund nennst, warum es dir erst einen Tag vor Abgabe in den Sinn kommt mal in nem Forum nach etwas Lektüre zu dem Thema zu fragen, dann würde ich es in Betracht ziehen dir zu helfen.

    0
  • S

    Any schrieb:

    Aha du hast es also versucht aber bist mangels C++-Kenntnissen gescheitert.
    Wenn du mir jetzt nen (guten!) Grund nennst, warum es dir erst einen Tag vor Abgabe in den Sinn kommt mal in nem Forum nach etwas Lektüre zu dem Thema zu fragen, dann würde ich es in Betracht ziehen dir zu helfen.

    also nen guten Grund....
    wahrscheinlich hab ich keinen der dir gut genug scheint...
    hab ja nicht erst heute angefangen, etwas ist schon programmiert(tu mich nur mit den kompliziereren Dingen etwas schwer), dann hab ich die ganze zeit versuch c++ besser zu verstehen und schwups war es auch schon der 9. Februar.
    dann musste ich auch noch viel arbeiten und umziehen....
    naja alles keinen überzeugenden Gründe 😞
    Vllt hilfst du mir ja trotzdem 😕

    0
  • K

    was klappt denn nicht? (wenn garnichts klappt weil du noch nichts hast, dann wirds schwer)

    0
  • ?

    Gut ich bin ja mal nicht so, hier das TSP mit Tiefensuche und niedrigste Kosten in C. Hab ich vor ettlichen Jahren mal geschrieben, aber es funktioniert.
    Wenn du das Prinzip verstanden hast, kannst es leicht nach C++ (und viel flexibler) übertragen, dort gibts die ganzen Standard-Container die dir ja viel Arbeit ersparen.

    /* KI mit Suchmethode Tiefe-Zuerst mit Niedrigste-Kosten */
#include <stdio.h>
#include <string.h>

#define MAX 100

/* Struktur der Flugdatenbank */
struct FL {
	char from[25];
	char to[25];
	int dist;
	char skip; /* Hilfreich bei Umkehr */
};

struct FL flight[MAX]; /* Array mit DB-Strukturen */

int f_pos = 0; /* Anzahl der Einträge in der Flug-Datenbank */
int find_pos = 0; /* Index zum Durchsuchen der Flugdatenbank */
int tos = 0;	/* Spitze des Stacks */

struct stack {
	char from[25];
	char to[25];
	int dist;
};

struct stack bt_stack[MAX]; /* Umkehr-Stack */

void setup (void);
void route (char *to);
void assert_flight (char *from, char *to, int dist);
void push (char *from, char *to, int dist);
void pop (char *from, char *to, int *dist);
void isflight (char *from, char *anywhere);
int find (char *from, char *anywhere);
int match (char *from, char *to);

int main (void) {

	char from[25], to[25];

	setup ();

	printf ("From? ");
	gets (from);
	printf ("To? ");
	gets (to);

	isflight (from, to);
	route (to);

	getch ();

	return 0;

}

/* Flugdatenbank initialisieren */
void setup (void) {

	assert_flight("New York", "Chicago", 1000);
	assert_flight("Chicago", "Denver", 1000);
	assert_flight("New York", "Toronto", 800);
	assert_flight("New York", "Denver", 1900);
	assert_flight("Toronto", "Calgary", 1500);
	assert_flight("Toronto", "Los Angeles", 1800);
	assert_flight("Toronto", "Chicago", 500);
	assert_flight("Denver", "Urbana", 1000);
  	assert_flight("Denver", "Houston", 1500);
   	assert_flight("Houston", "Los Angeles", 1500);
   	assert_flight("Denver", "Los Angeles", 1000);

}

/* Wissen in die Datenbank schreiben */
void assert_flight (char *from, char *to, int dist) {

	if (f_pos < MAX) {
		strcpy (flight[f_pos].from, from);
		strcpy (flight[f_pos].to, to);
		flight[f_pos].dist = dist;
		flight[f_pos].skip = 0;
		f_pos++;
	}
	else printf ("Flight Database full.\n");

}

/* Route und Gesamtentfernung anzeigen */
void route (char *to) {

	int dist, t;

	dist = 0;
	t = 0;

	while (t < tos) {
		printf ("%s to ", bt_stack[t].from);
		dist += bt_stack[t].dist;
		t++;
	}
	printf ("%s\n", to);
	printf ("Distance is %d", dist);

}

/* Gib die Entfernung zwischen Von-Nach zurück, sofern Flug vorhanden; andernfalls 0. */
int match (char *from, char *to) {

	register int t;

	for (t = f_pos-1; t > -1; t--)
		if (!strcmp (flight[t].from, from) && !strcmp (flight[t].to, to))
			return flight[t].dist;

	return 0;

}

/* Von ist gegeben nun eine Verbindung suchen */
int find (char *from, char *anywhere) {
	int pos,dist;
	pos = 0;
	dist = 32000; /* Länger als die längste Route */
	find_pos = 0;

	while (find_pos < f_pos) {
		if (!strcmp (flight[find_pos].from, from) && !flight[find_pos].skip) {
			if (flight[find_pos].dist < dist) {
				pos = find_pos;
				dist = flight[find_pos].dist;
			}
		}
		find_pos++;
	}
	if (pos) {
		strcpy(anywhere, flight[pos].to);
		flight[pos].skip = 1;
		return flight[pos].dist;
	}
	return 0;

}

/* Feststellen ob es eine Route zwischen From und To gibt. */
void isflight (char *from, char *to) {

	int d, dist;
	char anywhere[25];

	while (dist = find (from, anywhere)) {
		/* Sind wir am Ziel ? */
		if (d = match (anywhere, to)) {
			push (from, to, dist);
			push (anywhere, to, d);
			return;
		}
	}
	/* Andere verbindung probieren */
	if (dist = find (from, anywhere)) {
		push (from, to, dist);
		isflight (anywhere, to);
	} else
	if (tos > 0) {
		/* Umkehr */
		pop (from, to, &dist);
		isflight (from, to);
	}

}

/* Stack-Routinen */
void push (char *from, char *to, int dist) {

	if (tos < MAX) {
		strcpy (bt_stack[tos].from, from);
		strcpy (bt_stack[tos].to, to);
		bt_stack[tos].dist = dist;
		tos++;
	}
	else printf ("Stack Full\n");

}

void pop (char *from, char *to, int *dist) {

	if (tos > 0) {
		tos--;
  		strcpy (from, bt_stack[tos].from);
		strcpy (to, bt_stack[tos].to);
		*dist = bt_stack[tos].dist;
	}
	else printf ("Stack Underflow\n");

}
    0
  • S

    Korbinian schrieb:

    was klappt denn nicht? (wenn garnichts klappt weil du noch nichts hast, dann wirds schwer)

    hab nur probleme mit dem finden von algorithmen..

    werde mir jetzt das hier erstmal genauer ansehen und versuchen zu verstehen 🙂

    0
  • J

    Naja, durch vollständige Suche ist ja recht einfach zu machen:

    Du mußt nur alle Stationen, die Du anfliegen willst einmal hinschreiben und dann jede mögliche Reihenfolge ausprobieren und die beste merken.

    Du brauchst also eine Funktion, die Dir zu einem Ablauf die Kosten sagt, sagen wir:

    size_t calculateLength(std::vector<unsigned int> const& path);

    Dabei sind die Stationen einfach von 1 bis n (oder auch 0 bis n-1) durchnumeriert. Du brauchst da drin eigentlich nur für je zwei aufeinander folgende Stationen in ner Tabelle nachschlagen was es kostet und das aufaddieren. (erster + letzter, falls es ein Rundweg werden soll nicht vergessen).

    Und dann müssen wir noch alle Kombinationen durchprobieren. Glücklicherweise gibt's ne fertige C++-Funktion, die das kann. einfach mit std::next_permutation.

    Also etwa so:

    std::vector<unsigned int> currentPath; // noch mit 0...n-1 initialisieren
std::vector<unsigned int> bestPath = currentPath;
size_t bestLength = calculateLength(bestPath);

while(es gibt noch ne Permutation)
{
  // generiere die nächste Permutation
  size_t length = calculateLength(currentPath);
  if(length < bestLength)
  {
    bestLength = length;
    bestPath = currentPath;
  }
};

// jetzt bestpath ausgeben

    Viel Spaß damit. 😉
    Jester

    0
  • K

    ungültige permutationen bekommst du eliminiert, indem du fehlende verbindungen mit maximalen kosten einträgst (dann wird sie sicher nicht kürzer sein als gültige...)

    ansonsten @jester: respekt, so ne billige version wär mir echt im traum nicht eingefallen 😃

    edit: ich habs in 19 zeilen 🙂

    0
  • ?

    Hui, kannst du deine 19Zeilen-Lösung Morgen veröffentlichen?

    0
  • K
     

    int tsp_costs(vector<int> path, int *costs)
{
	int cost = 0;
	for (size_t i = 0; i < path.size()-1; ++i)
		cost += costs[path[i]*path.size()+path[i+1]];
	return cost + costs[path[path.size()-1]*path.size()+path[0]];
}
vector<int> stupid_tsp(int cities, int *costs)
{
	vector<int> path, perm;
	for (int i = 0; i < cities; ++i) perm.push_back(i);
	path = perm;
	vector<int>::iterator begin = perm.begin(), end = perm.end();
	int nc, cc = tsp_costs(path, costs);
	while (next_permutation(begin, end))
		if ((nc = tsp_costs(perm, costs)) < cc)
			{ cc = nc; path = perm;	}
	return path;
}

    wobei costs ein flattened array der größe städte x städte ist und die kosten von einem zum nächsten angibt. das ganze mit testcase gibts hier: http://wwwcip.informatik.uni-erlangen.de/~sikoried/tsp.cpp

    0
Anmelden zum Antworten