Problem komiwojażera - optymalizacje DFS

0

Staram się rozwiązać problem komiwojażera. Mam DFSa, który szuka najkrótszej ścieżki. Poniżej zamieszczam kod. Czy macie pomysł na wcześniejsze ucięcie części wywołań?

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#define debug(fmt,...) fprintf(stderr,fmt,##__VA_ARGS__)
using namespace std;

//--------------------------------------------------------------------------------------------------------------------------

struct vertex
{
	short unsigned int neighbour, weight;
	vertex (short unsigned int a, short unsigned int b)
	{
		neighbour=a;
		weight=b;
	}
};
bool operator< (vertex a, vertex b)
{
	return a.weight<b.weight;
}
short unsigned int n, m, level=0;
unsigned int min_way=(1<<25), act_way=0, add_weight, infty=(((unsigned int)1<<31)-1);
map<string, short unsigned int>M;
vector<vertex>G[100];
bool visited[100], t[100];

//--------------------------------------------------------------------------------------------------------------------------
void DFS_CONNECT(short unsigned int v)
{
	t[v]=true;
	for (unsigned int i=0; i<G[v].size(); i++)
		if (!t[G[v][i].neighbour])
			DFS_CONNECT(G[v][i].neighbour);
}
bool CZYSIEDA (short unsigned int v)
{
	memcpy(t, visited, n*sizeof(bool));
	DFS_CONNECT(v);
	for(int i=0; i<n; i++)
		if(t[i]==false)
			return false;
	return true;
}
void READ()
{
	scanf("%hu %hu ", &n, &m);
	char tmp1[50], tmp2[50];
	short int tmpint;
	for (short unsigned int i=0; i<n; i++)
	{
		scanf(" %s ", tmp1);
		M.insert(make_pair(string(tmp1), i));
		visited[i]=false;
	}
	short int _1, _2;
	for (short unsigned int i=0; i<m; i++)
	{
		scanf(" %s %s %hu", tmp1, tmp2, &tmpint);
		_1=M.find(string(tmp1))->second;
		_2=M.find(string(tmp2))->second;
		G[_1].push_back(vertex(_2, tmpint));
		G[_2].push_back(vertex(_1, tmpint));
	}
	for(short unsigned int i=0; i<n; i++)
		sort(G[i].begin(), G[i].end());
}
void DFS(short unsigned int v)
{
	if (act_way>=min_way || act_way*n>min_way*level+add_weight || !CZYSIEDA(v))
		return;
	visited[v]=true;
	if (level==n-1)
	{
		for (unsigned int i=0; i<G[v].size(); i++)
			if (G[v][i].neighbour==0)
			{
				min_way=min(min_way, act_way+G[v][i].weight);
				debug("nowe minimum: %d z wierzchołka %d\n", min_way, v);
				break;
			}
	}
	else
	{
		level++;
		for (unsigned int i=0; i<G[v].size(); i++)
			if(!visited[G[v][i].neighbour])
			{
				act_way+=G[v][i].weight;
				DFS(G[v][i].neighbour);
				act_way-=G[v][i].weight;
			}
		level--;
	}
	visited[v]=false;
}
void ADD_WEIGHT()
{
	min_way=(1<<20);
	add_weight=50*n+4000;
	debug("2*MST = %d, add_weight = %d\n", min_way, add_weight);
}
int main ()
{
	READ();
	ADD_WEIGHT();
	debug("rozpoczęto wyszukiwanie ścieżki\n");
	DFS(0);
	printf("%d\n", min_way);
}

Dziękuję za wszelkie wskazówki.

0

A jak to działa do tej pory? Z tego spghetti ciężko coś wywnioskować.

Np. co to jest act_way*n>min_way*level+add_weight, albo co to CZYSIEDA?

Poza tym problem komiwojażera jest bardzo popularny, w internecie materiałów jest od groma.

0

Do tej pory:

  1. Sortuje sąsiadów po wadze krawędzi (mniejsze sprawdza najpierw)
  2. CZYSIEDA sprawdza, czy w ogóle da się odwiedzić wszystkie pozostałe wierzchołki.
  3. Jeżeli droga do tej pory jest większa niż minimalna znaleziona, nie ma sensu dalej szukać.
  4. add_weight to element funkcji wagowej, która, jeżeli przeszliśmy małą część trasy a już mamy bardzo dużą odległość do pokonania, przerywa sprawdzanie danej ścieżki.
0
merlinnot napisał(a):
  1. CZYSIEDA sprawdza, czy w ogóle da się odwiedzić wszystkie pozostałe wierzchołki.
    Czy to w ogóle przyspiesza algorytm? Nie bardzo mogę rozszyfrować co tam się dzieje, ale nie wygląda to zbyt dobrze.
