RUBY - algoritmo Floyd Warshall

Ciao ragazzi, non ho grandi conoscenze informatiche.
Ma devo sviluppare un algoritmo per l’ultimo esame universitario.
Devo costruire una rete idrica, avendo a disposizione i dati che
compongono la rete e una serie di vincoli.

C’è qualcuno disposto a darmi qualche illuminazione?

Grazie in anticipo a chi si renderà disponibile :slight_smile:

Roberta

2015-02-04 0:02 GMT+01:00 Roberta P. [email protected]:

C’ qualcuno disposto a darmi qualche illuminazione?

E luce fu

http://bit.ly/1zFO4Xn

Nel senso che puoi darmi una mano?! :smiley:

Cos posta la domanda risulta un po’ generica, puoi scendere pi nello
specifico?

Il giorno mer 4 feb 2015 00:26 Roberta P. [email protected] ha scritto:

On Wed, Feb 4, 2015 at 12:26 AM, Roberta P. [email protected] wrote:

Nel senso che puoi darmi una mano?! :smiley:

Trollavo, ma a quanto pare non sono riuscito nell’intento :slight_smile:

Guarda il link che ti ho mandato (e altri analoghi che trovi su
google), se poi hai problemi a capire alcune parti specifiche
dell’algoritmo o dell’implementazione prova chiedere aiuto su quelle
in particolare, e credo sar pi facile che qualcuno ti aiuti.

Io mi offro volontario ma mi servono pi dati.

Ciro Attanasio

Software Analyst e Developer

Citt : Mestre (VE)
GSM : +39 328 7577162
Nome Skype : cattani0
LinkedIn : it.linkedin.com/pub/ciro-attanasio/45/696/719
http://it.linkedin.com/pub/ciro-attanasio/45/696/719
Sito Web : www.pasticcinformatici.com
http://www.pasticcinformatici.com
Partita Iva : 05263250655

Avviso ai sensi del Dlgs. 196/2003 e art. 616 Cod.Pen. Il contenuto di
questo messaggio di posta e di eventuali allegati rivolto unicamente
al destinatario cui indirizzato e pu contenere informazioni la cui
riservatezza tutelata. Sono vietati la riproduzione e l’uso di questo
messaggio in mancanza di autorizzazioni del destinatario. Se avete
ricevuto questo messaggio per errore, vogliate cortesemente comunicarlo
immediatamente per telefono o e-mail al mittente Attanasio C… Il
presente messaggio NON E’ INVIATO A TITOLO PERSONALE ed inerente

Il 04/02/2015 00:02, Roberta P. ha scritto:

Grandi! :slight_smile:
L’obiettivo del progetto è trovare una rete idrica per l’irrigazione di
7 differenti distretti territoriali(una rete per distretto).
Ogni distretto è diviso in diversi appezzamenti di terreno (proprietà) e
ha un nodo di allaccio a una rete irrigua principale.
L’obiettivo è quello di progettare, per ogni distretto, una rete irrigua
locale di minimo costo che non attraversi alcuna proprietà.

Ho i dati del grafo in questo formato:
(nodo i, nodo, j, costo)
es. c’è un arco da i a j che ha costo 10
Il grafo è connesso e non orientato.
La rappresentazione del grafo è tipo questa (ma molto molto più grande!)
http://it.wikipedia.org/wiki/Utente:SilsisScalaZarli/Grafo_Planare
e ogni area racchiusa dagli archi rappresenta un appezzamento di terreno
che deve essere servito dalla rete idrica.

Per il progetto devo applicare l’algoritmo di Steiner, che, non essendo
risolvibile in tempo polinomiale, ha bisogno di vari sottopassaggi.

Ho immaginato di:

  1. inserire dei nodi ‘terminali’ fittizi in ogni proprietà e i relativi
    archi fittizi per connettere i nodi terminali ai nodi confinanti;
  2. creare un grafo ‘metrico’ tra tutti i nodi terminali: ossia creare un
    cammino minimo tra tutte le proprietà (ogni proprietà n-esima deve avere
    un arco che la collega con ognuna delle altre n-1 proprietà);
  3. trovare il minimo albero ricoprente sul ‘nuovo’ grafo formato da
    tutti i nodi terminali e tutti i cammini output del passo precedente;
  4. associare ad ogni arco dell’albero ricoprente il cammino minimo sul
    grafo ‘originario’;
  5. identificare quindi l’abero minimo ricoprente sul grafo originario e
    i relativi nodi di Steiner, eliminando, come ultimo step, i nodi e gli
    archi fittizi che avevo inserito all’inizio.

