Come vi avevo promesso posto il link ad una bozza delle soluzioni dei problemi delle OII 2014, in attesa della versione finale.
Nel problema bottleneck, perchè iterate sugli archi e non sui vertici?
Uhm… in che senso? L’obiettivo è cercare, tra gli archi che appartengono ad almeno uno dei percorsi buoni (buono = di lunghezza minima in termini di archi), quello di peso minimo. Dato che i vertici non hanno un “peso” non puoi fare molto quando li stai iterando… ma forse non ho capito cosa intendi.
Giusto, io in gara per iterare sui nodi mi salvavo anche il costo dell’arco con peso minimo nel cammino da L e da W del nodo che stavo considerando
Probabilmente dico una cavolata, ma la soluzione di Taglialegna non è esponenziale? Per renderla dinamica, non si dovrebbero salvare le soluzioni parziali da qualche parte, per poi andarle a ripescare nelle chiamate successive?
Probabilmente dico una cavolata, ma la soluzione di Taglialegna non è esponenziale? Per renderla dinamica, non si dovrebbero salvare le soluzioni parziali da qualche parte, per poi andarle a ripescare nelle chiamate successive?cip999
“Volendo privilegiare la trasparenza nella spiegazione, abbiamo volutamente ignorato la parte di memoizzazione (memoization), che non può invece essere trascurata inuna implementazione reale.”
Pag19
Ops, mi era sfuggito… :S Grazie