Minimierungsproblem Zahlenraster (ohne optimale Lösung) - Suche Vorgehen

Neue Frage »

Schneeeule Auf diesen Beitrag antworten »
Minimierungsproblem Zahlenraster (ohne optimale Lösung) - Suche Vorgehen
Hallo,

bei folgendem Problem erhoffe ich mir eine Art Anleitung zu finden, wie man derartige Probleme lösen könnte.
Vorweg genommen - es gibt nicht immer eine optimale Lösung. Je größer die Zahlenraster, deswo schwieriger oder unmöglich sollte eine optimale Lösung zu ermitteln sein.
Allerdings suche ich einen Weg um eine möglichst gute Lösung zu erzielen.

Situation:
Gegeben ist eine Reihe von Datensätzen, die in einer Tabelle angeordnet sind*.
Jeder Kombination eines Datensatzes wurde zu einem anderen Datensatz eine Zahl zugeordnet (Zustände).
Alle für die Aufgabe wichtigen Zustände besitzten eine 1 oder 2 (blau markiert), welche bestimmte Kombinationen von Datensätzen verbinden, sind blau markiert und interessant.

*Auf Grund der tabellarischen Form ist der Teil rechts oben zu dem Teil links unten gespiegelt (getrennt durch die Diagonale).


Aufgabe:
Es sollen aus der Tabelle soviel als möglich Datensätze entfernt werden (Leaver), so dass am Ende so wenig als möglich Datensätze übrig bleiben (Remainer).


Regeln zum Entfernen:
1. Von jedem beliebigen Datensatz dürfen alle oder ein Teil dessen Partner-Datensätze, welche durch den zustand 1 oder 2 verbunden sind, entfernt werden (Leaver).
Der Datensatz selbst wird ein Remainer. Remainer sind bis zum Ende nicht mehr entfernbar.
2. Sollten von einem Remainer nicht alle Partner-Datensätze (Zustand 1 oder 2) entfernt werden, wo werden diese nicht entfernten Datensätze zwingend ebenfalls Remainer.
Allerdings dürfen von diesen Remainern auch wieder deren Partner-Datensätze mit Zustand 1 oder 2 entfernt werden (allerdings nur von Partner-Datensätzen, die in einem vorherigen Schritt selbst noch keine Remainer sind).
3. Wenn ein Datensatz keinen Partner mit einer 1 oder 2 (mehr) hat, wird er zwangsläufig ein Remainer.


Ziel: Am Ende sollen so wenig als möglich Remainer übrig bleiben.


Jede denkbare Hilfe aus den Datensätzen oder Verwenden von Hilfsspalten, Hilfsberechnung etc. darf genutzt werden.
Es wird keine Brute-Force-Lösung gesucht, da dies schon bei mittleren Rastern praktisch nicht errechenbar ist.


Am konkreten Beispiel:

Gegeben ist ein Zahlenraster mit 37 Datensätzen (fett die Nummern der Datensätze; grün Zustandstabelle; blau die "interessanten" Zustände 1 und 2)

[attach]42307[/attach]


Bei diesem Zahlenraster lässt sich noch realtiv leicht ein "optimales" Ergebnis an Remainern ermitteln - es lautet 3.
Es gibt verschiedene Remainer-Kombinationen, welche dieses Ergebnis liefern.



Wie könnte man aber stattdessen bei einem größeren Raster vorgehen, z. B. mit 170 Datensätzen?
Also in welcher Reihenfolge und nach welchen Kriterien sollte man nacheinander möglichst sinnvoll die Leaver entfernen?
Es macht wahrscheinlich Sinn, wenn man z. B. ggf. nicht immer alle Partner eines Remain-Datensatzes entfernt, sondern auch mal einen schont und diesen dann zu einem neuen Remainer macht. Man nimmt dabei einen kurzfristigen Nachteil in Kauf, um am Ende durch eine kleinere Endsumme an Remainern einen Vorteil zu haben (was ja das Ziel ist). Nur nach welcher "Regel" könnte man das durchführen?


Beispiel 2 (170 Datensätze):

Als gute Lösung ist mir bekannt, das im Beispiel 2 mit 170 Datensätzen 13 Remainer verbleiben können (Nr. 9,11,20,55,57,79,101,102,106,123,144,147,162).

Beide Beispiele sind als Excel in der Anlage enthalten. [attach]42306[/attach]

Hätte jemand einen Vorschlag, wie man da am effektivsten vorgehen kann?

Vielen Dank im Voraus
Schneeeule
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »