Soluzione fattibile nella fase di costruzione di GRASP

0

Sto imparando la meta-euristica del GRASP (Greedy Randomized Adaptive Search).

Da quanto ho capito, GRASP si basa su due fasi principali. Il primo:

Construct a initial solution based on a greedy and random strategy

e il secondo:

Construct a local search on the previous found solution

La domanda che ho è per la prima fase. Devo creare una soluzione fattibile ?

Sono autorizzato forse a creare una soluzione non fattibile nella prima fase dell'algoritmo, e quindi utilizzare la ricerca locale per trovare una soluzione fattibile ?

EDIT:

Fondamentalmente ho il problema Peso parziale parziale SAT. L'idea è che devo massimizzare la somma di tutte le clausole soft soddisfatte, mentre allo stesso tempo soddisfare tutte le clausole hard.

Quello che stavo pensando è creare una soluzione iniziale (forse irrealizzabile) che cerchi di massimizzare il numero di clausole soft soddisfatte. Successivamente, desidero utilizzare una ricerca locale per ottimizzare ulteriormente la soluzione o renderla fattibile se necessario.

Voglio sapere se questa è una strategia valida, perché la costruzione iniziale potrebbe creare una soluzione non fattibile.

    
posta lhahn 28.06.2015 - 16:51
fonte

0 risposte

Leggi altre domande sui tag