Algoritmo in C
Salve a tutti!!
Sono alle prese con l'implementazione di un algoritmo in DEV-C++ e spero di trovare qualche aiutino, dato che sono alle prime armi ( o meglio ho programmato in passato, ma MAI un algoritmo di così alto spessore!)...
Cerco di descrivere un pò per volta ciò che mi interessa:
Input: Un grafo $D(N,F,A)$, $l$, $c$, $t^I$, $UB$
Output: $t^I$ ottimo
Innanzitutto, $D(N,F,A)$ è un grafo, dove $N$ è l'insieme di vertici, $F$ è l'insieme di archi, $A$ insieme di archi disgiuntivi, $l$ è un vettore peso, $c$ una funzione costo, $t^I$ si assume, inizialmente, uguale al vuoto, $UB = +\infty$ (upper bound)
Nel passo 1. chiede di calcolare la "chiusura" di $D$ applicando questa procedura:
Attraverso l'algoritmo di Floyd-Warshall calcolare la matrice di distanza massima $L^*=[l_{ij}^*]_{i,j \in N}$, oppure trovare un ciclo positivo.
Come posso iniziare ad implementare tutto questo? Il problema iniziale sta nel fatto di dover dichiarare il grafo...ho cercato online e su alcuni testi di programmazione...ma non mi sono stati d'aiuto!!
Grazie!
Sono alle prese con l'implementazione di un algoritmo in DEV-C++ e spero di trovare qualche aiutino, dato che sono alle prime armi ( o meglio ho programmato in passato, ma MAI un algoritmo di così alto spessore!)...
Cerco di descrivere un pò per volta ciò che mi interessa:
Input: Un grafo $D(N,F,A)$, $l$, $c$, $t^I$, $UB$
Output: $t^I$ ottimo
Innanzitutto, $D(N,F,A)$ è un grafo, dove $N$ è l'insieme di vertici, $F$ è l'insieme di archi, $A$ insieme di archi disgiuntivi, $l$ è un vettore peso, $c$ una funzione costo, $t^I$ si assume, inizialmente, uguale al vuoto, $UB = +\infty$ (upper bound)
Nel passo 1. chiede di calcolare la "chiusura" di $D$ applicando questa procedura:
Attraverso l'algoritmo di Floyd-Warshall calcolare la matrice di distanza massima $L^*=[l_{ij}^*]_{i,j \in N}$, oppure trovare un ciclo positivo.
Come posso iniziare ad implementare tutto questo? Il problema iniziale sta nel fatto di dover dichiarare il grafo...ho cercato online e su alcuni testi di programmazione...ma non mi sono stati d'aiuto!!
Grazie!
Risposte
Ciao,
che cosa calcola l'algoritmo? ha un nome? Perchè utilizzi un altro algoritmo di shortest path ma non dici esplicitamente che problema risolve...
che cosa calcola l'algoritmo? ha un nome? Perchè utilizzi un altro algoritmo di shortest path ma non dici esplicitamente che problema risolve...
Non conosco l'algoritmo comunque un modo classico consiste nell'utilizzare le matrici di adiacenza. In questo caso memorizzi al suo interno anche il peso di ogni arco. Per i vertici non collegati li poni a peso infinito. In pratica è una matrice il cui valore ij contiene il più corto arco che unisce i due vertici i e j (memorizza il peso).
Non capisco lo scopo di inviare alla funzione l'upper bound. Quello, una volta che hai scelto tra int e float, è una sorta di costante di sistema, a meno che tu non voglia abbassarlo.
P.S.: Dev-C++ non è più implementato e corretto da bug dal 2005 (e la versione del febbraio 2005 era una beta!) e non risulta essere stato ottimizzato per vista e 7. Trovo il suo uso piuttosto inutile e dannoso: nessuno lo usa se non qualche studente! Ci sono varie alternative opensource (eclipse CDT e code::blocks) nonché proprietarie (visual studio c++ express). Penso comunque che code::blocks sia, per una persona abituata a dev-c++ l'alternativa migliore (anche perché visual c++ è molto più indirizzato al c++). Detto questo, se non ti interessa compilare in C++, c'è anche pelles C.
La mia impressione è che chiunque consigli dev-c++ a 7 anni di distanza non programmi mai.
Non capisco lo scopo di inviare alla funzione l'upper bound. Quello, una volta che hai scelto tra int e float, è una sorta di costante di sistema, a meno che tu non voglia abbassarlo.
P.S.: Dev-C++ non è più implementato e corretto da bug dal 2005 (e la versione del febbraio 2005 era una beta!) e non risulta essere stato ottimizzato per vista e 7. Trovo il suo uso piuttosto inutile e dannoso: nessuno lo usa se non qualche studente! Ci sono varie alternative opensource (eclipse CDT e code::blocks) nonché proprietarie (visual studio c++ express). Penso comunque che code::blocks sia, per una persona abituata a dev-c++ l'alternativa migliore (anche perché visual c++ è molto più indirizzato al c++). Detto questo, se non ti interessa compilare in C++, c'è anche pelles C.
La mia impressione è che chiunque consigli dev-c++ a 7 anni di distanza non programmi mai.
@hamming_burst: non interessa il nome dell'algoritmo nè tantomeno che cosa calcola!! Il motivo di utilizzare un altro algoritmo per il calcolo della matrice di massima distanza, non è dettato dalla mia volontà, ma dalla esecuzione dell'algoritmo!
@vict85: cercherò di ragionare su quello che mi hai suggerito!! Per quanto riguarda dev-c++, non è stata una mia scelta! ma visual c++, funziona allo stesso modo? Quale versione dovrei considerare? 2010?
@vict85: cercherò di ragionare su quello che mi hai suggerito!! Per quanto riguarda dev-c++, non è stata una mia scelta! ma visual c++, funziona allo stesso modo? Quale versione dovrei considerare? 2010?
Beh, 2010 è l'ultima uscita. La 2012 è attualmente in beta (release candidate a dire il vero), penso che quella finale uscirà il prossimo anno. Se vuoi puoi scaricarti i tanti GB della versione ultimate 2012 (quella che ho installato io) ma non penso abbia molto senso se non sei interessata a provare le caratteristiche del programma.
Visual studio (quello professional) è abbastanza l'IDE standard per la programmazione in ambiente windows e soprattutto per windows. L'express è per certi versi una versione per imparare. Gli studenti e gli accademici potrebbero avere sconti alle versioni a pagamento.
Comunque code::blocks è assolutamente un valido prodotto e usa, teoricamente, lo stesso compilatore di dev-c++.
Visual studio (quello professional) è abbastanza l'IDE standard per la programmazione in ambiente windows e soprattutto per windows. L'express è per certi versi una versione per imparare. Gli studenti e gli accademici potrebbero avere sconti alle versioni a pagamento.
Comunque code::blocks è assolutamente un valido prodotto e usa, teoricamente, lo stesso compilatore di dev-c++.
"tika":
@hamming_burst: non interessa il nome dell'algoritmo nè tantomeno che cosa calcola!! Il motivo di utilizzare un altro algoritmo per il calcolo della matrice di massima distanza, non è dettato dalla mia volontà, ma dalla esecuzione dell'algoritmo!
come non serve sapere che cosa calcola
va bhe per il nome, ma come fai a scrivere un algoritmo e non sapere che problema risolve, mi pare un controsenso. Forse questo è un "semplice" esercizio di programmazione e nulla di più. Il problema a cui vine applicato sarà la sorpresa finale...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo