[PYTHON] Calcolare il percorso con il più alto costo

[postgres]

Non riesco a risolvere un esercizio dove il professore chiede che vengano usate ricorsione/iterazione comprensioni di lista e elementi di programmazione funzionale come filter map e reduce.
Ecco il testo in inglese:

Everyday we have to face some choices and each of these choices will provide a different profit (or a drawback) for us and sometimes the profit we get from a choice depends on the choices we have done before and so on. It is a really common situation to desire to get the maximum benefit from any choice we do but in everyday situation is quite impossible since we only know the past and not where our choices address us.

Let us suppose to be in an ideal situation where both past, present and future possibilities, all their interdependencies and the cost/benefit of each choice are known. Such a base of knowledge can be represented as a direct acyclic graph (for simplicity we suppose that every choice originates only and always two scenarios and each scenario can be reached by two adjacent choices) where the nodes are the choices and the edges represent the different scenarios the choice originates; the cost/benefit of the choice is absolute, independent of the choice we do and associated to the node in the tree. The next figure represents an example of such a representation.

The goal of the exercise is to write a function (maxpath) that computes and returns the maximum benefit we can achieve from a base of knowledge as the one described above. To simplify the exercise the base of knowledge is stored per levels in a list of lists (each list contains all the nodes in a level, note that the length of the lists in adjacent levels always differs of one).

qui l'immagine:
http://cazzola.dico.unimi.it/didatti...nzata/tree.jpg

if __name__ == "__main__":
  l0 = [[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]
  l1 = [[11], [7,32], [14,14,14], [0,1,2,3], [5,99,1,2,7], [0,25,9,45, 54,1],   [99,88,77,66,55,44,33]]
  l2 = [[-3],[-7,1], [-14,-2,-10], [7,0,0, -7], [-1,1,0,1,-1], [5,-5,25,-25,-7,7]]
  l3 = [[1.2], [-1.2,3.14], [1,-1,0], [-3.14,5.7,-1,.23], [.1,-.2,.3,-.4,.5]]
  print(l0, ":-",end=’ ’) 
  print(maxpath(l0))
  print(l1, ":-",end=’ ’)
  print(maxpath(l1))
  print(l2, ":-",end=’ ’)
  print(maxpath(l2))
  print(l3, ":-",end=’ ’)
  print(maxpath(l3))

e deve restituire questo:

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] :- 30
[[11], [7, 32], [14, 14, 14], [0, 1, 2, 3], [5, 99, 1, 2, 7], [0, 25, 9, 45, 54, 1], [99, 88, 77, 66, 55, 44, 33]] :- 270
[[-3], [-7, 1], [-14, -2, -10], [7, 0, 0, -7], [-1, 1, 0, 1, -1], [5, -5, 25, -25, -7, 7]] :- 22
[[1.2], [-1.2, 3.14], [1, -1, 0], [-3.14, 5.7, -1, 0.23], [0.1, -0.2, 0.3, -0.4, 0.5]] :- 9.34


Io ho provato con scarsi risultati:

La mia idea era di fare un doppio for e dirgli di sommare gli elementi di una lista con quella successiva seguendo lo schema: somma quello nella tua stessa posizione e in quella successiva.

def maxpath(ll):

  listaris = list()
  #caso base sommo
  ris = ll[0][0]  + ll[1][0] 
  ris2 = ll[0][0]  + ll[1][1]   
  ll[1][0] = ris
  ll[1][1] = ris2            
  for i in range(0,len(ll)-1): 
    for j in range(0,len(ll[i])-1):      
      ris = ll[i][j]  + ll[i+1][j]          #i = lista successiva ma nella stessa posizione "0"
      ris2 = ll[i][j]  + ll[i+1][j+1]        #i = lista successiva ma anche posizione successiva "1"
      listaris.append(ris)  #appendo il risultato della somma alla lista finale 
      listaris.append(ris2)
      ll[i] = listaris
 
  print ("listaris {0}".format(listaris))

Non capisco perchè con un doppio for non mi faccia tutti i casi possibili.
Se vi vengono in mente altre possibilità più veloci, più compatte, più sensate ditemelo pure, non voglio risolverlo per forza in questa maniera!

[postgres]

qualche consiglio?

[ingframin]

