janjan
03-06-2004, 15:08
Ho grosse difficoltà ad implementare l'algoritmo dei trasporti, ossia l'algoritmo ungherese in c o c++. Qualcuno riesce a darmi una mano?
Grazie mille in anticipo!
Ciao Jan
Grazie mille in anticipo!
Ciao Jan
View Full Version : problema dei trasporti. "ungherese"
NA01
03-06-2004, 20:27
se ti può essere utile...
http://mrfreedom.web.ctonet.it/TesinaRO/ung.html
una spiegazione completa non ce la faccio a riscriverla, ora non ne ho il tempo (e dubito che riuscirei a essere chiaro :D )
ciao
http://mrfreedom.web.ctonet.it/TesinaRO/ung.html
una spiegazione completa non ce la faccio a riscriverla, ora non ne ho il tempo (e dubito che riuscirei a essere chiaro :D )
ciao
janjan
07-06-2004, 10:44
Grazie mille, xò il mio era un problema un po' + pratico... nel senso che ho capito "abbastanza" l'algoritmo come funziona ma non riesco ad implementarlo in c !! Pensavo fosse molto più facile... AIUTOOO!!!
bizzu
07-06-2004, 22:54
Se vuoi io l'ho fatto per l'università, esame di ricerca operativa. Funziona benissimo, calcola la matrice a caso, provato anche su matrici 7000x7000 (!), poi il pc cominciava a swappare :p
Ti do i dati per un bonifico... :sofico: :D
Scherzo, se vuoi te lo passo. Se vuoi un consiglio xò non scopiazzarlo, io ho imparato un casino nel programmarlo.
Ti do i dati per un bonifico... :sofico: :D
Scherzo, se vuoi te lo passo. Se vuoi un consiglio xò non scopiazzarlo, io ho imparato un casino nel programmarlo.
khamel
08-06-2004, 10:12
mmmm.... anche io sono in crisi per questa cosa!!!
non è che fai la mia stessa facoltà? SdI a cesena....
c'è un po di codice anche per me?? lo so che è squallido ma tra 2 giorni ci sarebbe l'esame e non so se ci riesco...
grazie :p
non è che fai la mia stessa facoltà? SdI a cesena....
c'è un po di codice anche per me?? lo so che è squallido ma tra 2 giorni ci sarebbe l'esame e non so se ci riesco...
grazie :p
bizzu
08-06-2004, 10:56
Ok vi passo il codice...
x khamel: studiatelo bene il codice, quando glielo fai vedere Mingozzi ti chiede un casino di roba e se non la sai ti infama!
Cmq l'algoritmo è "tradotto" in C da quello delle sue dispense.
MINGOZZI CI SEEEI?? (zelig docet) :D :asd: :asd: :rotfl:
Vi copio/incollo anche la relazione per capire come funziona...
Il programma riceve in input il numero di origini e di destinazioni, alloca dinamicamente i relativi vettori e li
riempie con numeri casuali il cui massimo e minimo sono definiti dall’utente. A questo punto viene calcolata
la somma delle quantità nei due vettori, se differiscono viene aggiunta un’origine o una destinazione fittizia
per pareggiarle. Poi viene riempita la matrice dei costi, anch’essa con valori casuali di estremi definiti
dall’utente.
Il vettore u viene riempito con i valori minimi di ogni riga, i quali vengono poi sottratti alla matrice dei costi;
lo stesso procedimento viene fatto con v, il vettore dei minimi di ogni colonna di c-u.
Inizia quindi il procedimento del trasporto vero e proprio; le quantità vengono trasportate dalle origini alle
destinazioni nei casi in cui è possibile, cioè quando nella corrispondente posizione della matrice dei costi sia
presente uno 0. Le quantità trasportate nelle relative posizioni sono memorizzate nella matrice dei flussi.
Poi vengono esaminate una per una le origini esposte, cioè quelle in cui sia rimasta una quantità non nulla.
Su di esse viene chiamata la funzione CamminoAumentante, che riceve in input l’origine esposta e restituisce
–2 se non riesce a trovare un cammino aumentante, oppure l’indice della destinazione se invece ne trova uno.
La procedura aggiorna anche gli array Po e Pd, che sono i vettori dei predecessori, in questo modo: nelle
posizioni con predecessore è inserito il suo indice, in quelle senza –2, in quella da cui parte scrive –1. Essa si
basa su una coda (implementata con una single-linked list) nella quale vengono via via inseriti gli archi che
potrebbero far parte di un possibile cammino aumentante; si provvede poi ad estrarre l’elemento in testa alla
lista, i cui dati serviranno ad aggiornare i predecessori e a decidere quali altri archi considerare.
A seconda del valore che CamminoAumentante ritorna, vengono svolte due operazioni diverse. Se viene
trovato un cammino aumentante, viene chiamata la procedura Ricostruisci, che riceve in input gli indici
dell’origine e della destinazione. Essa determina la quantità da trasportare e aggiorna di conseguenza la
matrice dei flussi, l’origine e la destinazione interessate. Questa funzione parte dal vertice destinazione, e
basandosi sui vettori dei predecessori precedentemente modificati, si serve di una pila (implementata con una
single-linked list) nella quale inserisce tutti gli archi che fanno parte del cammino, fino ad arrivare all’origine
da cui esso parte.
Se invece CamminoAumentante ritorna –2, significa che non è stato possibile trovare alcun cammino. Perciò
è necessario modificare la matrice dei costi, sommando o sottraendo la quantità delta ai vari elementi, a
seconda della posizione che occupano rispetto agli elementi modificati nei vettori dei predecessori. Vengono
modificati anche u e v, cioè le variabili duali.
Terminata una delle due operazioni sopra descritte, il programma controlla se l’origine considerata è ancora
esposta; in caso affermativo si riprende il ciclo considerandola nuovamente.
Qualora le origini siano tutte vuote l’algoritmo termina; vengono allora calcolate le variabili primali e duali
(mostrate solo se di grandezza minore a 35, per evitare confusione nella visualizzazione a schermo), e il
costo primale e duale (che coincidendo danno la garanzia del buon funzionamento dell’algoritmo). Vengono
anche visualizzati i vettori xo e xd (nulli al termine del procedimento), il numero di cammini aumentanti
trovati, e il tempo di calcolo necessario per terminare il procedimento.
x khamel: studiatelo bene il codice, quando glielo fai vedere Mingozzi ti chiede un casino di roba e se non la sai ti infama!
Cmq l'algoritmo è "tradotto" in C da quello delle sue dispense.
MINGOZZI CI SEEEI?? (zelig docet) :D :asd: :asd: :rotfl:
Vi copio/incollo anche la relazione per capire come funziona...
Il programma riceve in input il numero di origini e di destinazioni, alloca dinamicamente i relativi vettori e li
riempie con numeri casuali il cui massimo e minimo sono definiti dall’utente. A questo punto viene calcolata
la somma delle quantità nei due vettori, se differiscono viene aggiunta un’origine o una destinazione fittizia
per pareggiarle. Poi viene riempita la matrice dei costi, anch’essa con valori casuali di estremi definiti
dall’utente.
Il vettore u viene riempito con i valori minimi di ogni riga, i quali vengono poi sottratti alla matrice dei costi;
lo stesso procedimento viene fatto con v, il vettore dei minimi di ogni colonna di c-u.
Inizia quindi il procedimento del trasporto vero e proprio; le quantità vengono trasportate dalle origini alle
destinazioni nei casi in cui è possibile, cioè quando nella corrispondente posizione della matrice dei costi sia
presente uno 0. Le quantità trasportate nelle relative posizioni sono memorizzate nella matrice dei flussi.
Poi vengono esaminate una per una le origini esposte, cioè quelle in cui sia rimasta una quantità non nulla.
Su di esse viene chiamata la funzione CamminoAumentante, che riceve in input l’origine esposta e restituisce
–2 se non riesce a trovare un cammino aumentante, oppure l’indice della destinazione se invece ne trova uno.
La procedura aggiorna anche gli array Po e Pd, che sono i vettori dei predecessori, in questo modo: nelle
posizioni con predecessore è inserito il suo indice, in quelle senza –2, in quella da cui parte scrive –1. Essa si
basa su una coda (implementata con una single-linked list) nella quale vengono via via inseriti gli archi che
potrebbero far parte di un possibile cammino aumentante; si provvede poi ad estrarre l’elemento in testa alla
lista, i cui dati serviranno ad aggiornare i predecessori e a decidere quali altri archi considerare.
A seconda del valore che CamminoAumentante ritorna, vengono svolte due operazioni diverse. Se viene
trovato un cammino aumentante, viene chiamata la procedura Ricostruisci, che riceve in input gli indici
dell’origine e della destinazione. Essa determina la quantità da trasportare e aggiorna di conseguenza la
matrice dei flussi, l’origine e la destinazione interessate. Questa funzione parte dal vertice destinazione, e
basandosi sui vettori dei predecessori precedentemente modificati, si serve di una pila (implementata con una
single-linked list) nella quale inserisce tutti gli archi che fanno parte del cammino, fino ad arrivare all’origine
da cui esso parte.
Se invece CamminoAumentante ritorna –2, significa che non è stato possibile trovare alcun cammino. Perciò
è necessario modificare la matrice dei costi, sommando o sottraendo la quantità delta ai vari elementi, a
seconda della posizione che occupano rispetto agli elementi modificati nei vettori dei predecessori. Vengono
modificati anche u e v, cioè le variabili duali.
Terminata una delle due operazioni sopra descritte, il programma controlla se l’origine considerata è ancora
esposta; in caso affermativo si riprende il ciclo considerandola nuovamente.
Qualora le origini siano tutte vuote l’algoritmo termina; vengono allora calcolate le variabili primali e duali
(mostrate solo se di grandezza minore a 35, per evitare confusione nella visualizzazione a schermo), e il
costo primale e duale (che coincidendo danno la garanzia del buon funzionamento dell’algoritmo). Vengono
anche visualizzati i vettori xo e xd (nulli al termine del procedimento), il numero di cammini aumentanti
trovati, e il tempo di calcolo necessario per terminare il procedimento.
janjan
08-06-2004, 13:03
Grazie mille... cmq sono anch'io di sdi e x l'esame di giove sono nella merda... Grazie mille!!!!Ma qual'è il tuo user?
bizzu
08-06-2004, 13:58
Originariamente inviato da janjan
Grazie mille... cmq sono anch'io di sdi e x l'esame di giove sono nella merda... Grazie mille!!!!Ma qual'è il tuo user?
Prego!
Ma che user vuoi sapere?
Grazie mille... cmq sono anch'io di sdi e x l'esame di giove sono nella merda... Grazie mille!!!!Ma qual'è il tuo user?
Prego!
Ma che user vuoi sapere?
janjan
08-06-2004, 14:12
il nome del tuo account all'uni... magari ci conosciamo anche... quanti anni fa lo hai dato? Io lo devo dare giove... speriamo bene.... Ciao!
bizzu
08-06-2004, 14:39
Il mio account è bizzocch, faccio il 3° anno.
Cmq l'esame l'ho passato a settembre scorso (la 4^ volta che provavo! :D )...
Cmq l'esame l'ho passato a settembre scorso (la 4^ volta che provavo! :D )...
khamel
08-06-2004, 20:35
Originariamente inviato da bizzu
x khamel: studiatelo bene il codice, quando glielo fai vedere Mingozzi ti chiede un casino di roba e se non la sai ti infama!
Cmq l'algoritmo è "tradotto" in C da quello delle sue dispense.
lo so tranquillo io il programma l'ho fatto seguendo passo passo i suoi lucidi ma non so perchè mi va sempre in loop, non mi riesco a sbloccare da li....
e contando che ho TWI/EINN sul groppone che mi porta via tutto il tempo non riuscivo a rifarlo in breve tempo da zero...
grassie tante
cmq il mio user è zannir e sono del 2 anno...
x khamel: studiatelo bene il codice, quando glielo fai vedere Mingozzi ti chiede un casino di roba e se non la sai ti infama!
Cmq l'algoritmo è "tradotto" in C da quello delle sue dispense.
lo so tranquillo io il programma l'ho fatto seguendo passo passo i suoi lucidi ma non so perchè mi va sempre in loop, non mi riesco a sbloccare da li....
e contando che ho TWI/EINN sul groppone che mi porta via tutto il tempo non riuscivo a rifarlo in breve tempo da zero...
grassie tante
cmq il mio user è zannir e sono del 2 anno...
bizzu
08-06-2004, 22:11
Originariamente inviato da khamel
lo so tranquillo io il programma l'ho fatto seguendo passo passo i suoi lucidi ma non so perchè mi va sempre in loop, non mi riesco a sbloccare da li....
Mi ricordo che anche a me era successa una cosa del genere, infatti manca qualche controllo nell'algoritmo di Mingozzi. Se non mi ricordo male, il suo non controlla se la destinazione che si sta considerando (nel cammino aumentante) abbia già un predecessore... e altre robette che però non fanno funzionare l'algoritmo.
Io ad esempio avevo "scopiazzato" il simplesso duale, ma me lo ero studiato bene, e alla fine ho calcolato che ci avrei messo lo stesso tempo per implementarlo. Quello che porta via più tempo però è il debug, che oltre a essere spesso noioso è anche frustrante... fase che può essere evitata avendo a disposizione un programma che funziona.
In bocca al lupo per RO1 allora
;)
lo so tranquillo io il programma l'ho fatto seguendo passo passo i suoi lucidi ma non so perchè mi va sempre in loop, non mi riesco a sbloccare da li....
Mi ricordo che anche a me era successa una cosa del genere, infatti manca qualche controllo nell'algoritmo di Mingozzi. Se non mi ricordo male, il suo non controlla se la destinazione che si sta considerando (nel cammino aumentante) abbia già un predecessore... e altre robette che però non fanno funzionare l'algoritmo.
Io ad esempio avevo "scopiazzato" il simplesso duale, ma me lo ero studiato bene, e alla fine ho calcolato che ci avrei messo lo stesso tempo per implementarlo. Quello che porta via più tempo però è il debug, che oltre a essere spesso noioso è anche frustrante... fase che può essere evitata avendo a disposizione un programma che funziona.
In bocca al lupo per RO1 allora
;)
khamel
09-06-2004, 10:21
ho dato una prima occhiata al programma, mi è chiaro adesso lo sistemo un po, lo divido in funzioni e gli do un'organizzata, volevo solo chiederti, forse è una domanda un po stupida, se tolgo gli if che controllano se sei in modalità debug non comprometto niente vero?
OT
Vedo che sei di rimini anche tu non hai saputo della cena che abbiamo fatto una ventina di giorni fa?
/OT
grazie ancora se lo passo ci becchiamo i facoltà che ti offro una birra
OT
Vedo che sei di rimini anche tu non hai saputo della cena che abbiamo fatto una ventina di giorni fa?
/OT
grazie ancora se lo passo ci becchiamo i facoltà che ti offro una birra
khamel
09-06-2004, 12:41
ok l'ho praticamente sventrato e organizzato bene, funziona ancora, i costi duali e primali coincidono quindi tutto ok...
l'unico problema è quando alla fine del programma faccio il free della memoria... a volte mi solleva un'eccezionea volte no ma le strutture dati allocate sono sempre le stesse tanto...
mmm cmq penso che non sia un problema in fondo quello che deve fare lo fa...
l'unico problema è quando alla fine del programma faccio il free della memoria... a volte mi solleva un'eccezionea volte no ma le strutture dati allocate sono sempre le stesse tanto...
mmm cmq penso che non sia un problema in fondo quello che deve fare lo fa...
janjan
11-06-2004, 10:38
khamel.... zannir.... 2° anno... esame di twi.... non sarai mica Rocco!!!! Non ci credo, guarda te!!!!Chi mi incontro sul forum!!!!
khamel
11-06-2004, 13:20
certo sono io ma non ho capito chi sei te.... senza il tuo user o il tuo nome e cognome faccio un po fatica....
Ciao ;)
Ciao ;)
khamel
12-06-2004, 11:33
ehi janjan mi vorresti dire con chi ho il piacere di parlare?? mi hai messo una gran curiosità adesso... non mi immagino proprio chi tu sia anche perchè non 6 tra quelli che conosco che so che scrivono qua sul forum... :D :D
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.