merlinnot napisał(a):
  1. add_weight to element funkcji wagowej, która, jeżeli przeszliśmy małą część trasy a już mamy bardzo dużą odległość do pokonania, przerywa sprawdzanie danej ścieżki.
    W ten sposób nie zawsze znajdziesz najlepsze rozwiązanie. Jeśli interesuje cię rozwiązanie optymalne (nie koniecznie najlepsze) to są od tego inne, szybsze algorytmy.
0
  1. Wiem, że nie zawsze, już nie mam tego w kodzie.
  2. Tak, przyspiesza znacznie, sprawdzałem.
  3. Nowa optymalizacja: W 2) liczę także odległość, jaką przebył DFS. Jako, że krawędzie są posortowane od najmniejszych, to zawsze będzie to najkrótsza droga odwiedzająca wszystkie wierzchołki (mam rację?). Droga, która odwiedza je tylko jednokrotnie musi być dłuższa. Dlatego, jeżeli droga aktualna + wyliczona w DFSie jest większa od minimalnej, przerywam.

O tak:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#define debug(fmt,...) //fprintf(stderr,fmt,##__VA_ARGS__)
using namespace std;

//--------------------------------------------------------------------------------------------------------------------------

struct vertex
{
	short unsigned int neighbour, weight;
	vertex (short unsigned int a, short unsigned int b)
	{
		neighbour=a;
		weight=b;
	}
};
bool operator< (vertex a, vertex b)
{
	return a.weight<b.weight;
}
short unsigned int n, m, level=0, start_vertex;
unsigned int min_way=0, act_way=0, add_weight; 
unsigned int infty=(((unsigned int)1<<31)-1), random_start_vertex;
map<string, short unsigned int>M;
vector<vertex>G[100];
bool visited[100], t[100];
int DFS_L;

//--------------------------------------------------------------------------------------------------------------------------

void DFS_CONNECT(short unsigned int v);
inline bool CZYSIEDA (short unsigned int v);
void READ();
void DFS(short unsigned int v);
void ADD_WEIGHT();

//--------------------------------------------------------------------------------------------------------------------------

int main ()
{
	READ();
	ADD_WEIGHT();
	debug("rozpoczęto wyszukiwanie ścieżki\n");
	DFS(start_vertex);
	printf("%d\n", min_way);
}

//--------------------------------------------------------------------------------------------------------------------------

void DFS_CONNECT(short unsigned int v)
{
	t[v]=true;
	for (vector<vertex>::iterator it=G[v].begin(); it!=G[v].end(); it++)
		if (!t[it->neighbour])
		{
			DFS_CONNECT(it->neighbour);
			DFS_L+=it->weight;
		}
	return;
}
bool CZYSIEDA (short unsigned int v)
{
	memcpy(t, visited, n*sizeof(bool));
	DFS_L=0;
	DFS_CONNECT(v);
	for(int i=0; i<n; i++)
		if(t[i]==false)
			return false;
	return true;
}
void READ()
{
	scanf("%hu %hu ", &n, &m);
	char tmp1[50], tmp2[50];
	short int tmpint;
	for (short unsigned int i=0; i<n; i++)
	{
		scanf(" %s ", tmp1);
		M.insert(make_pair(string(tmp1), i));
		visited[i]=false;
	}
	short int _1, _2;
	for (short unsigned int i=0; i<m; i++)
	{
		scanf(" %s %s %hu", tmp1, tmp2, &tmpint);
		_1=M.find(string(tmp1))->second;
		_2=M.find(string(tmp2))->second;
		G[_1].push_back(vertex(_2, tmpint));
		G[_2].push_back(vertex(_1, tmpint));
	}
	for(int i=0; i<n; i++)
		sort(G[i].begin(), G[i].end());
}
void DFS(short unsigned int v)
{
	visited[v]=true;
	if (level==n-1)
	{
		for (vector<vertex>::iterator it=G[v].begin(); it!=G[v].end(); it++)
			if (it->neighbour==start_vertex)
			{
				min_way=min(min_way, act_way+it->weight);
				debug("nowe minimum: %d z wierzchołka %d\n", min_way, v);
				break;
			}
	}
	else
	{
		level++;
		for (vector<vertex>::iterator it=G[v].begin(); it!=G[v].end(); it++)
			if(!visited[it->neighbour] && CZYSIEDA(it->neighbour) && DFS_L+act_way<min_way)
			{
				act_way+=it->weight;
				if(act_way<min_way)// && (level<n/2 || act_way*n<(min_way*level+add_weight)))
					DFS(it->neighbour);
				act_way-=it->weight;
			}
		level--;
	}
	visited[v]=false;
}
void ADD_WEIGHT()
{
	min_way=(((unsigned int)1<<31)-1);
	add_weight=(n<30)?(50*n+1300):15000;
	start_vertex=0;
	debug("min_way = %d, add_weight = %d, start_vertex = %d\n", min_way, add_weight, start_vertex);
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1