Il tuo grafo lo puoi rappresentare/pensare come un albero e quindi lo puoi scorrere anche con un algoritmo tipo http://it.wikipedia.org/wiki/Breadth-first_search
Per ogni figlio che trovi sommi il peso del ramo al rispettivo cammino, ovviamente aggiungendo un cammino per ogni biforcazione.

Quando arrivi alla fine dell'albero avrai una lista di camminicol relativo peso, basta che in questa lista cerchi il massimo ed e' fatta.

Il tuo for comunque contiene un errore, se fai range(0,len(ll)-1) salti ogni volta l'ultimo elemento. Devi usare range(len(ll)) e range(ll[i]) e vedi che te li prende tutti.

[gugoXX]

L'immagine e' su un sito protetto da user+pwd

Comunque io costruirei prima la matrice delle adiacenze,
aggiungerei un nodo fittizio raggiungibile da tutti i nodi finali
e poi userei Dijkstra per calcolare il percorso piu' efficiente.

Partendo dal primo esempio
[[7], [3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]]

Avremo 15 nodi

tolgo il peso della prima transizione, che e' 7 ed di base per tutti i percorsi, e aggiungo un nodo finale.

[3,8], [8,1,0], [2,7,4,4], [4,5,2,6,5]
[1,2], [3,4,5], [6,7,8,9], [A,B,C,D,E]

    0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
0=> x,3,8,x,x,x,x,x,x,x,x,x,x,x,x,x
1=> x,x,x,8,1,x,x,x,x,x,x,x,x,x,x,x
2=> x,x,x,x,1,0,x,x,x,x,x,x,x,x,x,x
3=> x,x,x,x,x,x,2,7,x,x,x,x,x,x,x,x
4=> x,x,x,x,x,x,x,7,8,x,x,x,x,x,x,x
5=> x,x,x,x,x,x,x,x,8,9,x,x,x,x,x,x
6=> x,x,x,x,x,x,x,x,x,x,4,5,x,x,x,x
7=> x,x,x,x,x,x,x,x,x,x,x,5,2,x,x,x
8=> x,x,x,x,x,x,x,x,x,x,x,x,2,6,x,x
9=> x,x,x,x,x,x,x,x,x,x,x,x,x,6,5,x
A=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,0
B=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,0
C=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,0
D=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,0
E=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,0
F=> x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x

Ovvero, dal nodo 0 posso andare ai nodi 1 e 2, con peso rispettivamente di 3 e 8
dal nodo 1 posso andare ai nodi 2 e 4, con peso rispettivamente di 8 e 1
...
dal nodo E posso andare solo al nodo F, ed e' gratis.
dal nodo F non vado da nessuna parte.

Dove x significa non connessione, e che sarebbe infinito nel Dijkstra normale che serve per cercare il percorso piu' breve.
Ma per noi si tratta di cercare il percorso piu' lungo.
Il Dijkstra modificato per cercare il percorso piu' lungo prevede che ad ogni passo nel calcolare il potenziale di un nodo si scelga il valore piu' alto invece che quello piu' basso.
occorre quindi che la X valga -infinito (o semplicemente non usare l'arco corrispondente durante la realizzazione dell'algoritmo)

Il gioco quindi sarebbe trovare il percorso piu' lungo tra il nodo 0 e il nodo F

Quando ci fossero pesi negativi su qualche arco dovrebbe essere sufficiente sommare un offset a tutti gli archi per farli tornare tutti positivi, e poi ricordarsi di sottrarli tutti alla fine per il calcolo del percorso finale.

Diciamo che per un esercizio con quei pochi valori dati Dijkstra e' un po' overkilling, ma in teoria dovrebbe dare un'ottima soluzione.
E' probabile che inoltre Dijkstra applicato qui non faccia altro che cercare tutti i percorsi, data la geometria del grafo.
Ma ti proporrei comunque di scrivere un algoritmo Dijkstra generico in Python, che userai tante altre volte nella tua carriera.

[postgres]

ma dikstra si scrive più o meno nelllo stesso numero di righe con cui ho scritto io la mia soluzione?

[gugoXX]

Indipendentemente da Dijkstra e Python, la complessita' di ogni algoritmo ha una suo ordine, ed e' quello che occorre confrontare.
E non dipende dal numero di righe.