Verbindungen zwischen Elementen mit möglichst wenigen Überschneidungen

[Hans D]

Ich hoff ich hab das richtige Forum erwischt, eigentlich ist es eher ein Mathematisches als Java Problem, da es dabei aber um einen Algorithmus geht, kann mir hier vielleicht doch wer helfen.

Ich habe 2 Zeilen mit je n Elementen die untereinander Verbindungen haben, diese möchte ich nun durch neu anordnen der Reihenfolge mit möglichst wenigen Überschneidungen der Verbindungen darstellen.

Meine Erste Idee war durch Permutation alle Anordnungen durchzuspielen und mir die mit den wenigsten überschneidungen zu merken. Dabei kann ich die überprüfung einer Anordnung vorzeitig abbrechen wenn es schon mehr Überschneidungen gibt als ich in meiner bissher Besten Anordnung habe, oder wenn das Ergebniss für mich ausreichend ist (zb. max. 4 Überschneidungen).
Da ich aber in der ersten Zeile zwischen 5 und 10 und in der zweiten Zeile zwischen 10 und 20 Elemente hab, hätte ich mathematisch 10! * 20! Möglichkeiten was einer Zahl mit 25 Stellen entspricht. Also eher nicht praktikabel.

Kennt wer einen Algorithmus der sich mit der Thematik beschäftigt?

Hat wer Ideen wie ich zu einer Lösung kommen könnte? - Oder zumindestens ne Idee nach was ich dabei googlen könnte?

Herzlichen Dank
Hans

 

[Collinwood]

Wenn ich das Anliegen richtig verstanden habe, müsstest du sowas wie Mergesort verwenden, mit dem Zusatz, dass du nach jedem Durchlauf die beiden zusammengehörenden Elemente aus der ursprünglich zu untersuchenden Menge "entfernst", also natürlich irgendwo anders hinspeicherst. Ich stelle mir das wie ein Memory-Spiel vor... quasi 2 Karten aufgedeckt, die passen, nehm ich also aus dem Spiel. Der Algorithmus wird demnach gegen Ende immer schneller.

Wenn du noch Hilfe zum Algorithmus an sich brauchst, stehe ich gerne zur Verfügung.