Algoritmus Distribution in einer Matrix

[Smokers]

Also ich habe folgendes Problem.

Ich habe eine Matrix mit A x B Feldern. Dann habe ich eine Zahl k. Ich möchte dann k Positionen im Feld belgen undzwar so, das möglichst alle belegten Felder soweit wie möglich voneinander entfernt sind.

Habt ihr da eine Idee oder gibts da ein Stichwort?

lg schonmal und danke

 

[Simon_Flagg]

ein fall von rekursion denk ich....

lg

 

[Smokers]

mhh könntest du das noch ein wenig ausführen?
also als rekursion kenne ich fakultätsberechnungen etc, aber soetwas? wüsste nicht wie ich das gerade in ein rekursives schema reinpressen könnte :-/

 

[Simon_Flagg]

vllt. so:
positioniere ersten punkt
positioniere zweiten punkt, wenn nicht möglich, weil irgendeine distanz zu klein oder zu groß ist --> gehe zurück zum ersten punkt und positioniere den neu.... (im prinzip wie 8damenproblem....)

lg

 

[Marco13]

Man könnte da evtl. auch eine Iteration drüberlaufen lassen. (Also nicht "iterativ programmieren" als Gegenstück zu rekursiv, sondern eine Iteration...). GANZ Grob im Pseudocode

Setze die k Elemente auf die Indizes 0...k-1 der Matrix
while (smokersBreak) // :D 
{
    x = Index des Feldes der Matrix, dessen minimale Entfernung zu
        einem der belegten Felder maximal ist
    y = Ein "geeigneter"* Index eines belegten Feldes
    Bewege Element von y nach x
}

*"geeignet" könnte dann irgendwas sein wie "der Index des Elementes, das zum Schwerpunkt der anderen die kleinste Entfernung hat" (oder so, müßte man sich mal überlegen...)

Also, das klingt ziemlich unfundiert und ins Blaue, aber ist so eine Idee in Anlehnung an solche Dinge wie Laplacian smoothing - Wikipedia, the free encyclopedia ...

Zumindest haben solche Ansätze den Vorteil, dass sie vergleichsweise trivial sind im Vergleich zu einer geschlossen hingeschriebenen optimalen Lösung - da würde ich jetzt spontan sagen, dass das irgendwie nach einem Optimierungsproblem klingt, wo man, wenn man's drauf anlegt, auch mit ILP/Simplex & Co drangehen könnte.

Ich schätze, dass man mit einer guten Heuristik für die anfängliche Verteilung (anders als die im Pseudocode) und ein paar Iterationen schon gute Lösungen bekommen könnte, und vielleicht sogar schneller bessere, als den (ab einer bestimmten Matrixgröße ohnehin fast aussichtslosen) versuch, DIE Optimiale Lösung deterministisch auszurechnen...

Wenn man nicht von einer Matrix redet, sondern von einer Ebene, findet man bestimmt auch mehr dazu im Web.

 

[kay73]

Klar ist, dass Dein Problem viele Lösungen hat und DEN deterministischen Ansatz zu DER optimalen Lösung sehe ich nicht. Je nachdem ob es Dir den (Rechen-)Aufwand wert ist, könntest Du einen einfachen evolutionären Ansatz probieren. Er gibt nicht notwendigerweise eine optimale, aber garantiert eine "gute" Lösung. Grundidee ist, Mengen von Lösungskandidaten in mehreren Phasen zu bewerten, immer die Beste(n) auszuwählen, die Kind-Lösungskandidaten zu mutieren (und/oder zu kreuzen), bis eine Abbruchbedingung erfüllt ist.

Nehmen wir an, die k Punkte haben ganzzahlige Koordinaten und der Abstand zum Rand spielt keine Rolle. Alle Zahlen, die folgen, kannst Du problemlos anpassen.

1.) Bilde eine Anfangspopulation von 10 Lösungskadidaten: Jeder Lösungskandidat ist eine Liste mit k Punkten mit zufälligen Koordinaten.

2.) Jedem Lösungskandidaten wird eine Güte zugeordnet. Hier die Summe aller existieren Abstände: Für jeden Punkt summierst Du die Abstände zu allen anderen Punkten in der Liste. Das ist zwar eine quadratische Laufzeit, aber Du kannst z. B. die simple Manhattan-Metrik wälhen (nur die Koordinaten subtrahieren und die Absolutwerte addieren).

3.) Wähle die besten 3 Lösungskandidaten (- d. h. die mit der höchsten Summe aus 2.) -) und kopiere diese sooft, bis Du wieder eine Poplation von 10 neuen/alten Lösungskandidaten hast.

4.) Iteriere über alle 7*k Punkte der neuen Lösungskandidaten und mutiere jeden mit der Wahrscheinlichkeit 1%: Wenn ein Punkt mutiert wird, bedeutet das, ihn ein BISSCHEN wegzuschubsen, also z. B. mit Warhscheinlichkeit 1/2 den Wert 1 von seiner x- oder y-Koordinate abzuziehen oder addieren. (Wichtig ist, dass hier "behutsam" vorgegangen wird, "kleine" Werte nehmen und mit geringen Wahrscheinlichkeiten arbteiten)

5.) Gehe zurück zu Schritt 2.

Mach das Ganze so lange, bis eine Abbruchbedingung greift: Das kann eine maximale Anzahl evolutionärer Zyklen sein und/oder eine ausreichend geringe Änderung der besten Gütewerte.

Wenn man nach jedem Zyklus den besten Lösungskandidaten in eine Bitmap malt, gibt das bestimmt ein witziges Filmchen.

Es gibt noch Dutzende Varianten, wie man mit den Populationen umgehen kann; eine davon ist der Crossover, in dem man Individuen kreuzt, hier zufällig Koordinaten tauscht. Aber das Verfahren von oben sollte schon so einigermaßen klappen.

 

[Smokers]

Also die Ansätze hier gefallen mir schonmal,..
Auch die Lösung von kay, ich werd die als alternative Möglichkeit mit anbieten oder versuchen umzusetzen.Auch wenn diese eine hohe Laufzeit hat und wahrscheinlich schwerer zu realisieren sein wird.

Die primitivste Weise mit der ich zZ rangehe ist :

int std=6;
		
		int rows = 5;
		int cols = 5;
		int [][] test = new int [rows][cols];
                int cspacing = (int) Math.round(Math.sqrt((rows*cols)/std));
		int rspacing = (int)(Math.sqrt((rows*cols)/std));
                
                int sit=0;
		for(int i = 0;i<rows;i++){
			for(int j=0;j<cols;j++){
				if(i%cspacing==0 && j%rspacing==0) {
					test[i][j]=1; 
					sit++;
					if(sit >= std){
						break;
					}
				}
			}
			if(sit >= std){
				break;
			}
		}
		
		
		for(int i = 0;i<rows;i++){
			for(int j=0;j<cols;j++){
				System.out.print(test[i][j]+"\t");
			}
			System.out.println();
		}

Also indem ich die Spalten und Zeilen als Fläche ansehe und gleichgroße Unterflächen bilde.
Jedoch folgt aus den Rundungen meistens verschwendeter Platz.

Vllt kann man auch auf der Schiene weiter überlegen.

 

[kay73]

Auch wenn diese eine hohe Laufzeit hat und

Wenn man 100 Studenten auf Plaetze verteilen will, gibt es (100 * (100+1))/2-1. verschiedene Abstaende ("Haendeschuetteln-auf-einer-Party"-Problem). Das sind pro Loesungskandidat je 5049 Integersubtraktionen und Additionen, bei einer Population von 10 Loesungskandidaten insgesamt 100980 Integeroperationen. Finde ich nicht soooo schlimm. Ausserdem ist das Parallelisieren trivial.

wahrscheinlich schwerer zu realisieren sein wird.

Vielleicht habe ich es auch nur schlecht beschrieben.

Deine Aufgabe schreit aber foermlich nach einem genetischen Algorithmus, denn gerade mit Randbedingungen kann er gut umgehen und ist leicht erweiterbar. Ein Loesungskandidat, bei dem ein Abstand von 1 auftritt (oder ein Mindestabstand verletzt wird) hat automatisch die Guete 0. Auch weitere Randbedingungen, wie z. B. "minimaler Abstand zur Wand moeglichst gross", damit die Klausuraufsicht alle leicht im Blick hat und die Studenten nicht spicken koennen, wenn sie an der Wand entlang zum Klo gehen sind ganz simpel einzubauen. Und wenn die Aufgabe nicht loesbar ist, z. B. weil mehr als die Haelfte der Plaetze besetzt sein wuerden, gibt es einfach keine Loesungskandidaten.


Wenn ich heute abend nicht zu platt bin, versuche ich es mal...