Live-Forum - Die aktuellen Beiträge
Datum
Titel
29.03.2024 13:14:12
28.03.2024 21:12:36
28.03.2024 18:31:49
Anzeige
Archiv - Navigation
1832to1836
Aktuelles Verzeichnis
Verzeichnis Index
Übersicht Verzeichnisse
Vorheriger Thread
Rückwärts Blättern
Nächster Thread
Vorwärts blättern
Anzeige
HERBERS
Excel-Forum (Archiv)
20+ Jahre Excel-Kompetenz: Von Anwendern, für Anwender
Inhaltsverzeichnis

sehr spez. Formel-/PQ-Lösung gesucht ...

sehr spez. Formel-/PQ-Lösung gesucht ...
05.06.2021 20:19:36
neopa
Hallo @all Freaks,
... nachdem ich mich schon einige Stundenlang vergeblich abgestrampelt habe und noch immer keine richtige Lösung gefunden habe, hoffe ich nun auf eure Hilfe.
Ziel ist es eine alphabetisch gegebene Liste (in Spalte A: "vorhanden") von Objektbezeichnung so in Spalte C um zu sortieren, dass bestimmte "Nachbarschaften" der ersten 5 Zeichen der Objektbezeichnungen in der umsortierten Liste überhaupt nicht und andere "Nachbarschaften" so wenig wie (noch vertretbar) möglich sich ergeben.
Dazu habe ich mir eine eigene Prüftabelle in M3: AG23 aufgestellt in der ich die "Nachbarschafts-"Anzahl zähle. In dieser Zählung werden sowohl die Nachbarschaften der jeweilige ersten 5 Zeichen der Objekte sowohl nach dem unmittelbar vor und auch nach dem danach liegenden Objekt ausgewertet. (Deshalb ergibt sich z.B. für Objekte die mit "AA_-_" beginnen in Y4 ein Zählwert von 5, obwohl ja nur 3 Objekte mit "AA_-_" vorhanden sind.
Ziel ist es nun "umsortiert" in Spalte C so zu generieren, dass:
1. und unverzichtbar: die grün hinterlegten Zellen in N4: AA17 auch grün bleiben (also keine unmittelbaren Nachbarschaften gleicher Objekte vorhanden sind, was mir gelingt)
2. die rötlich hinterlegten Zählwerte in N4:AG23 zu reduzieren.
3. Weitestmöglich die gelb hinterlegten auch zu reduzieren.
Ideal wäre es natürlich, es würde nach der Umsortierung kein Prüfzellwert mehr rötlich oder gelb hinterlegt sein.
Die vorhandene Anzahl an Objektbezeichnungen sind natürlich nicht starr. Es können mehr oder auch weniger werden, max werden es wohl 250 und min 15 Objekte sein. Deshalb eine "intelligenten" Tabelle. Ebenso kann die Anzahl Objekten mit gleicher 5-stelligen Bezeichnung schwanken zwischen absolut nur 1 und max, wohl ca 20% der Gesamtanzahl.
Die vorliegende "Sortierung" in Spalte C ist mein Ergebnis einer Formellösung mit mehreren Hilfsspalten, was wie ihr seht unzureichend ist.
Ich würde mich sehr freuen, wenn mir jemand die richtige Lösungsstrategie aufzeigen kann. Bin aber aber auch dankbar für jeden guten Ratschlag, der mir hilft meine bisherige "Lösung" hier: https://www.herber.de/bbs/user/146501.xlsx erheblich zu verbessern.
Danke für das Lesen bis hierher.
Gruß Werner
.. , - ...

9
Beiträge zum Forumthread
Beiträge zu diesem Forumthread

Betreff
Datum
Anwender
Anzeige
AW: sehr spez. Formel-/PQ-Lösung gesucht ...
05.06.2021 21:50:34
Yal
Hallo Werner,
es ist natürlich eine Ehre, ein langjährigen Helfer zur Hilfe zu kommen, aber auch eine Herausforderung :-)
Ich verstehe einen Punkt nicht: wie wird die "Nachbarschaft" definiert?
Bedeutet es nur, dass wenn in der sortierten Liste (Spalte A), ein Element in Position 10 ist, dann sind die Elementen in Position 9 und 11 die Nachbar sind?
Oder ist diese Betrachtung auf die 5 ersten Zeichen reduziert: alle Elemente mit dieselben ersten 5 Zeichen sind Nachbar?
(Im Beispiel sind die 3 letzten Zeichen immer gleich, daher könnte man den Beispiel auf die 2 ersten Zeichen reduzieren)
Warum muss die Nachbarschaft von DA* zu AA* (5 in Y4) reduziert werden?
Ausserdem, wenn ich die Function @_Prüf richtig verstehe, sollte nicht diese Auswertungsmatrix dieselbe Ergebnisse auf die beiden Seiten der "grüne Linie" haben?
VG
Yal
Anzeige
AW: zu Deinen Fragen und Anmerkungen ...
06.06.2021 09:01:54
neopa
Hallo Yal,
... zunächst aber danke, dass Du Dich meiner spez. Problem annehmen wolltest.
- Mit "Nachbarschaft " ist gemeint: für Ergebnis-Datenwert z,B. in C7: "vorgelagert" der in C6 und "nachgelagert der in C8. Und das gilt so für jeden Zellenwert in C4:C##
- Im Original sind es immer die ersten 5 Zeichen aus den Bezeichnungen in Spalte A die übereinstimmend sein müssen/können. Im Beispiel ist das vereinfachend dargestellt, da wären natürlich zwei Zeichen völlig ausreichend. Im Original würden lediglich 2 Zeichen zu anderen "Mengen-"Verhältnissen der unterschiedlichen Objektbezeichnungen führen.
- Die Prüfanzahl 5 in Y4 kannst Du nachvollziehen, wenn Du Dir die Inhalte der Zellen C76:C80 ansiehst, welche allein mit der Formel 4 "Nachbarschaften" ergibt (wovon natürlich 2 doppelt sind) die "5. Nachbarschaft" ist im Beispiel in C84:C85
- Die Prüfergebniswerte unterhalb der Diagonale sind auch ("gespiegelt") die gleichen wie oberhalb. Da war ich bei der Definition einer meiner bedingten Formatierung unsauber. Das die Werte gleich sind, wird besser ersichtlich, wenn ich die bedingte 2. Formatierungsformel (für "rötlich" hinterlegt) korrekt wie folgt definiert hätte: =($M4=N$3)*(N4&gt0)*($M4"")*(N$3"")+((N4&gt=N$2)+(N4&gt=INDEX($N$2:$AZ$2;ZEILE()-3)))*(N4"")
Ich hoffe, dass mein Anliegen nun besser verständlich ist.
Gruß Werner
.. , - ...
Anzeige
Einige Ideen
06.06.2021 18:24:35
Yal
Hallo Werner,
Ich glaube nicht, dass es sich mit PQ einfach lösen lässt. Ich fürchte sogar, dass das Problem NP-complete ist. Es ist ein Graph-Algorithmus. Ich könnte aber keine ähnliche Problemstellung finden. Ich habe auch keine Lösung parat, nur ein paar Anhaltspunkten, die helfen könnten, eine Lösung näher zu kommen.
Vokabel:
die 5 ersten Zeichen bilden den Familienname und somit einen Knoten. Jede familie hat dementsprechend ein oder mehreren Mitglieder. Es werden nur die mögliche Verbindungen zwischen Familien betrachtet. Die möglichen Verbindungen zwischen diesen Familien bildet ein voll vermaschten Netz ( https://de.wikipedia.org/wiki/Vermaschtes_Netz ). Jede Familie hat "Anzahl Familien minus eins" mögliche Verbindungen zu den anderen Familien. Also bei 3 Familien, 3 Verbindungen, bei 4 -> 6, bei 5-> 10, usw. Immer n(n-1)/2.
Ziel ist es, diesen Graph vollständig durchzulaufen ("traversieren"), in dem jeden Konten je nach Anzahl der Mitglieder besucht werden, die Verbindung maximal einmal (oder minimiert) verwendet werden. Bei jedem Besuch einer Familie wird ein Mitglied an der Kette angebunden und der Anzahl an Mitglieder um eins reduziert. Ist das Anzahl an restliche Mitglied in einer Familie null, so kann diesen Knoten rausgenommen werden. Er darf nicht mehr besucht werden. Innerhalb der Ergebnis-Kette sind die Mitglieder einer Familie beliebig miteinander austauschbar, ohne dass das Ergebnis sich ändert.
Es ist ähnlich wie die Fragestellung der Brucken von Koenigsberg ( https://de.wikipedia.org/wiki/K%C3%B6nigsberger_Br%C3%BCckenproblem ), was der Ursprung der Graph-Theorie bildet. Nur dass hier nicht jeder Brücke mindestens einmal verwendet werden muss.
Grenzen:
um einen Mitglied in der Kette anzubinden, wird immer 2 Verbindungen verbraucht: "zu" der Familie und "von" der Familie raus. Also hat die Familie mehr Mitglied als "Anzahl Familien minus eins" durch 2, wird es "rote Zellen" geben: einige Verbindungen müssen zweimal verwendet werden.
Da die Anzahl an Verbindungen "von und zu" einer Familie "Anzahl Familien minus eins" ist, hast Du eine ungerade Anzahl an Verbindungen, wenn die Anzahl an Familien gerade ist. Es führt dazu, dass jedes Knoten ist potentielle "Sackgasse" bildet (Siehe https://de.wikipedia.org/wiki/Haus_vom_Nikolaus ). Es ist aber nur ein Problem, wenn die Anzahl an Mitglieder von mehreren Familien den (n-1)/2 nah stehen. Insgesamt sind auf den grossen Familien zu achten.
Auf Grund diese beiden Beschränkung, sollte man, in Fall einer gerade Anzahl an Familien, mit einer, die nur einen Mitglied hat, anfangen (oder abschliessen): dann ist diesen Knoten aus nachfolgenden Bearbeitung raus (und auch die Verbindungen dazu). Die Anzahl an restlichen Knoten ist dann ungerade und die Anzahl an Verbindung gerade.
Haben wiederum mehrere Familien nur einen Mitglied, sollen diesen "früh" in der Verarbeitung einbezogen werden. Eine gangbare Lösung scheint (wenn auch nicht begründet), immer abwechselnd eine "kleine" Familie mit einer "grossen" Familie zu verketten.
Nun:
wie bearbeitet man die Fragestellung ab? Ich stelle mir eine Liste von "Familien" vor. Je nach gerade/ungerade erst die grösste Familie oder eine ein-Mitglied-Familie, dann abwechselnd gross/klein-Familien.
Beim ersten Lauf wird in einser Schritt "besucht und angebunden". Beim zweiten in zweier Schritt, Beim dritten 3er, usw. Wobei hier nicht berücksichtigt wird, dass ein Familie mit null verfügbare Mitglieder rausgenommen werden sollte.
Beim Schritten > 1, die Liste als "rund" beachten: der letzte Eintrag ist der Eintrag vor dem ersten Antrag. 2er Schritt auf ABCD ergibt ACBD, bei 3er ADCB. Problem gibt es, wenn die Liste genau ein Mehrfach vom Schritt hat: ABCD in 4er? AA!
Auf deinen Ergebnisse bin ich gespannt.
VG
Yal
Anzeige
AW: an deren Realisierung ich scheidere ...
06.06.2021 20:06:50
neopa
Hallo Yal,
... vorab meinen herzlichen Dank Dir, dass Du Dich so sehr mit meinem Problem auseinandergesetzt und Deine Gedanken dazu so ausführlich dargelegt hast. :-)
Von Graphentheorie habe ich zum ersten vernommen und konnte mir darüber erst einmal in Wikipedia einen nur völlig unvollständigen ersten verschwommenen Einblick verschaffen. Möglicherweise hab ich es nicht richtig verstanden, aber ich meine/denke, das was ich suche, ist nicht das verbindende sondern das trennende von "Familien". In meinem konkreten durch das einsortieren von anderen "Familien" (wie Du es bezeichnet hast) zur Trennung und Vermeidung neue "Bindungen"
Auch "NP" war mir bisher völlig unbekannt. Das meine Problemstellung höchstwahrscheinlich nicht komplett lösbar ist, glaubte ich schon mit den von mir vorgetragenen eingeschränkten Bedingungen im Eröffnungsbeitrag zum Ausdruck gebracht zu haben. Mein Ziel ist nach wie vor nur eine "Lösung", welche mit vertretbaren Aufwand, algorithmisch mit Excel-Funktionalität realisierbar ist und womit sich eine möglichst sichtbare Verbesserung meiner bisherigen "Lösung" ergibt. Ich wäre also schon zufrieden, wenn sich wenigstens keine rötlich hinterlegten Prüfzellen mehr ergeben und nur einige wenige gelb hinterlegte Zellen noch stehen bleiben. Wenn dem so sein sollte, dann betrachte ich es schon als gut "optimiert".
Das was Du mit "Abwechslung groß/klein" angeben hattest, hatte ich schon versucht zu realisieren. Dies führte aber dazu dass ich dann bei in etwa "mittelgroßen Familien" verstärktes Auftreten von ungewollten "Nachbarschaften" hatte. Ich will allerdings nicht ausschließen, dass mir da Fehler unterlaufen sein könnten.
Meine momentane Lösung basiert darauf, dass ich versucht habe, einen "Abstand von möglichst mind. 1" zwischen 2 "Familien" mit in etwa gleichstarken "Familien" zu bringen. Das geht aber offensichtlich auch nur bis zu einem gewissen Punkt (ca 80 - 90% der Gesamtanzahl), dann musste ich wenigsten dafür Sorge tragen, dass meine zwingende 1. Bedingung eingehalten wird.
Nun, ich werde die kommende Woche noch mal einen Anlauf versuchen. Vielleicht aber hat ja Rudi oder eine Anderer noch eine Idee.
Dir aber noch einmal mein Danke für Deinen Beitrag und wünsche einen guten Start in die neue Woche.
Gruß Werner
.. , - ...
Anzeige
AW: an deren Realisierung ich scheidere ...
07.06.2021 11:37:51
Yal
Hallo Werner,
ich hoffe, ich habe Dich mit meine Überlegungen nicht durcheinander gebracht. Aber ich sehe auch, dass Du viele der Punkten bereits entdeckt und probiert hattest.
Nur zur Ergänzung: das Verbinden hat nur das Ziel weitere Verbindung zu blockieren. Spricht, da ein Element kann nur 2 Nachbar haben kann (ausser Starter und Schliesser nur einen), wird durch die Verlinkung zu 2 Nachbarn, die die Bedingungen erfüllen, vermieden, dass Nachbarn dazukommen, die die bedingung nicht erfüllen. Also wenn B bereit A und C als Nachbar hat, kann D nicht mehr in direkte Nachbarschaft von B sein.
Die Verwendung der Graph und dessen "möglichen Verbindungen" ist nur ein Start-Gerüst. Wobei es auch dazu führt, dass man sofort prüfen kann, ob die 1. Bedingung erfüllt werden kann oder nicht (grösste Familie >= (Anzahl Familie -1) / 2. Nach und nach reduziert sich die Anzahl an mögliche Verbindung bis nur eine Verindung zu dem Schluss-Element besteht.
Ich gebe zu, wenn man sich noch nie mit Graphen beschäftigt hat, ist es ein Bischen befremdlich. Ich habe folgende Seite entdeckt ( https://www.orauh.de/excel-vba/animationen/eulertour/ ), die zwar nicht unseren Problem löst, aber das Thema Graph und traversieren anschaulich darstellt. Noch dazu mit "etwas in Excel".
Vielleicht nehme ich mir diese Woche Zeit, um eine Realisierung anzugehen. Das Thema finde ich interessant. Ich möchte eine Idee prüfen: man müsste jede mögliche Verbindungen gewichten, um "Verbindung zu bevorzügen" zu erzeugen, um dann ein Shortest Path Algorithmus verwenden.
VG
Yal
Anzeige
AW: das ist für mich eine "andere Welt" ...
07.06.2021 12:58:55
neopa
Hallo Yal,
... denn ich hatte keine Informatikausbildung, beschäftigte (hobbymäßig) mich nur seit vielen Jahren ausschließlich mit Excelstandardfunktionalitäten (überwiegend mit Formellösungen, erst seit ca. 2 Jahren ab und zu mal mit PQ ) nicht aber mit VBA.
Mir ging es mit der von mir im thread dargestellten Problem ähnlich wie scheinbar Dir jetzt. Ich hatte einem Bekannten zugesagt, sein spez. Problem zu lösen. Er war und ist mit meiner aufgezeigten Lösung auch zufrieden. Nur ich selbst nicht.
Ich bin mir zwar sicher, wie bereits geschrieben, dass es hierfür keine Ideallösung gibt, aber ich meine nach wie vor, es müsste auch mit Excel eine günstigere Lösung geben, eine die weniger "gleiche Berührungsstellen" zwischen den einzelnen "Familien" ergibt, als wie von mir bisher ausgewiesen.
Wenn Dich mein Problem nun auch interessiert, freut das mich das insofern, dass ich nicht weiter nur m eigenen Saft schmore. Ich hätte aber natürlich volles Verständnis, wenn Du später evtl. zur Meinung gelangen solltest, dass Aufwand und Nutzen für Dich nicht mehr in einem vertretbaren Verhältnis steht. Ich bin Dir so oder so schon jetzt dankbar, dass Du Dich meiner Problematik überhaupt angenommen hast und jetzt gespannt, zu welcher Erkenntnis Du gelangst.
Gruß Werner
.. , - ...
Anzeige
AW: siehst Du noch eine Realisierungschance? ...
11.06.2021 17:03:17
neopa
Hallo Yal,
... ich hatte mich noch 3 mal damit beschäftigt mit jeweils schlechteren Ergebnis als bisher erreicht und aufgezeigt. Ich lasse es jedenfalls jetzt erst einmal liegen bzw. gebe mich mit dem erreichten zunächst zufrieden. Vielleicht beschäftige ich mich zu einer späteren Zeit damit noch einmal.
Wünsche ein schönes WE
Gruß Werner
.. , - ...
wenn Werner was fragt, ...
05.06.2021 22:08:26
Rudi
... geht's ihm wahrscheinlich so, wie wenn ich mal was frage. ;-)
PQ kann ich nicht, verstehe ich (momentan noch) nicht. Ich beschäftige mich sporadisch damit. VBA ist aber(( für mich) (noch)) erheblich einfacher.
Gruß
Rudi
Anzeige
AW: eine VBA_Lösung hierfür ...
06.06.2021 09:16:51
neopa
Hallo Rudi,
... wäre mir vielleicht auch schon hilfreich. Dies deswegen, als dass daraus für mich zumindest ersichtlich wäre, wie weit man sich dem ideal möglichen Zielergebnis nähern kann. Und wenn mir dann dazu noch die realisierte Strategie der VB Lösung verbal kurz beschrieben wird, könnte ich versuchen, diese mit einer Formellösung (mit PQ könnte ich es auf keinen Fall, denn da stecke ich selbst auch noch in den Kinderschuhen) annähernd umzusetzen.
Gruß Werner
.. , - ...

Beliebteste Forumthreads (12 Monate)

Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige
Anzeige
Anzeige