URL:         /axel/ineuronale_netze_ss01_blatt5.html
 
 
 

Aufgabe 5 - Theorieaufgabe (6 Punkte)
 
 

In der Vorlesung wurde gezeigt wie die Boltzmann Maschine (BM)  zur Lösung des max-cut Problems verwendet werden kann. Ein noch berühmteres kombinatorisches Optimierungsproblem ist das travelling salesman proplem (TSP).
Ein Handlungsreisender soll n Städte besuchen. Jede Stadt soll genau einmal besucht werden. Die Gesamtroutenlänge soll minimiert werden.  Um dies Problem mit einer BM zu lösen verwendet man ein Netz aus nxn Neuronen. Im Beispiel von 5 Städten a1,a2,a3,a4,a5 sähe eine Lösung so aus:
 
 

1	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	0	0	0	1
0	0	0	1	0

dies bedeutet, dass das die Stadt a1 zuerst besucht wird, die Stadt a2 als dritte, die Stadt a3 als zweite die Stadt a4 als letzte und die Stadt a5 als vierte in der Tour. Aufgabe ist nun eine passende Energiefunktion zu definieren, die zu minimieren ist. Sie hat zwei Bestandteile, ein Teil der gewährleistet, dass die Nebenbedingungen (jede Stadt genau einmal, alle Städte) erfüllt werden bei einer minimalen Lösung und einen zweiten Teil der die Tourlänge minimiert.