tabu search in linguaggio c

gessic

Nuovo Utente
6
0
salve a tutti,
devo realizzare un algoritmo ibrido tabu search simulated annealing in C per il massimo di una funzione, qualcuno può darmi qualche informazione utile , soprattutto sulla tabu search. per favore è urgente. grazie mille
 
Ultima modifica:
U

Utente cancellato 68151

Ospite
Allora, dando un' occhiata qui e la sono giunto a questa conclusione: E' UN CASINO!!!
Comunque, da quel poco che ho capito, si tratta di una procedura non-geedy che permette anche un peggioramento della soluzione.
Infatti, supponi che una funzione abbia un minimo locale: se l' algoritmo non permettesse un peggioramento, il risultato sarebbe quel minimo locale e non quello assoluto.
Da quel poco che ho capito, è intanto necessario crearsi una lista di tutte le possibili soluzioni, nel tuo caso farei così:
- definiamo una funzione f(x) (ovviamente per il compilatore sarà y = funzione)
- definiamo un intervallo per quella funzione [a,b]
- definiamo la precisione dello spostamento, ovvero la variazione minima di x
- ci creiamo una lista (magari facciamo un array per semplicità) con tutte le funzioni

ESEMPIO:
Codice:
/*supponiamo di voler definire la funzione F(x) = x^2 (parabola)*/
/*nell' intervallo [0, 10] con offset 0,01*/


int i = 0;			/*contatore*/
float a = 0; 			/*inizio intervallo*/
float b = 10;			/*fine intervallo*/
float offset = 0.01;		/*offset*/
int dim = (b-a)/offset;		/*numero massimo soluzioni*/


/*VARIANTE ARRAY*/


float solutionsArray[dim];	/*array con TUTTE le possibili soluzioni*/


/*riempio l' array*/
for(i = 0; i < dim; i++) {
	solutionsArray[i] = i^2; /*quest' assegnazione varierà a seconda della funzione*/
}


-------------------------------------------------------------------------------------------


/*VARIANTE LISTA*/


struct Data {
	float data;
	struct data *succ = NULL;
};
typedef struct Data solution;


solution *head = NULL;
solution *temp = NULL;
solution *new = NULL;


/*riempio l' array*/
for(i = 0; i < dim; i++) {
	new = malloc(Sizeof(solutions));
	new.data = i^2; /*quest' assegnazione varierà a seconda della funzione*/
	if(head == NULL) head = new;
	else {
		temp = head;
		while(temp->succ != NULL) temp = temp->succ;
		temp->succ = new
	}	
}

Ora, se fosse un normale algoritmo, farei semplicemente la ricerca del massimo dell' array o della lista (ok la parabola per x>0 è crescente, quindi ovviamente il massimo sarà per x = 10).
Purtroppo non ho compreso i metodi per cui l' insieme rimpicciolito o ingrandito (ma in questo caso ti occorre forzatamente una lista, visto che l' array non è dinamico) spero però che questo poco ti sia d' aiuto
 

flavioso

Nuovo Utente
2
0
Salve dovrei 'scrivere in C un algoritmo ibrido Algoritmo Genetico + Tabu Search per la determinazione del numero minimo di colori necessario per la colorazione di un dato grafo G (V, E). Testare l'algoritmo su 5 stanze distinte

Potreste darmi una mano?

Grazie
 

Entra

oppure Accedi utilizzando

Hot: E3 2021, chi ti è piaciuto di più?

  • Ubisoft

    Voti: 17 18.3%
  • Gearbox

    Voti: 1 1.1%
  • Xbox & Bethesda

    Voti: 66 71.0%
  • Square Enix

    Voti: 3 3.2%
  • Capcom

    Voti: 5 5.4%
  • Nintendo

    Voti: 14 15.1%
  • Altro (Specificare)

    Voti: 8 8.6%

Discussioni Simili