Hallo, kennt ihr eine Möglichkeit, wie ich eine Anzahl Rechtecke (variabel, z.b. 15) aus einer vorgegebenen Anordnung (variabel, z.B. wie im Anhang) auswählen kann, bei denen die ausgewählten Felder maximalen Abstand zu den jeweiligen Nachbarn haben? Ich habe schon versucht mit ForNext -Schleifen mit den Mittelpunkten der Rechtecke Abstandsberechnungen (Pythagoras) durchzuführen, komme aber nicht zum gewünschten Ergebnis. Meist befinden sich alle am äußeren Rand verteilt oder alle auf einer Seite.. VG korax
Angehängte Dateien:
-
Rechtecke.png
4,1 KB
Der Abstand zu einem Nachbar ist doch immer 0. Oder was meinst du mit "Abstand" und "Nachbar"?
Angehängte Dateien:
-
Rechtecke2.png
4,4 KB
Nun ja, Abstände der Mittelpunkte. Wenn 15 Rechtecke von 50 ausgewählt werden, bleiben auch nichtausgewählte dazwischen.
Fra N. schrieb: > Nun ja, Abstände der Mittelpunkte. Wenn 15 Rechtecke von 50 ausgewählt > werden, bleiben auch nichtausgewählte dazwischen. Ist noch immer nicht klar. Bei 15 Rechtecken hat jedes 14 Abstände. Solle Summe der Summen dieser Abstände maximal werden, oder die Summe der Abstände des "nächsten" Nachbars? So oder so dürfte das eine "schwierige" Aufgabe sein.
Anders formuliert. Ich möchte aus 50 Rechtecken 15 auswählen, welche gut verteilt sind (wie in Bild Rechtecke2.png) Mein Ansatz war: 1. ein "Start"-Rechteck festlegen (z.B. in der Mitte) 2. alle möglichen Rechtecke "abklappern" d.h. Die Abstände des Mittelpunkts zum vorher ausgewählten (in der Mitte) ermitteln und das mit dem größten Abstand auswählen (zwangsläufig ist das dann eins am Rand. 3. Wiederholen von 2. aber jetzt muss ich zwei schon ausgewählte Rechtecke berücksichtigen und zu denen einen größtmöglichen Abstand des Mittelpunkts wahren. 4. Immer wiederholen bis die vorgegebene Anzahl (hier 15) erreicht ist. Meine Annahme ist, daß erst am Rand die gewählt werden bis deren Abstände kleiner werden als Mitte-Rand; dann werden welche aus dem "mittleren Bereich" ausgewählt... Ergebnis sollte dann eine Ansicht wie in Bild Rechtecke2.png ergeben. Gruß korax
Patrick schrieb: > > Einen Versuch hast du noch. Danach bist du durchgefallen. OK. Ich möchte mittels eines Algorithmus (Ich brauch nur Denkanstöße, proggen kann ich selbst 'n bisschen) von mit Linien umrahmten weißen Flächen wie in Bild "Rechtecke.png" einige einfärben, die nicht aneinandergeklatscht sind sondern gleichmäßig voneinander entfernt (wie in Bild "Rechtecke2.png"). Die Anzahl und vorgegebene Anordnung der vorhandenen ist von Mal zu Mal anders und die Anzahl der auszuwählenden ist u.U. variabel. Mein Progrämmchen soll halt Vorschläge zur Auswahl unterbreiten. Ich denke aber, Du nimmst mich nur auf die Schippe.. VG
Fra N. schrieb: > Patrick schrieb: >> >> Einen Versuch hast du noch. Danach bist du durchgefallen. > > OK. > > Ich möchte mittels eines Algorithmus (Ich brauch nur Denkanstöße, > proggen kann ich selbst 'n bisschen) von mit Linien umrahmten weißen > Flächen wie in Bild "Rechtecke.png" einige einfärben, die nicht > aneinandergeklatscht sind sondern gleichmäßig voneinander entfernt (wie > in Bild "Rechtecke2.png"). > > Die Anzahl und vorgegebene Anordnung der vorhandenen ist von Mal zu Mal > anders und die Anzahl der auszuwählenden ist u.U. variabel. Mein > Progrämmchen soll halt Vorschläge zur Auswahl unterbreiten. > > Ich denke aber, Du nimmst mich nur auf die Schippe.. > > VG nimm eine zweite farbe! wähle ein rechteck zufällig aus, färbe das ein, färbe die nachbarfelder die frei bleiben sollen mit der zweiten farbe. ad nauseam. wenn alle platziert sind (so sich das ausgeht) die zweite farbe wieder entfärben.
> gleichmäßig voneinander entfernt
Willst du die gleichmäßigste Lösung berechnen oder nur irgendeine
halbwegs verteilte?
Bei 15 von 50 hast du 2,94 *10^24 Möglichkeiten. (50*49*48...*36).
Dauert ewig.
Eine einfache Lösung wäre: 100 Versuche, in denen die Felder vollkommen
zufällig besetzt werden. Und von den 100 zufälligen die gleichmäßigste
auswählen.
Das ist nicht so trivial lösbar, ausser vieleicht ein Brute force Ansatz. Siehe für ein ähnliches Problem das VBierfarben Problem: https://de.wikipedia.org/wiki/Vier-Farben-Satz https://people.math.ethz.ch/~cbusch/pspdf/Mathetag_busch.pdf ... Als erstes solltest du dir eine Metrik für Fra N. schrieb: > sondern gleichmäßig voneinander entfernt definieren. Wie gewichtest du das? wie berechnest du das? Bevor du das nicht hast brauchst du nicht an die Lösung gehen. Fra N. schrieb: > proggen kann ich selbst 'n bisschen Das nützt dir nichts wenn du keinen Algorithmus hast.
Der Andere schrieb: > VBierfarben Sorry ich habe aber noch nichts getrunken :-) Sollte natürlich "Vierfarbenproblem" heissen.
Patrick schrieb im Beitrag #4536781: > Denken kannst du nicht. Ich denke, daran liegt's nicht. Das die beispielhafte Verteilung nicht gleichmäßig ist ist mir klar. Geht auch nicht (nur in einem Sonderfall). Ein so gleichmäßig wie möglich (oder sinnvoll erreichbar - Rechenzeit) reicht natürlich. Patrick schrieb im Beitrag #4536781: > nicht einmal dein Problem formulieren Ich dachte, der Unterschied zwischen den beiden Bildern ist halbwegs klar. Patrick schrieb im Beitrag #4536781: > Also kannst du auch > nicht denken, dass dich jemand auf die Schippe nimmt. Da hab' ich wohl falsch gedacht. Trotzdem viele Grüße, korax
Noch einer schrieb: > Eine einfache Lösung wäre: 100 Versuche, in denen die Felder vollkommen > zufällig besetzt werden. Und von den 100 zufälligen die gleichmäßigste > auswählen. Alternativ: erst mal zufällig 15 Rechtecke auswählen. Dann in einer Schleife zufällig eines davon auswählen, und überprüfen, ob man durch Verschieben (d.h., Tausch mit einem leeren Nachbarn) die Situation verbessern kann.
Hm. Schau mal ob Dich ein Voroni-Diagramm https://de.m.wikipedia.org/wiki/Voronoi-Diagramm oder Delaunay-Triangulierung https://de.m.wikipedia.org/wiki/Delaunay-Triangulierung weiterbringen. Eine andere Lösung könnten quad- bzw. R-Trees sein. Die nimmt man um den nächste Nachbarn zu finden. Du willst ja das Gegenteil, aber der Ansatz könnte klappen wenn man den inversen Abstand nimmt.
Carl Friedrich schrieb im Beitrag #4537491: > Studier Mathematik, ... aber zumindest > sinnvoll formulieren. So einen Aufwand wollte ich nicht treiben.. Ich verstehe nicht, was an: Fra N. schrieb: > maximalen Abstand zu > den jeweiligen Nachbarn Fra N. schrieb: > gleichmäßig voneinander entfernt unverständlich sein soll. Das das zweite Bild nicht das Optimum ist, ist mir klar - das habe ich nur in Paint gemalt!
Fra N. schrieb: > Carl Friedrich schrieb: >> Studier Mathematik, ... aber zumindest >> sinnvoll formulieren. > > So einen Aufwand wollte ich nicht treiben.. Brauchst du ja auch gar nicht. Aber dann beschäftige dich doch nicht mit Dingen, von denen du nichts verstehst. Oder fragst du auch bei schweren Krankheiten in irgendwelchen Foren, wie man sie behandelt, weil du es nicht hinbekommst, einem Arzt zu erklären, welche Beschwerden du hast, und weil es dir zu aufwändig ist, selbst Medizin zu studieren? > > Ich verstehe nichts Siehst du, genau das ist das Problem.
rmu schrieb: > nimm eine zweite farbe! > > wähle ein rechteck zufällig aus, färbe das ein, färbe die nachbarfelder > die frei bleiben sollen mit der zweiten farbe. ad nauseam. > > wenn alle platziert sind (so sich das ausgeht) die zweite farbe wieder > entfärben. Dieser Ansatz erscheint mir vielversprechend. Als Start wuerde ich zwei Rechtecke mit maximalem Abstand auswaehlen (falls das zu aufwaendig ist, zwei mit nur grossem Abstand). Von allen bereits gewaehlten Rechtecken faerbt man die Nachbarn ein. Das ergibt eine wellenartige Ausbreitung. Die/das Rechteck, das als letztes eingefaerbt wird hat den groessten Abstand zu den anderen, usw. Mit verschiedenen Definitionen fuer den Abstand und die Nachbarn kann man etwas experimentieren. Im einfachsten Fall ist einfach das angrenzende Rechteck ein Nachbar mit Abstand 1. Erinnert ein bisschen an den Lee Algorithmus. Jetzt kann man noch versuchen zu beweisen, dass der Algorithmus die Greedy Eigenschaften besitzt und dann wuerde er sogar zur optimalen Loesung fuehren.
Angehängte Dateien:
-
sonicht.png
1010 Bytes
Ihr könnt hier noch lange rum labern, aber so lange Frank nicht weiß, was er will, ist ihm nicht zu helfen. Zur Klarstellung hänge ich im Anhang ein Beispiel für eine Lösung einer 4-in-10-Feldern-Konfiguration an. Frank wird sicherlich behaupten, dieses sei keine Lösung. Dann möchte ich mal wissen, welches dieser Kriterien nicht erfüllt ist: Fra N. schrieb: > auswählen kann, bei denen die ausgewählten Felder maximalen Abstand zu > den jeweiligen Nachbarn haben? Johann L. schrieb: > Der Abstand zu einem Nachbar ist doch immer 0. Oder was meinst du mit > "Abstand" und "Nachbar"? Fra N. schrieb: > Nun ja, Abstände der Mittelpunkte. Wenn 15 Rechtecke von 50 ausgewählt > werden, bleiben auch nichtausgewählte dazwischen.
Patrick schrieb: > Dann möchte ich mal wissen, welches dieser > Kriterien nicht erfüllt ist Heureka, er hat's! Bei Deinem Beispiel mit den seeehr schmalen Rechtecken sieht's halt so aus: Es "klatschen" Rechtecke aneinander. Die Fra N. schrieb: > Abstände der Mittelpunkte. sind in Deinem Beispiel (ich habs nicht nachgemessen ;o)) maximal. Das ist das, was ich suche. Meine Rechtecke werden nicht so extrem sein nur Verhältnis 1:1 bis 2:3. Da sollte sich ein Bild wie mir vorschwebt entstehen. Könntest Du noch ein, zwei Rechtecke in Deiner 2x11-Matrix dazu rechnen? Und wichtiger: Wie ist dein Ansatz zu dieser Verteilung? VG korax
Fra N. schrieb: > Ich verstehe nicht, was an: > > Fra N. schrieb: >> maximalen Abstand zu den jeweiligen Nachbarn [...] > > unverständlich sein soll. Das heißt nichts anderes, als dass du folgendes Optimierungsproblem lösen willst
wobei Ri bzw. Rj die Mittelpunkte der Rechtecke durchlaufen. Nehmen wir als Beispiel mal ein 3×3 Raster, in dessen Ecken sich bereits 4 mit "1" markierte Rechtecke befinden:
1 | 1.1 |
2 | ... |
3 | 1.1 |
und wir wollen ein weiteres R hinzufügen. Der Unterschied in der Metrik hängt dann nur von der Platzierung des 5. R ab. Bei Platzierung in der Mitte
1 | 1.1 |
2 | .1. |
3 | 1.1 |
wächst die Metrik um 4·√2≈5.65. Platzieren wir das 5. R jedoch ebenfalls in einer Ecke
1 | 2.1 |
2 | ... |
3 | 1.1 |
dann wächst die Metrik sogar um 2+2+√8≈6.83! Die doppelte Platzierung in der Ecke widerspricht zwar einer Nebenbedingung zur Konstruktion, aber das Problem bleibt bei einer Verfeinerung des Rasters unter Einhaltung der Nebenbedingung bestehen! Nimm zum Beispiel ein Raster 101×101 mir Rs in (0,0), (0,100), (100,0) und (100,100). Das 5. R in (1,1) zu platzieren ist besser, als es in (50,50) zu platzieren. Anstatt der Summe der Abstände die Abstandsquadrate zu nehmen behebt das Problem nicht : 2²+2²+√8² = 16 > 8 = 4·√2²
...eine funktionierende Formulierung basiert auf einem physikalischen System geladener Teilchen, die sich so anordnen, dass sich ihre potentielle Energie minimiert
Es soll aber auf Position (50,50), weil es da den größten Abstand zum jeweiligen Nachbarn hat.
Johann L. schrieb: > dass sich ihre > potentielle Energie minimiert Genau! Sie stoßen sich ab und halten einen größtmöglichen Abstand.
Fra N. schrieb: > Heureka, er hat's! > > Bei Deinem Beispiel mit den seeehr schmalen Rechtecken sieht's halt so > aus: Es "klatschen" Rechtecke aneinander. Die Was denn nun? Ist das die Lösung, also ist es erlaubt, dass aneinandergeklatschte Rechtecke markiert werden? Wenn ja, geht es tatsächlich nur um die Entfernungen der Mittelpunkte, und das ganze Gelabere von Rechtecken hätte man sich sparen können. Du suchst also n aus m Punkten im zweidimensionalen (oder vielleicht doch dreidimensionalen?) Raum, die "maximalen" Abstand voneinander haben. Was heißt maximaler Abstand für eine Punktewolke? Soll der minimale Abstand aller Paare maximiert werden? (Das kann mehrdeutig sein.) Soll die Summe der Abstände von jedem Punkt zum nächsten Nachbarn maximiert werden? Die Summe der Quadrate? Die Summe der Abstände aller Punktepaare? Die Summe der Quadrate der Abstände aller Punktepaare? Man kann noch unendlich viele andere Maße für das Optimierungsproblem definieren, von denen viele in Abhängigkeit von der Fragestellung sinnvoll sein können. Aber die Fragestellung scheinst du ja geheimhalten zu wollen.
Patrick schrieb: > Wenn ja, geht es > tatsächlich nur um die Entfernungen der Mittelpunkte, und das ganze > Gelabere von Rechtecken hätte man sich sparen können Die Rechtecke dienen der Verdeutlichung des Rasters, der vorgegebenen möglichen Positionen. Patrick schrieb: > Soll der minimale Abstand aller Paare maximiert werden? (Das kann > mehrdeutig sein.) Das war meine ursprüngliche Idee. Fra N. schrieb: > proggen kann ich selbst 'n bisschen macht mir noch Probleme bei der Umsetzung. Das: Johann L. schrieb: > dass sich ihre > potentielle Energie minimiert trifft den Nagel uffen Kopp.
Fra N. schrieb: > Patrick schrieb: >> Soll der minimale Abstand aller Paare maximiert werden? (Das kann >> mehrdeutig sein.) > > Das war meine ursprüngliche Idee. Das ist total billig zu lösen. Das kriegst sogar du hin. Obwohl... meinen Arsch würde ich darauf nicht verwetten... genauer genommen, gar nichts verwette ich darauf... Du bekommst das nicht hin, sorry, dass ich mich korrigieren muss.
Fra N. schrieb: > Es soll aber auf Position (50,50), weil es da den größten Abstand zum > jeweiligen Nachbarn hat. Wie ist "Nachbar" definiert? Un bei Platzierung in der Mitte verringern sich die Abstände aller Eck-Rechtecke. Es muss also eine Regel geben, wie sich diese Verringerung der Abstände auf die Metrik auswirken soll. Ansonsten ist das Ergebnis von der Reihenfolge der Platzierungen abhängig. Als praktikablen Ansatz würde ich das Energie-basierte Modell vorschlagen: 1) Platziere die Rs zufällig so dass die Kanten-Bedingung erfüllt ist 2) Verschiebe ein zufällig gewähltes R auf einen Nachbarplatz 3) Falls die Energie des Systems dadurch zunimmt oder die K-Bedingung verletzt wird, mache 2) rückgängig 4) Gehe nach 2) Als Verbesserung kann noch eine Temperatur T eingeführt werden. https://en.wikipedia.org/wiki/Simulated_annealing Abhängig von der Temperatur sind dann auch Konfigurationsänderungen erlaubt, welche die Energie des Systems nicht mehr als einen bestimmten Betrag erhöhen bzw. mit einer bestimmten, von T abhängigen Wahrscheinlichkeit sind Energieerhöhungen eines bestimmten Betrages erlaubt: Die Simulation startet mit hoher Temperatur, die im Laufe des Verfahrens gesenkt wird. Ziel ist, nicht in einem lokalen Minima gefangen zu werden. Physikalisches Vorbild sind Phasenübergänge. Die Kanten-Bedingung wirkt dabei ziemlich unnatürlich, also unphysikalisch, was weitere Probleme erwarten lässt: Es wird schwerer, sich aus einem lokalen Minimum zu befreien, weil Energieniveaus in der Nähe durch die K-Bedingung verboten sind. Außerdem ist nicht klar, ob überhaupt eine Lösung existiert, welche der K-Bedingung genügt, und selbst wenn, kann es sehr uznwahrscheinlich sein, überhaupt eine Startkonfiguration gemäß 1) zu finden. Man könnte versucht sein, einfach K-verletzende Konfigurationen zuzulassen und sich das letzte, gültige Layout merken. Wenn es eng wird auf dem Brett werden Layouts, die der K-Bedingung genügen, jedoch extrem unwahrscheinlich. Vielleicht hilft ein weiteres physikalisches Phänomen, nämlich der Tunneleffekt bei der Modellierung.
:
Bearbeitet durch User
Angehängte Dateien:
-
Rechtecke3.png
4,5 KB
Patrick schrieb: > Das kriegst sogar du hin Anbei meine bisherigen Erfolge. Eine Häufung auf der linken Seite ist zu erkennen. Das liegt daran, das ich die Spalten von links und die Zeilen von unten "abklappere" und während der Schleife gleiche Ergebnisse ermittelt werden aber nicht zu einer Aktualisierung führen - Es "gewinnt" also der erste Treffer. Das muss ich noch ausmerzen.
Johann L. schrieb: > Als praktikablen Ansatz würde ich das Energie-basierte Modell > vorschlagen: Mal den Ball flach halten. Das Problem ist mit Franks Erklärung Fra N. schrieb: >> Soll der minimale Abstand aller Paare maximiert werden? (Das kann >> mehrdeutig sein.) > > Das war meine ursprüngliche Idee. gelöst. Bzw. ist gar kein Problem mehr. Er kann nur das Ergebnis nicht umsetzen: Fra N. schrieb: >> proggen kann ich selbst 'n bisschen > macht mir noch Probleme bei der Umsetzung. Fra N. schrieb: > Eine Häufung auf der linken Seite ist zu > erkennen. So what? Die Qualität der Lösung ist dieselbe wie die ursprüngliche - der minimale Abstand ist \sqrt(w^2+h^2), wenn w und h die Kantenlängen der Rechtecke sind. Besser wird es nicht bei 15 auszuwählenden Punkten im gegebenen Beispiel. Also spar dir das weitere rumjammern.
Backtracking und Simulated Annealing etc. dürfte viel zu kompliziert sein für jemanden der das Problem nicht exakt formulieren kann. Eine (einfache) Methode, die funktionieren könnte: man nummeriere die Felder von der Mitte ausgehend spiralförmig der Reihe nach, platziere die Farbklekse in den Feldern (immmer Anzahl farbige / Anzahl Felder Abstand lassen), und geht in einem zweiten Schritt drüber und repariert die "Zusammenklatscher".
Patrick schrieb: > Also spar dir das weitere rumjammern. Na gut. Ich danke allen für die Vorschläge und werde noch weiter "frickeln". Patrick schrieb: >> Ich verstehe nichts > > Siehst du, genau das ist das Problem. das "s" gebe ich Dir zurück. Nicht, das es woanders dann fehlt.
Josef schrieb: > rmu schrieb: >> nimm eine zweite farbe! >> >> wähle ein rechteck zufällig aus, färbe das ein, färbe die nachbarfelder >> die frei bleiben sollen mit der zweiten farbe. ad nauseam. >> >> wenn alle platziert sind (so sich das ausgeht) die zweite farbe wieder >> entfärben. > > Dieser Ansatz erscheint mir vielversprechend. > > Als Start wuerde ich zwei Rechtecke mit maximalem Abstand auswaehlen > (falls das zu aufwaendig ist, zwei mit nur grossem Abstand). > > Von allen bereits gewaehlten Rechtecken faerbt man die Nachbarn ein. Das > ergibt eine wellenartige Ausbreitung. > Die/das Rechteck, das als letztes eingefaerbt wird hat den groessten > Abstand zu den anderen, usw. > > Mit verschiedenen Definitionen fuer den Abstand und die Nachbarn kann > man > etwas experimentieren. Im einfachsten Fall ist einfach das angrenzende > Rechteck ein Nachbar mit Abstand 1. > > Erinnert ein bisschen an den Lee Algorithmus. > > Jetzt kann man noch versuchen zu beweisen, dass der Algorithmus die > Greedy Eigenschaften besitzt und dann wuerde er sogar zur optimalen > Loesung > fuehren. ok, Greedy Eigenschaften sind nicht erfuellt. Damit erreicht man durch Faerben/Wellenausbreitung nicht unbedingt die beste Loesung. @Patrick: Selten so jemand Unfreundlichen erlebt.
Angehängte Dateien:
-
Rechtecke4.PNG
603 Bytes -
Rechtecke5.PNG
479 Bytes
Hi folks, Wer verteilt denn hier die "Minusse"? Egal, ich habe jetzt eine Optimierung eingebaut, die, wenn sie ein neues Rechteck hinzugefügt hat, der Reihe nach vorhandene wieder löscht und neu anordnet. Damit halten die Rechtecke immer den größtmöglichen Abstand zueinander. Eine Iteration von 5 reicht da schon und es kommt folgendes raus (siehe Anhang). Da die Anordnung der Rechtecke nicht immer symmetrisch ist, kommen manchmal nicht (für mich) optimale Verteilungen heraus. Ist vom Ansatz her etwas Außenlastig. Für Patrick auch die schmale Variante ;o)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.