Colonii de furnici v2

//Optimizarea cu colonii de furnici
#pragma warning (disable:4996)
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

// Am declarat aici variabilele constante care sunt prestabilite inaintea programului
#define alfa 1
#define beta 1
#define grad_eva 0.01
#define nr_furnici 100

double functie_euristica(int oras1, int oras2, int m[20][20]) {
	// functia returneaza nij unde nij = 1 / (d(i, j)/10).
	return double(1 / (double(m[oras1][oras2]/10)));
}

int algoritm_ruleta(double q[20]) {
	//Se genereaza un numar random intre 0 si 1 si se alegere orasul
	double r = double(rand() % 100);
	r = r / 100;

	int i = 0;
	while (q[i] < r)
		i++;
	i++;
	return i;
}

void initializare_tau(double tau[20][20]) {
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			tau[i][j] = 1;
}

void initializare_a(double a[20][20]) {
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			a[i][j] = 0;
}

void colonii_de_furnici(int plecare, int sosire, int m[20][20], char *oras[]) {
	//Majoritatea variabilelor au nume sugestive
	//nr_noduri[nr_furnici] memoreaza numarul de orase parcurse de cele nr_furnici la fiecare iteratie
	int nod, lista_tabu[nr_furnici][20], nr_noduri[nr_furnici], nr_q, iteratia = 0, noduri[20], nr_nod, Vizitate[20], Parinte[20], vector_solutie[20], nr_vector_solutie = 21;
	double a[20][20], q[20], tau[20][20];

	// Initial nivelul de feromon, tau[i][j], este 1 pentru orice drum
	initializare_tau(tau);

	//Se poate modifica 10-le daca dorim sa ruleze pentru mai multe iteratii
	while (iteratia != 10) {
		//La inceput nu exista niciun oras parcurs
		for (int i = 0; i < nr_furnici; i++)
			nr_noduri[i] = 0;

		//Pentru fiecare furnica
		for (int i = 0; i < nr_furnici; i++) {
			// La inceput nu avem niciun nod in noduri[20] deci nr_nod=0 si niciun oras nu e vizitat
			nr_nod = 0;
			for (int i = 0; i < 20; i++)
				Vizitate[i] = 0;
			Vizitate[plecare] = 1;
			nod = plecare;

			//Cat timp stare_curenta!=stare_tinta (nod!=sosire)
			while (nod != sosire) {
				//Se initializeaza a-ul cu 0
				initializare_a(a);

				// nr - numarul de vecini ai orasului nod
				// suma_a este numitorul lui a
				int nr = 0;
				double suma_a = 0;

				//Se calculeaza numitorul lui a[nod][j] dupa formula si se salveaza in suma_a si in acelas timp se adauga in fiecare a[nod][j] numaratorul
				for (int j = 0; j < 20; j++)
					if ((m[nod][j] != 0) && (Vizitate[j] == 0)) {
						nr++;
						suma_a = suma_a + pow(tau[nod][j], alfa)*pow(functie_euristica(nod, j, m), beta);
						a[nod][j] = pow(tau[nod][j], alfa)*pow(functie_euristica(nod, j, m), beta);
					}
				//Daca orasul are vecini, se imparte numaratorul (a[nod][j]) la numitorul calculat anterior (suma_a)
				//Se adauga in noduri toti vecini,se marcheaza ca vizitati si se salveaza parinti fiecarui vecin
				for (int j = 0; j < 20; j++)
					if (a[nod][j] != 0) {
						a[nod][j] = a[nod][j] / suma_a;
						Vizitate[j] = 1;
						noduri[nr_nod++] = j;
						Parinte[j] = nod;
					}

				// Se afla q-ul pentru fiecare a
				nr_q = 0;
				while (nr_q != nr) {
					int gasit = 0;

					q[nr_q] = 0;
					for (int j = 0; j < 20; j++)
						if ((a[nod][j] != 0) && (nr_q + 1 != gasit)) {
							gasit++;
							q[nr_q] = q[nr_q] + a[nod][j];
						}
					nr_q++;
				}

				//selectat va reprezenta orasul selectat dupa ce s-a generat un numar random iar alegere_oras va memora acel oras selectat
				int selectat = algoritm_ruleta(q), alegere_oras = 0;

				for (int j = 0; j < 20; j++) {
					if (a[nod][j] != 0)
						alegere_oras++;
					if (alegere_oras == selectat) {
						alegere_oras = j;
						break;
					}
				}
			    //Daca nr=0 inseamna ca nod nu are vecini deci s-a blocat si luam un nou nod, primul din noduri[0]
				//Stergem noduri[0] dupa ce il salvam in alegere_oras
				if (nr == 0) {
					alegere_oras = noduri[0];
					for (int k = 1; k < nr_nod; k++)
						noduri[k - 1] = noduri[k];
				}
				else {
					//Daca nr nu e 0 atunci stergem nodul alegere_oras din noduri[20]
					int poz;
					for (int k = 0; k < nr_nod; k++)
						if (alegere_oras == noduri[k]) {
							poz = k;
							break;
						}
					for (int k = poz; k < nr_nod - 1; k++)
						noduri[k] = noduri[k + 1];
				}
				nr_nod--;
				//Adaugam in nod orasul ales
				nod = alegere_oras;
			}
			// Dupa ce am gasit o solutie o punem in lista_tabu in mod invers
			int solutie[20], n = 0;
			int sol = sosire;

			while (sol != plecare) {
				solutie[n++] = sol;
				sol = Parinte[sol];
			}
			solutie[n++] = plecare;
			for (int k = n - 1; k >= 0; k--)
				lista_tabu[i][nr_noduri[i]++] = solutie[k];

			//Daca cumva solutia costul drumului unei furnici(n) este mai mic decat costul drumului vector_solutie (nr_vector_solutie) atunci salvam drumul mai bun
			if (n < nr_vector_solutie) {
				nr_vector_solutie = 0;
				for (int k = n - 1; k >= 0; k--)
					vector_solutie[nr_vector_solutie++] = solutie[k];
			}
			//Depunerea feromonului pe arce
			double cost_tabu;

			for (int i = 0; i < nr_furnici; i++) {
				cost_tabu = 0;
				for (int j = 0; j < nr_noduri[i] - 1; j++)
					cost_tabu = cost_tabu + (m[lista_tabu[i][j]][lista_tabu[i][j + 1]] / 10);
				for (int j = 0; j < nr_noduri[i] - 1; j++)
					tau[lista_tabu[i][j]][lista_tabu[i][j + 1]] += 1 / cost_tabu;
			}

		}
		//Evaporarea feromonului
		for (int i = 0; i < 20; i++)
			for (int j = 0; j < 20; j++)
					tau[i][j] = (1 - grad_eva)*tau[i][j];
		iteratia++;
	}
	// Afisarea cel mai bun drum parcurs dintre cele x furnici in cele x iteratii
	printf("\nDrumul parcurs de ultima furnica este: ");
	for (int i = 0; i < nr_vector_solutie; i++)
		printf("%s ", oras[vector_solutie[i]]);
}

