# Kombinationsalgorithmus



## K-Man (20. Dez 2006)

Hallo
Ich habe ein Problem und suche einen Algorithmus dazu. Hab mir schon ein paar Überlegungen gemacht, aber vielleicht könnt ihr mir helfen.

Ich habe 4096 Bausteine. Ich soll 6 von diesen Bausteinen zusammenbauen. Dabei kann nicht jeder Baustein mit jedem zusammen gesetzt werden. Jeder Baustein kann mit 64 anderen Bausteinen zusammengesetzt werden. Am Ende soll ich eine Liste an 6er-Bausteinen haben, wobei jeder der 4096 Bausteine hier vorkommen sollte. Das Problem ist, jeder Baustein sollte am besten nur einmal vorkommen.
Hab mir schon überlegt, die Sache mit einem Baum oder einer Hashmap anzugehen. Aber vielleicht gibt es zu diesem Problem schon einen Algorithmus und ich weiß es nur noch nicht...

Klingt fast wie das Handelsreisen Problem. 4096 Städte, jede Stadt ist mit 64 anderen verbunden. Gesucht wird eine Liste mit Routen durch 6 Städte. Alle Städte sollen in dieser Liste vorkommen, jede Stadt soll aber am besten nur einmal vorkommen.

Hab ihr mein Problem verstanden? Hab mir schon überlegt, dass ich eine Hashmap mit 4096 Einträgen anlege und ich jeden bereits verwendeten Baustein markiere. Sollte ich mal keinen Baustein finden, der noch nicht benutzt wurde, dann müsste ich einen so auswählen, damit der übernächste Baustein zumindest wieder nicht verwendet wurde...

Wär cool, wenn jemand einen Algorithmus dazu kenn. Name oder so reicht. Zusammenbauen könnt ich den evtl alleine. Klingt jedenfalls nach einem bekannten Problem...


----------



## Gast (28. Dez 2006)

Ameisenalgorithmus evtl?


----------



## K-Man (30. Dez 2006)

Gast hat gesagt.:
			
		

> Ameisenalgorithmus evtl?


Ich hab es mal mit einem Baum probiert, der nur Referenzen auf die 4096 Bausteine verwendet. Der Algorithmus lief auch in ein paar ms durch. Muss aber erst noch sehen, ob er korrekt ist. Danke für den Tipp. Werd mich da mal näher informieren...


----------

