Algoritmo a DNA

Questo algoritmo si propono di risolvere il noto problema della ricerca dei cammini minimi.
Per chi non sapesse di cosa si tratti diamo una breve spiegazione.
Supponiamo di avere un commesso viaggiatore che deve coprire per lavoro n citta' e che vi siano m collegamenti. Chiaramente non tutte le citta' sono collegate alle altre. Si cerca un cammino che compra tutte le citta', senza mai ripassare da una citta' gia' toccata.
Vi sono vari modi di solvere questo problema, primo fra tutti quello che utilizza il backtracking. In pratica si compie una sequenza di passi casuale, se si termina in un ramo morto si fa un passo all'indietro e si ripercorre un cammino non ancora toccato.
Chiaramente questo metodo e' molto dispendioso ed, in alcuni casi, puo' portare ad un tempo di lavoro estremamente alto.
Io vi propondo una soluzione alternativa.
Supponiamo di avere le seguenti citta'
A-B-C.......
e di considerare la stringa AB come un cammino che collega la citta' A alla B.
Per prima cosa si considerano tutti i cammini che collegano le citta', quindi avremo
AB, AC, AE, BC, BE, CE, ......
Definiamo questi cammini filamenti 2.
Il passo successivo e' quello di generare i filamenti 4, questo viene fatto facendo combinare i filamenti 2 nella seguente maniera.
Supponiamo di avere AB e CD, questi due cammini si possono combinarea formare ABCD se esiste il cammino BC che fa da ponte tra i due, si devono dunque inizialmente testare tutti i possibili accoppiamenti.
Successivamente bisogna effettuare una scrematura, infatti il cammino ABCA non viene ritenuto valido, per la regola che non e' possibile ripassare su una citta' gia' visitata.
Il passo successivo e' quello di combinare i filamenti 4 per formare filamenti 8, tra cui avremo le soluzioni cercate.
I filamenti vengono creati combinando filamenti 4 e successivamente scremando nella maniera vista precedentemente.
Vediamo adesso un esempio per chiarire il metodo di lavoro di questo algoritmo.
Supponiamo di avere le seguenti citta'
A,B,C,D,E,F,G,H
ed i seguenti collegamenti

AB,AD,AG,BC,BE,CD,CF,DB,DE,EB,ED,FE,FD,FG,GH

Sviluppando otteniamo i seguenti filamenti 4

ABCD, ABCF, ABEB, ABED,
ADBC, ADBE, ADEB, ADED,
BCDB, BCDE, BCFE, BCFD,
BCFG, BEBC, BEBE, BEDB,
BEDE, CDBC, CDBE, CDEB,
CDED, CFEB, CFED, CFDB,
CFDE, CFGH, DBCD, DBCF,
DBEB, DBED, EBCD, EBCF,
EBEB, EBED, EDBC, EDBE,
EDEB, EDED, FEEBC, FEBE,
FEDB, FEDE, FDBC, FDBE,
FDEB, FDED.

Dopo una prima selezione dividiamo i filamenti in due gruppi distinti, quelli che iniziano nella citta' A e quelli che finiscono nella citta' H, se riusciamo a legare senza ottenere nodi, due filamenti appartenenti a due gruppi distinti, otteniamo un cammino che parte da A e termina in H e quindi otteniamo la soluzione.

Abbiamo
ABCD, ABCF, ABED, ADBC, ADBE, ADEB
e dall'altra parte
CFGH
quindi otteniamo
ADEBCFGH
che e' la soluzione cercata.

Pietro Bonfigli