void main() {

	char *oras[] = { "Alba Iulia","Arad","Baia Mare","Bistrita","Braila","Brasov","Bucuresti","Cluj Napoca",
		"Constanta","Craiova","Iasi","Oradea","Piatra Neamt","Pitesti","Satu Mare","Sibiu","Suceava","Targu Mures",
		"Timisoara","Tulcea" };
	int m[20][20], plecare, sosire;

	time_t t;
	srand((unsigned)(time(&t)));
	// In matrice am pus -0 daca nu exista drum intre cele 2 orase si nr de km - daca exista drum

	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			m[i][j] = 0;
	m[10][12] = m[12][10] = 129;
	m[5][15] = m[15][5] = 141;
	m[5][12] = m[12][5] = 238;
	m[0][18] = m[18][0] = 217;
	m[11][7] = m[7][11] = 159;
	m[14][2] = m[2][14] = 62;
	m[2][7] = m[7][2] = 148;
	m[14][11] = m[11][14] = 139;
	m[11][1] = m[1][11] = 114;
	m[7][1] = m[1][7] = 268;
	m[1][18] = m[18][1] = 58;
	m[18][9] = m[9][18] = 341;
	m[9][13] = m[13][9] = 121;
	m[9][0] = m[0][9] = 295;
	m[0][7] = m[7][0] = 98;
	m[7][3] = m[3][7] = 108;
	m[7][17] = m[17][7] = 111;
	m[0][15] = m[15][0] = 74;
	m[15][17] = m[17][15] = 114;
	m[17][3] = m[3][17] = 93;
	m[3][16] = m[16][3] = 195;
	m[16][10] = m[10][16] = 147;
	m[5][13] = m[13][5] = 137;
	m[13][6] = m[6][13] = 118;
	m[6][8] = m[8][6] = 227;
	m[6][12] = m[12][6] = 352;
	m[6][4] = m[4][6] = 218;
	m[4][12] = m[12][4] = 255;
	m[4][19] = m[19][4] = 95;
	m[19][8] = m[8][19] = 138;
	m[17][5] = m[5][17] = 169;
	m[5][6] = m[6][5] = 170;
	printf("Alegeti orasul de plecare si de sosire.\n");
	for (int i = 0; i < 20; i++)
		printf("%d.%s\n", i, oras[i]);
	printf("Introduce numarul orasului de plecare:");
	scanf("%d", &plecare);
	printf("Introduce numarul orasului de sosire:");
	scanf("%d", &sosire);

	colonii_de_furnici(plecare, sosire, m, oras);
	_getch();
}