Note de curs, probleme algoritmică, 18 octombrie 2013

În acest curs am discutat despre calcularea ciclului hamiltonian de cost minim într-un graf prin backtracking, optimizat ulterior prin memoizare.

Un evaluator on-line pentru această problemă poate fi găsit la adresa http://www.infoarena.ro/problema/hamilton.

Versiunea 1

Să se rezolve problema prin backtracking recursiv, cu variabile globale.

Complexitate timp: O((N - 1)! * N)

Complexitate spațiu: O(N * N)

#include <stdio.h>

const int NMAX = 20;

int N, M;

int costMuchie[NMAX][NMAX];

bool exista[NMAX];
int permutare[NMAX];

int SOL;

void ciclu(int pozitie, int costPartial) {
	if (pozitie == N + 1) { // s-a generat o permutare
		if (costMuchie[permutare[N]][1] != 0) { // exista muchia care inchide ciclul
			costPartial += costMuchie[permutare[N]][1]; // costul muchiei se adauga
			if (SOL > costPartial) {
				SOL = costPartial;
			}
		}
	} else {
		int i;
		for (i = 2; i <= N; ++i) {
			if (costMuchie[permutare[pozitie - 1]][i] != 0) {// exista muchie
				if (!exista[i]) {
					exista[i] = true;
					permutare[pozitie] = i;
					ciclu(pozitie + 1, costPartial + costMuchie[permutare[pozitie - 1]][i]);
					exista[i] = false;
				}
			}
		}
	}
}

int main(void) {
	int i;
	int a, b, c;

	// citirea datelor
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		++a;
		++b;
		costMuchie[a][b] = c;
	}

	// calcularea solutiei
	SOL = 0x7fffffff; // "+infinit" pe int
	permutare[1] = 1;
	exista[1] = true;
	ciclu(2, 0);

	// afisarea solutiei
	printf("%d\n", SOL);
	return 0;
}

Versiunea 2

Să se rescrie rezolvarea anterioară astfel încât:

• variabila globală bool exista[NMAX] să fie înlocuită cu un parametru întreg, folosit pe biți (int exista);
• variabila globală int permutare[NMAX] să fie înlocuită cu un parametru întreg, reprezentând doar ultimul nod vizitat (int nodAnterior);
• variabila globală int SOL să fie eliminată prin returnarea soluției de către funcția recursivă (int ciclu).

Complexitate timp: O((N - 1)! * N)

Complexitate spațiu: O(N * N)

#include <stdio.h>

const int NMAX = 20;

int N, M;

int costMuchie[NMAX][NMAX];

int ciclu(int pozitie, int costPartial, int nodAnterior, int exista) {
	if (pozitie == N + 1) { // s-a generat o permutare
		if (costMuchie[nodAnterior][1] != 0) { // exista muchia care inchide ciclul
			costPartial += costMuchie[nodAnterior][1]; // costul muchiei se adauga
			return costPartial;
		}
		return 0x7fffffff; // "+infinit" ~= ciclu invalid
	} else {
		int SOL = 0x7fffffff;
		int solutiePotentiala;
		int i;
		for (i = 2; i <= N; ++i) {
			if (costMuchie[nodAnterior][i] != 0) {// exista muchie
				if ((exista & (1 << i)) == 0) {
					solutiePotentiala = ciclu(pozitie + 1, costPartial + costMuchie[nodAnterior][i], i, exista ^ (1 << i));
					if (SOL > solutiePotentiala) {
						SOL = solutiePotentiala;
					}
				}
			}
		}
		return SOL;
	}
}

int main(void) {
	int i;
	int a, b, c;

	// citirea datelor
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		++a;
		++b;
		costMuchie[a][b] = c;
	}

	// calcularea solutiei
	int SOL = ciclu(2, 0, 1, 1 << 1);

	// afisarea solutiei
	printf("%d\n", SOL);
	return 0;
}

Versiunea 3

Să se rescrie rezolvarea anterioară astfel încât:

• să se elimine parametrii int pozitie și int costPartial, fiind redundanți;
• să se optimizeze execuția algoritmului, prin memoizarea funcției recursive.

Complexitate timp: O(N * 2^N * N)

Complexitate spațiu: O(N * 2^N)

#include <stdio.h>

const int NMAX = 20;
const int NMAXPOW2 = 1 << NMAX;

int N, M;

int costMuchie[NMAX][NMAX];

int Ciclu[NMAX][NMAXPOW2];

int ciclu(int nodAnterior, int exista) {
	if (Ciclu[nodAnterior][exista] == 0) {
		int SOL;
		if (exista == ((1 << N) - 1) << 1) { // s-a generat o permutare
			if (costMuchie[nodAnterior][1] != 0) { // exista muchia care inchide ciclul
				SOL = costMuchie[nodAnterior][1]; // costul muchiei se adauga
			} else {
				SOL = 0x3fffffff; // "+infinit"/2 ~= ciclu invalid
			}
		} else {
			SOL = 0x3fffffff;
			int solutiePotentiala;
			int i;
			for (i = 2; i <= N; ++i) {
				if (costMuchie[nodAnterior][i] != 0) {// exista muchie
					if ((exista & (1 << i)) == 0) {
						solutiePotentiala = costMuchie[nodAnterior][i] + ciclu(i, exista ^ (1 << i));
						if (SOL > solutiePotentiala) {
							SOL = solutiePotentiala;
						}
					}
				}
			}
		}
		Ciclu[nodAnterior][exista] = SOL;
	}
	return Ciclu[nodAnterior][exista];
}

int main(void) {
	int i;
	int a, b, c;

	// citirea datelor
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		++a;
		++b;
		costMuchie[a][b] = c;
	}

	// calcularea solutiei
	int SOL = ciclu(1, 1 << 1);

	// afisarea solutiei
	printf("%d\n", SOL);
	return 0;
}