Note de curs, probleme algoritmică, 9 decembrie 2013

În acest curs am discutat despre problema 1152 - False Mirrors.

Implementare

Versiunea 1

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

Complexitate timp: O(N! * N)

Complexitate spațiu: O(N)

#include <stdio.h>

const int MAX_N = 20;
const int MAX_INT = 0x7fffffff;

int N;
int V[MAX_N];

bool distrus[MAX_N];
int raspuns;

int backtracking() {
	int i, j;
	int raspuns = 0x7fffffff;
	bool distrusComplet;
	distrusComplet = true;
	for (i = 0; i < N; ++i) {
		if (!distrus[i]) {
			distrusComplet = false;
		}
	}
	if (distrusComplet) {
		raspuns = 0;
	} else {
		int lovit;
		int raspunsPotential;
		for (i = 0; i < N; ++i) {
			if (!distrus[i]) {
				bool anteriorI  = distrus[(i    ) % N];
				bool anteriorI1 = distrus[(i + 1) % N];
				bool anteriorI2 = distrus[(i + 2) % N];
				distrus[(i    ) % N] = true;
				distrus[(i + 1) % N] = true;
				distrus[(i + 2) % N] = true;
				lovit = 0;
				for (j = 0; j < N; ++j) {
					if (!distrus[j]) {
						lovit += V[j];
					}
				}
				raspunsPotential = lovit + backtracking();
				if (raspuns > raspunsPotential) {
					raspuns = raspunsPotential;
				}
				distrus[(i    ) % N] = anteriorI;
				distrus[(i + 1) % N] = anteriorI1;
				distrus[(i + 2) % N] = anteriorI2;
			}
		}
	}
	return raspuns;
}

int main(void) {
	int i;

	// citirea datelor
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		scanf("%d", &V[i]);
	}

	// calcularea solutiei
	for (i = 0; i < N; ++i) {
		distrus[i] = false;
	}
	raspuns = backtracking();

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

Versiunea 2

Să se rescrie rezolvarea anterioară astfel încât variabila globală bool distrus[MAX_N] să fie înlocuită cu un parametru întreg, folosit pe biți (int distrus).

Complexitate timp: O(N! * N)

Complexitate spațiu: O(N)

#include <stdio.h>

const int MAX_N = 20;
const int MAX_INT = 0x7fffffff;

int N;
int V[MAX_N];

int raspuns;

int backtracking(int distrus) {
	int i, j;
	int raspuns = 0x7fffffff;
	bool distrusComplet;
	if (distrus == (1 << N) - 1) {
		distrusComplet = true;
	} else {
		distrusComplet = false;
	}
	if (distrusComplet) {
		raspuns = 0;
	} else {
		int lovit;
		int raspunsPotential;
		for (i = 0; i < N; ++i) {
			if ((distrus & (1 << i)) == 0) {
				int anterior = distrus;
				distrus |= 1 << ((i    ) % N);
				distrus |= 1 << ((i + 1) % N);
				distrus |= 1 << ((i + 2) % N);
				lovit = 0;
				for (j = 0; j < N; ++j) {
					if ((distrus & (1 << j)) == 0) {
						lovit += V[j];
					}
				}
				raspunsPotential = lovit + backtracking(distrus);
				if (raspuns > raspunsPotential) {
					raspuns = raspunsPotential;
				}
				distrus = anterior;
			}
		}
	}
	return raspuns;
}

int main(void) {
	int i;

	// citirea datelor
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		scanf("%d", &V[i]);
	}

	// calcularea solutiei
	raspuns = backtracking(0);

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

Versiunea 3

Să se rescrie rezolvarea anterioară astfel încât 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 MAX_N = 20;
const int MAX_INT = 0x7fffffff;

int N;
int V[MAX_N];

int raspuns;

int Backtracking[1 << MAX_N];

int backtracking(int distrus) {
	if (Backtracking[distrus] == MAX_INT) {
		int i, j;
		int raspuns = 0x7fffffff;
		bool distrusComplet;
		if (distrus == (1 << N) - 1) {
			distrusComplet = true;
		} else {
			distrusComplet = false;
		}
		if (distrusComplet) {
			raspuns = 0;
		} else {
			int lovit;
			int raspunsPotential;
			for (i = 0; i < N; ++i) {
				if ((distrus & (1 << i)) == 0) {
					int anterior = distrus;
					distrus |= 1 << ((i    ) % N);
					distrus |= 1 << ((i + 1) % N);
					distrus |= 1 << ((i + 2) % N);
					lovit = 0;
					for (j = 0; j < N; ++j) {
						if ((distrus & (1 << j)) == 0) {
							lovit += V[j];
						}
					}
					raspunsPotential = lovit + backtracking(distrus);
					if (raspuns > raspunsPotential) {
						raspuns = raspunsPotential;
					}
					distrus = anterior;
				}
			}
		}
		Backtracking[distrus] = raspuns;
	}
	return Backtracking[distrus];
}

int main(void) {
	int i;

	// citirea datelor
	scanf("%d", &N);
	for (i = 0; i < N; ++i) {
		scanf("%d", &V[i]);
	}

	// calcularea solutiei
	raspuns = backtracking(0);

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