Vogliamo cercare di restare nel nostro spazio delle soluzioni ammissibili, senza dover stare ad esplorare tutto, vogliamo andare a concentrarci su una parte specifica di essa. Vogliamo utilizzare una struttura fondamentale per i problemi di programmazione lineare, che è quello con cui vogliamo andare a fare. Il fatto è che spostandoci leggermente da un punto tra le soluzioni, possiamo gestire in modo molto semplice il modo con cui si sposta la retta dei valori. ...
Questi problemi sono una sottoclasse della programmazione lineare con variabili reali. (Alcuni riescono a riconoscere se un problema è in questa forma, e lo risolvono in modo istantaneo se questo succede). Un problema dei router è un classico problema di flusso, che si risolvono con questi algoritmi polinomiali Note introduttive Rete, terminologia In questo caso andiamo ad indicare con rete un grafo con $G = (N, A)$ con $N$ nodi e $A$ archi, che solitamente sono diretti con pesi associati. Possiamo interpretare gli archi come canali in cui fluiranno un qualcosa (ad esempio acqua in un tubo). Questi possono essere discreti o continui (mi sembra di ricordare che il discreto stranamente è più facile del continuo, non so se vale anche in questo caso). Abbiamo poi i nodi che sono punti di ingresso e uscita della nostra rete. ...
Algoritmo del simplesso Ricerca della direzione migliore Ricerca dello step Pseudocodice Slide B sono gli indici di partenza, poi questi vengono aggiornati In riga 5 vado a checkare se ho direzioni di crescita possibili, se è tutto positivo non ne ho. in riga 6, si sceglie il più piccol per evitare loop. L’idea in generale va in questo modo Cerco di trovare il duale e confrontarlo con la x attuale Se sono uguali, allora ho trovato l’ottimo ed esco Altrimenti cerco una direzione di crescita che sia anche ammissibile Continuo fino a trovare un vertice, se ho il vertice allora mi muovo lì e riapplico, altrimenti è illimitata, se non esiste un vertice. Correttezza Slide ...
Questa sezione la tengo separata rispetto agli altri per favorire lo studio, così questa roba nuova la ripasso più spesso, in seguito si può accorpare. Goldberg Tarjan/Push-relabel Questo algoritmo è importante perché introduce ragionamenti sul minimo locale che possa alla fine essere ricomposto come soluzione globale. Questa lezione youtube lo spiega da Dio Preflusso 🟩 Slide La parte nuova di questa cosa è che i vincoli di bilanciamento possono diventare una disuguaglianza. (cioè quello che arriva è di più rispetto quanto va fuori. ...