PDA

Visualizza la versione completa : [C] Programmazione per risolvere un problema di ricerca operativa


lucgian84
11-07-2010, 19:09
Ciao a tutti, sono nuovo di questo forum, mi sono iscritto perchè ho alcuni problemi con un mio compagno di corso per quanto riguarda la risoluzione di un problema di ricerca operativa.
La consegna del nostro progetto è:

Valves location:
in una rete acquedottistica, rappresentata attraverso un grafo non orientato
G = (V,E), si vogliono localizzare k valvole su altrettanti archi in E in modo tale da massimizzare il numero di componenti connessi (settori) che si ottengono in seguito alla chiusura simultanea di tutte le valvole.

Dopo aver parlato con la professoressa abbiamo deciso insieme a lei di sviluppare il progetto utilizzando il linguaggio di programmazione C.
L'idea di base è la seguente:

1. Si parte da un file in cui si rappresenta una situazione di partenza al cui interno vengono memorizzati per ogni riga il nodo sorgente, il nodo destinatario, il peso (le utenze connesse a quel nodo) e la presenza o meno di una valvola
2. Il programma deve caricare il contenuto del file all'interno di un array di struttura di dimensione pari al numero delle connessioni tra i vari nodi
3. In seguito, il programma deve andare a calcolare il valore del peso (delle utenze) nel caso in cui la connessione presenti una valvola (il peso si suddivide equamente tra il nodo di partenza ed il nodo di destinazione)
4. Si devono definire i settori, cioè si deve andare a calcolare la somma di tutti i pesi associati ad ogni connessione presente all'interno di un taglio della rete
5. Si calcola la media del peso di tutti i settori
6. Si applica l'algoritmo della ricerca locale per ottimizzare la soluzione
7. Il risultato viene salvato su un file di testo uguale a quello utilizzato in precedenza in modo da poter effettuare un'ulteriore ottimizzazione nel caso sia possibile ottenere una soluzione migliore

Volevo chiedervi a voi se avevate una qualche idea su come sviluppare il codice che riguarda i punti 4, 5 e 6.
Spero di essermi espresso bene e se trovate una soluzione vi ringrazio per la vostra disponibilità

Luca

alka
13-07-2010, 13:28
Inizia a stendere del codice e a formulare delle proposte valutabili: gli utenti disponibili a darti una mano leggeranno la soluzione che proponi e ti daranno i propri suggerimenti.

Loading