Non so se sto ragionando bene…ma più o meno l’ho immaginato così.
Quindi come prima cosa vorrei applicare l’algoritmo di Floyd Warshall
per trovare tutti i cammini tra i nodi fittizi…
Ruby ha quest’algoritmo, ma…non saprei come ‘allinearlo’ ai dati che
ho a disposizione:

def floyd_warshall(weight=nil, zero=0)
c = Hash.new {|h,k| h[k] = Hash.new}
path = Hash.new {|h,k| h[k] = Hash.new}
delta = Hash.new {|h,k| h[k] = 0}
edges.each do |e|
delta[e.source] += 1
delta[e.target] -= 1
path[e.source][e.target] = e.target
c[e.source][e.target] = cost(e, weight)
end
vertices.each do |k|
vertices.each do |i|
if c[i][k]
vertices.each do |j|
if c[k][j] &&
(c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j]))
path[i][j] = path[i][k]
c[i][j] = c[i][k] + c[k][j]
return nil if i == j and c[i][j] < zero
end
end
end
end
end
[c, path, delta]
end # floyd_warshall

end # Distance

end # Graph
end # GRATR

Grazie in anticipo a chi mi darà una mano :slight_smile:

On Feb 4, 2015 8:02 AM, “Stefano P.” [email protected]
wrote:

On Wed, Feb 4, 2015 at 12:26 AM, Roberta P. [email protected] wrote:

Nel senso che puoi darmi una mano?! :smiley:

Trollavo, ma a quanto pare non sono riuscito nell’intento :slight_smile:

Qualcuno ha apprezzato :smiley:

Ciao, da quel codice si capisce che tu non solo non conosci ruby ma in
generale non sai programmare. E’ difficile aiutarti se non sai neanche
di cosa stiamo parlando, non credi?

E’ un’accozzaglia di copia incolla, pieno di errori, non c’è neanche una
base di partenza.

Ciao,

In realt mi sembra che si sia limitata ad incollare limplementazione di
questo algoritmo nella gemma GRATR

http://www.rubydoc.info/gems/gratr/0.4.3/GRATR/Graph/Distance#floyd_warshall-instance_method

Anche io ho apprezzato :slight_smile:

Mi trattengo dal commento acidissimo… la laurea non ha a che fare
con l’informatica vero?

On 4 February 2015 at 20:36, maurizio de magnis
[email protected] wrote:

[email protected]
http://lists.ruby-it.org/mailman/listinfo/ml


$ cd /pub
$ more beer

Il primo blog di application security italiano morbido fuori e
croccante dentro: http://codiceinsicuro.it

Ciao ragazzi, noto ‘con piacere’ che sui forum è dura trovare un aiuto,
si trovano solo commenti ‘di attacco’ e demoralizzanti.
Se fossi stata un genio in programmazione non vi avrei chiesto aiuto :wink:
non credete?!

E se stessi prendendo una laurea in informatica o similari, non starei
di certo a questi livelli…

Tiratevela di meno, che nessuno è nato ‘imparato’, per dirla in gergo!

Grazie lo stesso per il tempo che avete dedicato alla lettura di questo
post, certo poco costruttiva, dati i commenti!!

:open_mouth: se qui ci sono stati commenti di attacco vieni sul forum di
Nonciclopedia e cambierai parere riguardo “commenti di attacco” :stuck_out_tongue:

Il giorno mar 17 feb 2015 22:12 Roberta P. [email protected] ha
scritto:

Alcuni cercano di mantenere un tono “rilassato”, ma ogni tanto risulta
necessario un reality check.
Sei all’ultimo esame universitario e quindi non sei una novelina, ma
nonostante questo avanzi verso un traguardo così importante (l’ultimo
esame
universitario! ;-)) dimostrando lacune “significative” e per questo
strane.

Non stai seguendo un corso di stampo informatico ma suppongo che per
ogni
esame tu ti debba preparare sufficientemente.
Dato che non sei una novellina, avrai sicuramente avuto modo di
sviluppare
delle tecniche di studio per affrontare esami non strettamente legati al
nocciolo del tuo corso di laurea.

