[Visual Basic] Aiuto amica università gestionale

[davide87]

Ciao a tutti una mia amica deve fare un esame all'università gli hanno dato un programma in visual basic e deve capirlo per poi rispondere alle domande del professore ( lei va a ingegneria gestionale ) qualcuno può scrivere una sorta di riassunto in parole povere

Sub Greedy()
Dim vett_riga() 'memorizza il valore minimo per ogni riga
Dim visitati() As Boolean 'memorizza i nodi visitati
Dim i, j As Integer
Dim nCitta As Integer
Dim step As Integer
Dim min_riga
Dim min_riga2
nCitta = n
sel = Int(Rnd() * nCitta)
If sel = 0 Then
sel = 1
Else
End If

primonodo = sel
  
ReDim visitati(nCitta)
ReDim vett_riga(nCitta)


For i = 1 To nCitta

visitati(ncittà) = False

Next i
        visitati(sel) = True
        Cells(n + 3, 1) = sel
        
        min_riga = 1000000
       

For step = 1 To nCitta - 1
        
        
        For i = 1 To nCitta
            
                  If i <> sel And visitati(i) = False Then
                            
                            vett_riga(i) = Cells(sel, i)
        
                
                                    If vett_riga(i) <= min_riga Then 'aggiorno il minimo
                                        min_riga = vett_riga(i)
                                        puntatore = i
                                        
                                    Else
                                    End If
                    Else
                    End If
        Next i
        costo_totale = costo_totale + min_riga 'aggiorna il costo totale ad ogni iterazione
        sel = puntatore
        visitati(primonodo) = True
        visitati(puntatore) = True
        Cells(n + 3, step + 1) = sel
      
        Cells(n + 4, step + 1) = min_riga
min_riga = 1000000


Next step



Cells(n + 3, nCitta + 1) = primonodo
ritorno = Cells(sel, primonodo)
Cells(n + 4, nCitta + 1) = ritorno
costo_totale = costo_totale + Cells(sel, primonodo)

Cells(n + 6, 1) = "Il costo totale è:"
Cells(n + 7, 1) = costo_totale


End Sub

[Daniels118]

Per quanto la facoltà scelta dalla tua amica non sia specializzata in questo settore, non credo che il suo professore l'abbia invitata all'esame senza farle prima un corso.
Il regolamento vieta la risoluzione di compiti ed esercizi, se c'è qualcosa in particolare che non ha capito saremo lieti di aiutarla.
Inoltre senza l'indentazione corretta nessuno vorrà leggerlo.

[davide87]

è un programma in visual basic che fanno girare in excel, non hanno fatto nessun corso, non c'è niente da risolvere deve solo capire come funziona riga per riga.
Lei sa questo:
problema del commesso viaggiatore

in poche parole io ho una matrice dove su righe e colonne ho delle città

e dentro la matrice le distanze, in pratica devo visitare tutte le città una sola volta cercando il percorso minimo

io so a parole che il codice dice "prendi il primo nodo, trova il minimo su quella riga, scegli il nodo corrispondente se non è stato mai visitato, aggiorna il costo totale e rifai tutto partendo da quel nodo

[FirstDance]

Originariamente inviato da davide87

è un programma in visual basic che fanno girare in excel, non hanno fatto nessun corso, non c'è niente da risolvere deve solo capire come funziona riga per riga.

Io dico che se non lo capisce non dovrebbe presentarsi all'esame.

[Daniels118]

A parte che l'indentazione lascia ancora molto a desiderare... ma chi ha scritto il programma? E' - senza offesa - scritto coi piedi.
Per esempio, vett_riga è un vettore, ma potrebbe benissimo essere uno scalare.
L'istruzione visitati(primonodo) = True si trova in un ciclo, ma primonodo è costante, l'istruzione viene ripetuta inutilmente.
Gli else sono tutti vuoti e si possono eliminare.

Ed infine arriviamo all'errore più grande... l'algoritmo in oggetto non calcola il percorso minimo, perché va sempre verso la città più vicina all'ultima visitata, senza tenere conto di quanto sono distanti le rimanenti città da quella scelta.

Considera questa matrice:

    A    B    C    D
A   0   10   20   30
B  10    0  100  200
C  20  100    0 1000
D  30  200 1000    0

Il *tuo* algoritmo visiterebbe le città nell'ordine A B C D, che produrrebbe un costo pari a 10+100+1000 = 1100, ma esiste almeno una soluzione migliore:
A D B C, di costo 30+200+100=330.
Non per niente la complessità computazionale di questo problema è n!, mentre in quell'algoritmo è solo n^2.

Per concludere, secondo me c'è più di qualcosa da risolvere, comunque se sai già come funziona l'algoritmo non ho capito di cos'altro hai bisogno.

PS. quoto FirstDance.

[davide87]

Originariamente inviato da Daniels118

