<aside> ⚠️ Domanda: come andare a capire se la proprietà triangolare vale per un nodo? Supponiamo che un grado è dato dai punti sul nodo, gli archi collegano i punti. La distanza Euclidea ha la distanza triangolare, quindi dipende dalla soluzione di costo che ci sto mettendo sopra e che dipende dalla realtà di interesse.
</aside>
Modo intelligente di far forza bruta. Un algoritmo di Brute Force per TSP non è difficile, ma mi costa davvero tantissimo. Con B&B cerchiamo di fare una esplorazione delle soluzioni ammissibili e cerco di averne un pochino e con un unico test decidere se in quell’insieme ci può essere la soluzione ottima o meno. In caso contrario butto via tutto quanto. Se invece ci potrebbe essere allora quel sotto insieme deve essere esaminato.
Per prima cosa ho bisogno di calcolarmi una soluzione corrente. Che cosa vuol dire: current solution. Una soluzione che mi dice un valore, un ciclo qualunque e mi calcolo il valore di questa soluzione.
Immaginando di avere una retta con una soluzione ottima sulla sinistra, io praticamente sto andando sulle current solution che sono tutte quante sulla destra. La mia current solution è quella che mi permette di avere sempre un upper bound rispetto alla soluzione che sto cercando. La cosa difficile di questa tecnica è: come faccio a decidere se ho un insieme di soluzioni ammissibili che sono una parte di tutte quante. Ho questo gruppetto di soluzioni e voglio capire se al loro interno possono avere la soluzione ottima oppure non ce la possono avere.
Se riesco a trovare per tutte queste una lower bound al costo di tutte queste soluzioni: in questo praticamente sto sezionando un insieme di soluzioni per cui so esattamente in che misura andare a cercare le soluzioni che mi interessano.
Possono però andare a succedere delle cose: caso in cui UB sia sopra al lower bound? Posso buttare via tutto l’insieme? Assolutamente no, e devo vedere che cosa abbiamo in mezzo. Invece quando prima il LB era sopra il UB allora buttava tutto perché essenzialmente non avevo una sega.
Il mio ottimo non so mai dove sia, potrebbe anche essere fuori dalla finestra che sto considerando di LB e UB. L’idea è che posso andare a fare delle divisioni ulteriori e fare un lavoro di precisione per buttare via una parte di queste istanze che potrebbero essere o meno interessanti, ma che sicuramente non posso andare a calcolare tutte.
Posso vedere tutte queste operazioni come un albero in cui vado a suddividere tutte le soluzioni di partenza in diversi rami che rappresentano i vari sotto insieme di soluzioni che provengono dal nodo padre.
E’ interessante perché riesco a considerare, senza calcolare, le soluzioni che so non essere in alcun modo interessanti per andare a definire quello che poi alla fine sarà un ottimo.
Ovviamente non possiamo dire che abbiamo risolto TSP, perché? Perché potrei dover controllare tutte quante le istanze e andare quindi ad essere esponenziale o fattoriale per la dimensione dell’input. Quindi alla fine non posso avere un costo fisso polinomiale e non ho risolto in P il problema di TSP. Ricado comunque potenzialmente nei costi di forza bruta. Non posso concludere che sia sempre polinomiale, ma possiamo sperare di riuscire a velocizzare i tempi.
Se non vogliamo andare fino in fondo, quello che possiamo fare è fermarci ad un certo punto: definiamo un tempo massimo che vogliamo aspettare e fissiamo quello. Andiamo a valutare quello che può essere lo scarto con l’ottimo. Andando a valutare per tutti quanti i sotto insieme che abbiamo scartato quanto vale la distanza.
Come faccio a fare branching? Quando ho un certo insieme di soluzioni ammissibili e come faccio a calcolare il mio lower bound? Nel nostro caso la prima cosa è andare a stabilire come fare, quali saranno i nostri nodi ovvero i nostri sotto insiemi delle soluzioni ammissibili.
Il nostro nodo root (tutti gli hamiltoniani possibili), dobbiamo avere un modo per farlo in maniera compatta e tenerlo in maniera compatta. Allora quello che facciamo è rappresentiamo un sotto insieme di soluzioni con tutti quanti i cicli hamiltoniani in un sotto grafo di partenza. Questo è il grafo di partenza completo e pesato.
G = (V, E) e $G_1$ sarà essenzialmente il nostro grafo di partenza. Se prendo un altro nodo del mio albero di esecuzione. Quando vado a fare la divisione come faccio?
$G_1 \rightarrow G' = (V,E') \space di \space cui \space E'\sube E$
Quando arrivo alla fine in teoria ho un ciclo hamiltoniano e devo fare la valutazione solo allora del costo effettivo. Ci sono dei grafi in cui ho dei nodi il cui grado non è uguale a 2, questo praticamente mi porta ad avere una situazione in cui so sicuramente che non potrei avere un ciclo hamiltoniano.
Devo riuscire a capire come tutte le soluzioni ammissibili che sono in un grafo sono interessanti oppure no e quindi calcolare il LB alle soluzioni. In più rimane da considerare come fare banching.