Non vedo risposte in cui qualcuno se l’è tirata o ha dimostrato di
essere
nato imparato.
Vedo una richiesta di aiuto generica per un problema non banale, esposta
nella forma (bada, è solo la mia imterpretazione):

“chi mi dedica il suo tempo per capire il mio problema e per scrivermi
il
95% della soluzione che mi permetta di ottenere i dati che il prof mi ha
fornito e che trascriverò verbatim senza neanche cercare di comprendere

il problema, né il processo di ottenimento della soluzione e rendendo di
fatto sia inutile (in quanto non mi resterà alcuna nozione utile) che
dannoso (in quanto mi verrà “certificata” una competenza che non ho) lo
sforzo di chi mi ha aiutato?”

Quindi, permettimi di dare 3 consigli a chi è saggio:

  1. take it easy: non prendertela
  2. fail fast: se c’è qualcosa che non va bene nel tuo approccio, meglio
    rendersene conto subito
  3. iterate: cambia ciò che non ha funzionato e riprovaci

L’onere di dimostrare che ti stai sbattendo è tutto tuo.

Aiutaci ad aiutarti :slight_smile:

Praticamente: esponi il problema con il massimo rigore e dettaglio
possibile e assieme ad esso anche tutto ciò che hai ottenuto fino ad ora
(non parlo solo di codice, parlo di processo e di logica).

Ricorda che sei te che devi superare l’esame, mica gli altri utenti del
forum :slight_smile:

2015-02-17 22:12 GMT+01:00 Roberta P. [email protected]:

Cara Roberta… CHE PALLE!!!

Sei all’ultimo esame universitario quindi non sei una bambina, sei una
donna che si sta per affacciare al mondo del lavoro.

Ti accorgerai, anche se in realtà è una cosa della quale dovresti già
aver preso familiarità, che è ben diverso dire “oh ragazzi, non sono
capace… ho buttato lì questo codice ma non funziona, ho cercato qui
e là e non ne vengo a capo. mi date una mano per favore?” piuttosto
che dire “mi fate il compito per l’ultimo esame universitario?”.

Noi possiamo anche tirarcela di meno ma tu impara che nella vita se
vuoi aiuto devi sbatterti anche perché questo non è un forum di aiuto
universitario, noi non siamo i tutor del laboratorio.
Se vuoi la pappa pronta, o impari ad usare google o ti becchi questo
genere di persone e piantala di pestare i piedi perché nessuno ti fa i
compiti.

Thanks
Paolo

2015-02-17 22:58 GMT+01:00 maurizio de magnis
[email protected]:

nocciolo del tuo corso di laurea.
fatto sia inutile (in quanto non mi resterà alcuna nozione utile) che
L’onere di dimostrare che ti stai sbattendo è tutto tuo.
2015-02-17 22:12 GMT+01:00 Roberta P. [email protected]:


Maurizio ಠ_ಠ My profile
https://plus.google.com/100973969013103507046/about


Ml mailing list
[email protected]
http://lists.ruby-it.org/mailman/listinfo/ml


$ cd /pub
$ more beer

Il primo blog di application security italiano morbido fuori e
croccante dentro: http://codiceinsicuro.it

Ciao,
in generale quando si cerca aiuto è bene esporre dettagliatamente il
problema e tutte le tecniche ed i tentativi fatti per risolverlo,
mettendo
in luce le problematiche e le criticità maggiori. Chiedere una mera
consulenza aspettandosi una risposta quasi del tutto esaustiva è
abbastanza
utopico.
Ciao

Il giorno 18 febbraio 2015 09:34, Luca P.
[email protected]
ha scritto:

Ho trovato 10 implementazioni funzionanti in 7 linguaggi in 3 query di
Google.
Questo ti aiuterà: http://bit.ly/1zFO4Xn

2015-02-18 9:14 GMT+01:00 Paolo P. [email protected]:

Roberta, questo forum è pieno di gente disposta a dare una mano ma non
puoi pretendere che la gente faccia il lavoro al posto tuo.

Il problema che devi risolvere è complesso e richiede una conoscenza
informatica che non hai e qual’è il senso di scrivere un codice che
neanche capisci. Non hai la base, non hai neanche azzeccato le chiusure
come può esserci un modo per aiutarti secondo te?