Hi !
Hat jemand eine Idee, wie man das Damenproblem
( wieviele Damen kann ich maximal auf ein n*n Schachbrett stellen, ohne, daß diese sich gegenseitig bedrohen)
per linearer Optimierung loesen kann ?
Ich meine wie saehen die Variablen aus, und was fuer Gleichungen oder Ungleichungen sind erforderlich ?
Richard
Hat jemand eine Idee, wie man das Damenproblem
( wieviele Damen kann ich maximal auf ein n*n Schachbrett
stellen, ohne, daß diese sich gegenseitig bedrohen)
per linearer Optimierung loesen kann ?
8x8 Felder, d.h. es koennen maximal 8 sein
(sonst wuerden ja zwei auf einer geraden Linien stehen).
Was die Diagonalen anbelangt, ich schaetze 5 ist das
Ergebnis. Man kann sich das so vorstellen: Mit 5 Damen
werden durch gerade Strecken alle bis auf 9 Felder
besetzt. Diese 9 (3x3) liegen jedoch auf den 5 Diagonalen
der 5 schon aufgestellt Damen.
MEB
Danke fuer Deine Bemuehungen.
Aber leider ist es nicht das, was ich brauche.
Zum einen geht es um ein n*n-Feld und zum anderen um einen Loesungsansatz per linearer Optimierung ( Simplex und so ) :)
Richard
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Danke fuer Deine Bemuehungen.
Aber leider ist es nicht das, was ich brauche.
Zum einen geht es um ein n*n-Feld und zum anderen um einen
Loesungsansatz per linearer Optimierung ( Simplex und so ) :)
Richard
Also: Nehme Variablen 1>=x(ij)>=0, x(ij))=1: Dame auf Feld ij, sonst nicht.
Zielfunktion maximiere sum_i,j x(ij)
Nebenbedingungen:
Zeilen: sum_i=1^n x(ij)=1 fuer alle j
Spalten sum_j=1^n x(ij)=1 fuer alle i
Diagonalen
sum_{i+j=c} x(ij)=1 fuer c=2...16
sum_(i-j)=c x(ij)=1 fuer c=-7,...,7
Ohne die Diagonalengleichungen ist das die Bedingung fuer stochastische Matritzen-> Polyeder hat ganzzahlige Ecken.
Ich wuerde tippen, dass das mit den DGs nicht mehr stimmt, dann
musst du das ganzzahlige Problem Loesen, was mit Limplex nicht geht. Dann nimm z.B. branch&bound.
Um evtl zu zeigen, dass das Teil doch ganzzahlig ist, kanst Du versuchen die Diagonalgleichungen in die Zielfunktion aufzunehmen.
MFG
Martin
Sorry, ich meine bei den Nebenbedingungen natuerlich <=1.
(kleiner gleich, nicht gleich.)
MFGML
Sorry, ich meine bei den Nebenbedingungen natuerlich <=1.
(kleiner gleich, nicht gleich.)
MFGML
Also so richtig check ich das noch nicht was Du da schreibst, aber ich bin auch keine Fachmann und Du hast bestimmt Recht : )
Ich werd mich da noch reinhaengen.
THX MFGRN
Hi,
der mathematische Teil wurde ja schon hinreichend geklärt. Nur von mir mal die praktische Info, daß die Lösung 8 lautet. Wobei DIE Lösung falsch ist, es gibt nämlich etliche davon. Ich habe irgendwann in der 7ten Klassen mal ein Progrämmchen zum Thema geschrieben. Es basierte auf einer Rekursivfunktion, d.h. es war auf jedenfall eine Routine drin, die prüfte, ob sich die Damen bedrohten. Da ich kein 5 1/4 Zoll-Laufwerk mehr habe, kann ich Dir (wahrscheinlich) den Quellcode nicht mehr liefern. Wenn Du ein entsprechendes Laufwerk hast, kann ich Dir die Disks gern zuschicken.
Gruß
Christian
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi Richard :)))
Das Damenproblem hat bei einem 8*8-Brett genau 92 Lösungen. Programmiertechnisch kannst du das mit Backtracking leicht herausfinden. Eine lineare Optimierung ist hingegen nicht möglich, weil die Damen nicht unabhängig voneinander aufgestellt werden können. Mit anderen Worten, es kann keine lineare Funktion geben, die du maximieren könntest. Wenn du dich für die 92 Lösungen interessierst, schicke ich dir gerne ein kleines Progrämmchen per Mail :)))
cu Stefan.
Eine lineare Optimierung ist hingegen nicht
möglich, weil die Damen nicht unabhängig voneinander
aufgestellt werden können.
Was meinst du mit unabhaengig ?
Wenn man das Problem nimmt, 8 Tuerme aufzustellen, so sind die
auch nicht unabhaengig, aber das Polyeder das rauskommt ist gerade das, das von den Permutationsmatritzen aufgespannt wird und die Nebenbedingungsmatrix ist halt total unimodular-> Lineare
Optimierung liefert ganzzahlige Loesungen.
Beim damenproblem geht das m.E. nicht, da ich vermute, dass die
Diagonal-Nebenbedingungen das kaputt machen.
MFG
Martin
Hi Leute !
Vielen Dank fuer Eure Bemuehungen.
Haette nicht gedacht, daß soviele Antworten kommen.
Morgen muß ich die Loesung abgeben : )
Richard