A parte che l'indentazione lascia ancora molto a desiderare... ma chi ha scritto il programma? E' - senza offesa - scritto coi piedi.
Per esempio, vett_riga è un vettore, ma potrebbe benissimo essere uno scalare.
L'istruzione visitati(primonodo) = True si trova in un ciclo, ma primonodo è costante, l'istruzione viene ripetuta inutilmente.
Gli else sono tutti vuoti e si possono eliminare.

Ed infine arriviamo all'errore più grande... l'algoritmo in oggetto non calcola il percorso minimo, perché va sempre verso la città più vicina all'ultima visitata, senza tenere conto di quanto sono distanti le rimanenti città da quella scelta.

Considera questa matrice:

    A    B    C    D
A   0   10   20   30
B  10    0  100  200
C  20  100    0 1000
D  30  200 1000    0

Il *tuo* algoritmo visiterebbe le città nell'ordine A B C D, che produrrebbe un costo pari a 10+100+1000 = 1100, ma esiste almeno una soluzione migliore:
A D B C, di costo 30+200+100=330.
Non per niente la complessità computazionale di questo problema è n!, mentre in quell'algoritmo è solo n^2.

Per concludere, secondo me c'è più di qualcosa da risolvere, comunque se sai già come funziona l'algoritmo non ho capito di cos'altro hai bisogno.

PS. quoto FirstDance.

Il programma l'ha fatto il professore, la mia amica mi dice che funziona, lavora su una matrice random generata da una macro in excel...

[lorenzo001]

Non so di che "tipo" di professore parli ma non riesco ad immaginare una persona che insegna programmazione e che lascia le Else vuote ... me le aspetto da uno studente/studentessa non da un docente ...

[davide87]

Originariamente inviato da lorenzo001

Non so di che "tipo" di professore parli ma non riesco ad immaginare una persona che insegna programmazione e che lascia le Else vuote ... me le aspetto da uno studente/studentessa non da un docente ...

Professore universitario ingegneria gestionale, l'esame è: Progettazione e simulazione dei sistemi di produzione e servizi

[airon]

Se a quel "professorone" hanno dato quel corso e la cattedra posso sicuramente ambire a diventare rettore della normale di Pisa

Come detto è l'algoritmo mal implementato (anzi sbagliato, come ti ha fatto notare) del percorso minimo.

[Daniels118]

Per dirla tutta l'algoritmo lavora in accordo con il nome che gli è stato dato: greedy, significa che costruisce la soluzione finale scegliendo la soluzione migliore ad ogni passo (migliore solo per quel passo).
Di fatto il risultato finale non è sempre il migliore, come già spiegato e dimostrato nell'esempio che ho fatto prima.

[FirstDance]

Credo che questo programma sia prima di tutto un esercizio didattico, dove probabilmente si vuole porre l'attenzione su determinate caratteristiche, ignorandone deliberatamente altre come l'ottimizzazione.
Per quello che può valere, non sono comunque d'accordo: sarebbe meglio mostrare da subito come si scrive un programma, per consentire allo studente di avere anche un approccio euristico alla programmazione.
Oppure, più semplicemente, quel professore non sa programmare.

In ogni caso, l'esercizio se l'ha dato alla ragazza è per farglielo studiare, non capisco che senso abbia venire a chiedere a noi come si risolve.
Se non è capace di comprendere l'esercizio, allora vuol dire che non merita nemmeno di passare l'esame, mi pare lapalissiano.

[WarDuck]

Originariamente inviato da Daniels118

Per dirla tutta l'algoritmo lavora in accordo con il nome che gli è stato dato: greedy, significa che costruisce la soluzione finale scegliendo la soluzione migliore ad ogni passo (migliore solo per quel passo).
Di fatto il risultato finale non è sempre il migliore, come già spiegato e dimostrato nell'esempio che ho fatto prima.

Il che non è sbagliato, è una ottimizzazione greedy appunto, che naviga ottimi locali e non verso l'ottimo globale, come tale ammette una soluzione sub-ottima.

Immagino che il corso tratti di quello.

Comunque concordo che dovrebbe sforzarsi di capire come funziona.

[Daniels118]

Originariamente inviato da WarDuck

Il che non è sbagliato, è una ottimizzazione greedy appunto, che naviga ottimi locali e non verso l'ottimo globale, come tale ammette una soluzione sub-ottima.

Immagino che il corso tratti di quello.

Comunque concordo che dovrebbe sforzarsi di capire come funziona.

Infatti io non ho mai detto che l'algoritmo è sbagliato, ho detto che è stato commesso un grave errore senza specificare dove, il che può significare:
(nell'implementazione di quanto richiesto) OR (nell'interpretazione dell'algoritmo)


Però non ho ancora capito cosa vorrebbe davide87, visto che sa già "a parole" cosa fa l'algoritmo... altre parole?

[davide87]

La mia amica ripeto fa ingegneria gestionale non gli hanno mai fatto seguire corsi di programmazione e l'esame non riguarda la programmazione.
Lei cercava una spiegazione riga per riga e cmq l'esame è oggi poi vi dirò