Beschränkte Permutation
25.05.2004 19:23:12
Ralf
Ich möchte Permutationen über ein Reihenfolgeproblem erzeugen, welche durch einen Vorrangraph bzw. Adjazenzmatrix beschränkt sind.
Zur Verdeutlichung folgendes Beispiel:
Ich habe drei Prozesse A,B,C die nacheinander abgearbeitet werden sollen, nur kann Prozess B nicht vor C erfolgen, ausgedrückt in der Adjazenzmatrix:
1 1 1
1 1 0
1 1 1
Ohne die Beschränkung wären alle Permutationen P={ABC,ACB,BAC,BCA,CAB,CBA}, aufgrund der Einschränkung P'={ACB,CAB}.
Das Vorgehen zuerst alle Permutationen über einen rekursiven Algorithmus zu erzeugen, und dann die verbotenen Permutationen aus der Menge zu streichen, fällt aus, da hierfür der Rechenaufwand fakultativ ansteigt.
Deshalb möchte ich einen Algorithmus implementieren, der die Möglichkeiten in einem Baum durchläuft, und verbotene Äste abschneidet, um den Rechenaufwand zu reduzieren (ist deswegen notwendig, da die Elementezahl schnell 10 übersteigt).
Wer kann mir hierbei helfen? Programmier noch nicht so lang in VBA, habe aber auch gute Kenntnisse in Java, wäre euch überaus dankbar, da ich mich in diesem Problem ziemlich verrant habe, denke ich!
Vielen Dank im Voraus
Ralf B