Springen naar inhoud

Lineaire programmering: schaakbordprobleem


  • Log in om te kunnen reageren

#1

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 19 oktober 2008 - 10:18

Probleem: Zet 8 koninginnen op een schaakbord, zodanig dat geen enkele koningin een andere koningin kan slaan.

Liefst zag ik dit opgelost met behulp van lineaire programmering.
Ik heb het volgende al bedacht:

Geplaatste afbeelding

waarbij xi,j = 1 als er een koningin staat in de i-de rij, in de j-de kolom van het schaakbord met i,j in {1,...,8}.

De eerste beperking legt op dat er exact 8 koninginnen op het bord moeten staan. De tweede beperking zegt dat er maar ťťn koningin per rij mag. De derde zegt hetzelfde, maar dan voor kolommen. Het enige wat ik nu nog moet modelleren is dat koninginnen niet op dezelfde diagonaal mogen staan, maar ik weet niet precies hoe ik dat moet aanpakken.
Be careful whose advice you buy, but be patient with those who supply it.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Burgie

    Burgie


  • >250 berichten
  • 582 berichten
  • Ervaren gebruiker

Geplaatst op 19 oktober 2008 - 11:25

Even een kleine opmerking... Jouw laatste 2 ongelijkheden, daar zou ik gelijkheden van maken. Er moet immers in elke rij en elke kolom ZEKER ťťn koningin staan.

Straks denk ik wel eens over het 2de deel van het probleem (als ik wat meer tijd heb).

#3

Burgie

    Burgie


  • >250 berichten
  • 582 berichten
  • Ervaren gebruiker

Geplaatst op 19 oktober 2008 - 12:04

Ik bedacht me net dat dit een standaardprobleem is, en dat ik het ook ooit heb moeten oplossen tijdens mijn studie. Aangezien ik niet met zekerheid weet wat jij precies wenst te bereiken (qua efficiŽntie van je oplossing), kan je misschien beter eerst zelf wat inspiratie opdoen uit volgende links:
http://en.wikipedia....t_queens_puzzle
http://en.wikipedia....uzzle_solutions

#4

raintjah

    raintjah


  • >250 berichten
  • 824 berichten
  • Ervaren gebruiker

Geplaatst op 19 oktober 2008 - 12:39

Even een kleine opmerking... Jouw laatste 2 ongelijkheden, daar zou ik gelijkheden van maken. Er moet immers in elke rij en elke kolom ZEKER ťťn koningin staan.

Straks denk ik wel eens over het 2de deel van het probleem (als ik wat meer tijd heb).


Akkoord. Maar dat maakt in principe dan niet uit, de solver zal er uiteindelijk dezelfde oplossing geven denk ik. Gelijkheden staan echter wel sierlijker. In deze vorm is het inderdaad een "toewijzingsprobleem" zie ik net, maar er moeten nog extra beperkingen bij.

Edit: van die oplossingenlink kan ik weinig opmaken. Dat zijn allemaal talen die ik niet spreek. Maar desalniettemin waren ze nuttig :D

Veranderd door raintjah, 19 oktober 2008 - 12:45

Be careful whose advice you buy, but be patient with those who supply it.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures