Damenbrett

[Janus]

Hallo...hab wieder ein Beispiel gelöst bin mir aber nicht sicher ob das so wirklich stimmt...könnt ihr meine Lösung wieder anschauen...danke....

Gegeben ist ein Damenbrett mit n*n Feldern. Die Felder können leer oder mit einem weißen oder schwarzen Stein belegt sein. Der Inhalt eines Feldes wird durch den folgenden Datentyp beschrieben:
type Field = (empty,white,black)
Gesucht ist ein Algorithmus, der das Brett zufällig mit w weißwn und b schwarzen Steinen belegt, wie das folgende Beispiel für n = 5, b = 4 und w = 5 zeigt.


Gefragt ist nach der asymptotischen Laufzeitkomplexität im ungünstigsten Fall in Abhängigkeit von n.

Code:

placeCheckers(Field[n,n] board, int n,int b,int w){
board[0:n-1,0:n-1] = empty // alle Felder auf empty setzen ...n²

while(b>0){
x=smallRand(n)
y=smallRand(n)
if(board[x,y]==empty){
board[x,y] = black
b=b-1
}
}

while(w>0){
x=smallRand(n)
y=smallRand(n)
if(board[x,y]==empty){
board[x,y] = white
w=w-1
}
}
}

So und jetzt soll ich einen Code finden der ein besseres Laufzeitverhalten aufweißt. Ich hab mir gedacht dass ich mir einfach den Codeteil spare wo alle Felder auf empty gesetzt werden. Ersparung von n² Schleifendurchläufen in der Laufzeit.
Ich gehe also jedes Feld einzeln durch und belege es per Zufallszahlengenerator entweder mit empty, white oder black

Code:

placeCheckers(Field[n,n] board, int n,int b,int w){
int help
int empty1 = n²-(w+b)

for(int i = 0; i < board.length;i++){
for(int j = 0; j <board[o].length;j++){
help = smallRand(3) //Zufallszahlengenerator
if(help == 0){
if(empty1 != 0){
board[i,j] = empty
empty1--;
}else{
if(b != 0){
board[i,j] = black
b--;
}else{
board[i,j] = white
w--;
}
}
}

if(help == 1){
if(b != 0){
board[i,j] = black
b--;
}else{
if(w != 0){
board[i,j] = white
w--;
}else{
board[i,j] = empty
empty1--;
}
}
}

if(help == 2){
if(w != 0){
board[i,j] = white
w--;
}else{
if(b != 0){
board[i,j] = black
b--;
}else{
board[i,j] = empty
empty1--;
}
}
}
}
}
}

mfg,
Janus

[DarkTom]

Mach dich mal bitte mit der Verwendung von Code-tags vertraut.


Zu deiner Lösung:
1. Du beantwortest die Frage nach der Laufzeitkomplexität nicht.
2. Eine Verringerung um n² Operationen bringt komplexitätsmäßig nur etwas, wenn der restliche Code nicht >= c*n² Schritte macht, was deiner aber tut (und auch jede Lösung tun muss, da ja jedes der n² Felder gesetzt werden muss). .
3. Dein Code verteilt die Steine nicht gleichmäßig (zufällig), sondern verstärkt an den "Anfang" des Brettes. Die "vorderen" Felder haben ja alle eine 1/3 Chance, mit einem Stein bestimmter Farbe besetzt zu werden.
4. Zu deiner Beruhigung: Dein Algorithmus kommt im worst case tatsächlich besser weg, als die angegebene Vorgehensweise. Aber das gilt für jeden Algorithmus im strengeren Sinne der Definition.

Ich würde das wohl mit 0 Punkten bewerten.

[Janus]

Hallo...ok war wirklich unübersichtlich...aber wie schaffe ich eine Gleichverteilung? Hast du eine bessere Lösung wo eine bessere Laufzeitkomplexität als O(n²) rauskommt?
Kannst du mir einen Tipp geben wie ich bei jedem Feld eine Gleichverteilung schaffe?

Hab mir die Lösung zu dem Beispiel angeschaut(irgendwann machts keinen Spaß mehr im Dunkeln zu tappen)...kapier aber nicht warum hier Gleichverteilung herrscht:


placeCheckers(Field[n,n] board, int n,int b,int w){

int x,y,i,j,e,k

e = n*n-w-b

for(x=1...n){
for(y=1...n){
i = smallRand(b)
j = smallRand(w)
k = smallRand(e)

if((i>=j)&&(i>=k)&&(b>0)){
board[x,y] = black
b=b-1
}
else{
if((j>=i)&&(j>=k)&&(w>0)){
board[x,y] = white
w=w-1
}
else{
if((k>=i)&&(k>=j)&&(e>0)){
board[x,y] = empty
e=e-1
}
}
}
}
}
}


Kannst du mir bitte etwas genauer erklären warum bei meinem Code keine Gleichverteilung herrscht?

mfg,
Janus

[DarkTom]

Nochmal: Besser als quadratisch geht nicht, da du jedes der n² Felder setzen musst. Der ursprünglich angegebene Code terminiert im worst case gar nicht. (Da wird dann immer ein Feld erwürfelt, das schon besetzt ist). Darum ist theoretisch alles, was beweisbar terminiert, besser. :D


Bei einer Gleichverteilung würde ja für jedes Feld gelten, dass dort mit einer Wahrscheinlichkeit von (b über n²) ein schwarzer Stein ist, bei dir ist diese Wahrscheinlichkeit aber schon für das erste betrachtete Feld 1/3.


Die Gleichverteilung in der Lösung ist für mich auch nicht auf den ersten Blick ersichtlich. Ich habe sogar den Verdacht, dass auch hier keine besteht, wenn sie auch besser angenähert ist.
(Btw, an alle Mitleser, der Lösungscode ist auch irreführend eingerückt, nicht davon verwirren lassen. Das zweite else bezieht sich auf das if innerhalb des ersten else-Blocks.)

*denk*

Ach ja, so geht's:
Ich nehme mal an, smallRand(n) generiert eine Zahl z mit 0<=z<=n.
Betrachten wir den Fall, dass der Algorithmus alle bis auf die letzten zwei Felder gesetzt hat und noch jeweils ein weisser und ein schwarzer Stein übrig sind (w=1, b=1). Jetzt sollte das vorletzte Feld mit 50% Wahrscheinlichkeit mit einem schwarzen Stein besetzt werden.

Schauen wir uns die vier möglichen Würfelergebnisse an:
i=0, j=0 => schwarzer Stein
i=0, j=1 => weisser Stein
i=1, j=0 => schwarzer Stein
i=1, j=1 => schwarzer Stein

Also: Mit einer Wahrscheinlichkeit von 75% wird das vorletzte Feld in dieser Situation mit einem schwarzen Srtein besetzt.
Ergo: Keine echte Gleichverteilung.
q.e.d

Von wem stammt die angebliche Lösung eigentlich?




Es gibt aber einige ersichtlichere (und richtige) Lösungen. Mit die einfachste wäre wohl die folgende:
1. Tue alle weissen, schwarzen und neutralen Steine in einen Beutel. (Die neutralen markieren leere Felder.)
2. Ziehe für jedes Feld einen Stein aus dem Beutel.

Als Code
Gegeben: b, w, n

int steineImBeutel = n*n;
for (int x=1..n) {
for (int y=1..n) {

//Stein ziehen
int stein = rand(steineImBeutel); //rand generiert 0<stein<=steineImBeutel
steineImBeutel--;

if (stein <= b) {
//stein ist schwarz
board[x, y] = schwarz;
b--;
}
else if (stein <= b+w) {
//stein ist weiss
board[x, y] = weiss;
w--;
}
else {
//stein ist neutral
board[x, y] = leer;
}
}
}


Eine andere Alternative wäre, ähnlich dem ursprünglichen Code vorzugehen, und dafür zu sorgen, dass keine Position zweimal gewürfelt werden kann. Das ist aber etwas umständlicher

[Janus]

Hallo...die Lösung habe ich einfach von einem Kellegen der auf diese Übung alle Punkte bekommen hat.

Bei einer Gleichverteilung würde ja für jedes Feld gelten, dass dort mit einer Wahrscheinlichkeit von (b über n²) ein schwarzer Stein ist, bei dir ist diese Wahrscheinlichkeit aber schon für das erste betrachtete Feld 1/3.

Wahrscheinlichkeit ist offenbar nicht gerade meine große Stärke deshalb fällt es für mich auch so schwer das Ganze zu kapieren. Wieso b/n² ?

Bei Gleichverteilung muss doch gelten dass in jedem beliebigen Feld entweder ein schwarzer Stein liegt 1/3 oder ein weißer Stein liegt 1/3 oder es leer ist 1/3....also:1/3+1/3+1/3 = 1...falsch
Ich durchschau deine Denkweiße nicht in der Wahrscheinlichkeit...könntest du mir bitte deinen Anschauung verdeutlichen?

mfg,
Janus

[Janus]

Hab nochmal in alten Schulaunterlagen gestöbert und jetzt kapier ich das mit der Wahrscheinlichkeit....

mfg,
Janus

[Janus]

Hallo...aha...

Bsp.:

n=3, b=2,w=1

Dann gilt bei Gelichverteilung beim ersten ausgewählten Feld: Mit einer Wahrscheinlichkeit von 2/9 wird ein schwarzes Feld belegt,
mit einer Wahrscheinlichkeit von 1/9 wird ein weißes Feld belegt,
mit einer Wahrscheinlichkeit von 6/9 wird ein leeres Feld belegt.
Ergibt zusammen 9/9 also 100%.
2/9 für schwarz ergibt bsp. 22.22.. % von 100% insgesamt....usw.
Jetzt wählst du beim ersten Mal eine gleichverteilte Zufallszahl zwischen 1...9. Falls 1,2...schwarz,3...weiß,4-9...leer.
Beim 2ten Mal verändern sich natürlich die Wahrscheinlichkeiten wieder da nur mehr 8 Felder zur Verfügung stehen......also: wenn schwarz ausgewählt wurde...1/8...schwarz, 1/8...weiß,6/8.....leer.
..usw.

mfg,
Janus

[Jan Krüger]

Die Gleichverteilung musst du etwas anders auffassen.

Hier ein paar Definitionen:
P(Wi) ^= Wahrscheinlichkeit, dass Feld i mit einem weißen Stein belegt ist
P(Bi) ^= W', dass Feld i mit einem schwarzen Stein belegt ist
P(Li) ^= W', dass Feld i leer ist
Mangels mathematischer Symbole werde ich "+" für Vereinigung, "*" für Schnitt und "^C" für Komplement benutzen.

Angenommen, du hast ein 5x5-Feld und sollst 4 schwarze und 5 weiße Steine setzen. Für jedes Feld ist P(Wi) = 5/25 = 1/5; P(Bi) = 4/25; P(Li) = (25-5-4)/25 = 16/25. Gleichverteilung bedeutet also: die Wahrscheinlichkeit, dass ein Feld eine bestimmte Belegung kriegt, ist unabhängig von der Position des Felds; NICHT, dass die Wahrscheinlichkeit für jede Belegung gleich ist. Denn es sollen ja mehr weiße als schwarze Steine und vor allem viel mehr leere Felder als belegte vorkommen... bei einer Wahrscheinlichkeit von je 1/3 wird das fast sicher nicht passieren.

Dein zweiter Algorithmus beachtet allerdings die Position; er fängt beim ersten Feld an und weist ihm mit einer Wahrscheinlichkeit von je 1/3 schwarz, weiß oder leer zu. Das stimmt gleich doppelt nicht, denn zum einen sind diese Wahrscheinlichkeiten falsch (siehe oben), und zum anderen wäre es auch mit den richtigen Wahrscheinlichkeiten nur "am wahrscheinlichsten", dass eine korrekte Lösung rauskommt. Kleines Beispiel: du hast vier Felder und sollst eins davon mit weiß belegen und die anderen leer lassen , d.h. P(Wi) = 1/4. Du erledigst die Belegung, indem du für jedes Feld einen entsprechenden Zufallswert von 0 bis 3 erzeugst und das Feld belegst, wenn er z.B. 0 ist. Dann ist aber die Wahrscheinlichkeit, dass 0 mehr als einmal auftaucht, etwa 0,74. In diesem sehr häufigen Fall musst du also eine der beiden Nullen ignorieren, und schon ist die Gleichverteilung im Eimer.

Der erste Algorithmus ist leider auch nicht ganz korrekt. Da du die Positionierung jedes einzelnen Steins gleichverteilt über alle Felder machst, kommt die Gleichverteilung durcheinander: wenn du einen Stein auf einem Feld positionieren willst, das schon belegt ist, musst du die nächste Zahl auswürfeln. Richtig wäre, nach jeder Belegung die Menge der Felder, zwischen denen gewürfelt wird, um diejenigen zu reduzieren, die schon belegt sind. Ob dabei eine Gleichverteilung im ursprünglichen Sinne rauskommt, möchte ich allerdings gerade auch nicht nachrechnen. ;)

Übrigens: die Zahl der möglichen Konfigurationen des Bretts ist n²!/(w! b! (n²-w-b)!), also im obigen 5x5-Fall 257.414.850.

Meine Lösung in Pseudocode:
N = Breite/Höhe des Bretts
B = Zu setzende schwarze Steine
W = Zu setzende weiße Steine
L = (N^2 - B - W)
I = N
brett = { 0 => leer, 1 => leer, ..., N => leer }
for (position = 0 bis N) {
P = rand(0 bis I)
if (P < B) { brett[position] = schwarz; B -= 1 }
else if (P - B < W) { brett[position] = weiß; W -=1 }
else { brett[position] = leer; L -= 1}
I -= 1
}

[Janus]

Hallo...die Lösung von DarkTom stimmt doch oder?

Kleines Beispiel: du hast vier Felder und sollst eins davon mit weiß belegen und die anderen leer lassen , d.h. P(Wi) = 1/4. Du erledigst die Belegung, indem du für jedes Feld einen entsprechenden Zufallswert von 0 bis 3 erzeugst und das Feld belegst, wenn er z.B. 0 ist. Dann ist aber die Wahrscheinlichkeit, dass 0 mehr als einmal auftaucht, etwa 0,74. In diesem sehr häufigen Fall musst du also eine der beiden Nullen ignorieren, und schon ist die Gleichverteilung im Eimer.

Wie kommst du auf den Wert 0.74 ?
Mir ist jetzt klar dass es so nicht gehen kann aber mich würde trotzdem gerne interressieren wie du auf den Wert kommst,

mfg,
Janus

[Jan Krüger]

Die Lösung von DarkTom ist korrekt und stimmt im Wesentlichen mit meiner überein; meine ist nur etwas algorithmischer formuliert.

Den Wert 0,74 kann man so ausrechnen: die Wahrscheinlichkeit für weiß ist pro Feld 1/4. Die Wahrscheinlichkeit, dass kein Feld weiß wird, ist (1 - 1/4)^4; die Wahrscheinlichkeit, dass genau ein Feld weiß wird, ist 4 * (1/4 * (1 - 1/4)^3) (einmal weiß und dreimal nicht, in vier verschiedenen Anordnungen). Macht also für alles außer 0x oder 1x weiß: 1 - ((3/4)^4 + 4 * (1/4 * (3/4)^3)) ~ 1 - (0,32 * 4 * 0,11) ~ 1 - (0,74) ~ 0,26. Und das, was ich vorher gesagt hab, war falsch. :rolleyes:

[DarkTom]

Der erste Algorithmus ist leider auch nicht ganz korrekt. Da du die Positionierung jedes einzelnen Steins gleichverteilt über alle Felder machst, kommt die Gleichverteilung durcheinander: wenn du einen Stein auf einem Feld positionieren willst, das schon belegt ist, musst du die nächste Zahl auswürfeln. Richtig wäre, nach jeder Belegung die Menge der Felder, zwischen denen gewürfelt wird, um diejenigen zu reduzieren, die schon belegt sind. Ob dabei eine Gleichverteilung im ursprünglichen Sinne rauskommt, möchte ich allerdings gerade auch nicht nachrechnen. ;)Bist du wirklich der Meinung, dass die Gleichverteilung dadurch verloren geht, dass du bestimmte der (gleichverteilten) Zufallswerte des Zufallsgenerators verwirfst?

Folgendes Argument:
Denk dir einen Wahrscheinlichkeitsbaum. An der Wurzel und jedem inneren Knoten hängen n Kinder mit den Werten von 1 bis n. Knoten mit Wert kleiner n sind Blätter. Ein Knoten mit Wert n ist ein innerer Knoten. (Dies modelliert etwa die benutzte Vorgehensweise.) Jetzt gilt, dass für jede Tiefe t des Baumes die Anzahl der Blätter in Tiefen <=t für alle Werte 1..n-1 gleich ist.

Ich weiss, das Argument ist nicht 100% akkurat und ich lasse mich auch gerne eines besseren belehren. :)


Btw, Jan Krüger, in deinem Pseudocode benutzt du N sowohl als Breite des Bretts als auch als Anzahl der Positionen. Du meintest wohlN = Breite/Höhe des Bretts
B = Zu setzende schwarze Steine
W = Zu setzende weiße Steine
L = (N^2 - B - W)
I = N^2
brett = { 0 => leer, 1 => leer, ..., N^2 => leer }
for (position = 0 bis N^2) {
P = rand(0 bis I)
if (P < B) { brett[position] = schwarz; B -= 1 }
else if (P - B < W) { brett[position] = weiß; W -=1 }
else { brett[position] = leer; L -= 1}
I -= 1
}

[Firefall]

Nachdem was ich bisher verstanden habe ist das beste Prinzip zufälligen generierten Feldern ihre Steine zuzuweisen, und solche die bereits belegt überspringt. Das Problem liegt darin das nicht alle Zufallszahlen verwendet werden können. Ein Lösungsansatz wäre eine endlose Schleife zu durchlaufen die alle Steine setzt und wenn das generierte Feld bereits einen Stein aufweist, ganz von vorne zu beginnen. Diese Methode potenziert sich natürlich mit der Anzahl Steine und "wurzelt" sich mit der Anzahl Felder. Erscheint mir aber als die beste Lösung wenn die zuvor genannte nicht akzeptiert wird.

[Janus]

Hallo...hab mir jetzt das Ganze wieder nach einiger Zeit angeschaut und mir is es klar geworden...danke...

mfg,
Janus