« Sammanfattning av Bloggareträff uti Malmö, söndagen 4 maj 2008 | Main | MiniZinc/FlatZinc version 0.8 släppt »
maj 26, 2008
Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem
Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.
Samtliga modeller att tilnå finns via My MiniZinc page.
Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.
En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.
I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".
Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.
SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.
För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).
A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).
Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.
Några Operations Research-problem
I John Hooker:s föreläsning A framework for integrating optimization and constraint programming finns några OR-problem som imlementerats:
- freight_transfer.mzn
- product_configuration.mzn
Ett skoj fotbollspussel
I Yahoo!-gruppen lp_solve kom ett skoj problem. Tyvärr krävs inloggning till gruppen, så MiniZinc-modellen innehåller hela meddelandet.
Problemet (som är en knapsack-variant) går ut på att optimera köp av brittiska fotbollsspelare med vissa krav:
- budgeten är på 30 miljoner (pund)
- man måste köpa ett visst antal spelare (målvakt, försvarsspelare etc) för en given kostnad per spelare
- man ska maximera den totala kostnaden men inte komma över budgeten.
Problemet uttrycks i flyttal men jag har valt att arbeta med heltal av två skäl:
- för tillfället är det fler MiniZinc-solvers som klarar av helttal än flyttal
- när det gäller spelarkostnader är inte orimligt att anta hela pund.
MiniZinc-modellen finns i football.mzn och är ganska generell.
Några andra modeller
- Funktionspartitionering, dvs partionera ett gäng heltal med avseende på en funktion t.ex. modulo-funktionen: modulo_partition.mzn. Det är enkelt att ändra funktion i modellen.
- Beslutsträd. Här modelleras ett fullständigt binärt beslutsträd: decision_tree_binary.mzn.
- Markovkedjor: markov_chains.mzn: Här räknar man ut "stable state" av marknadsandelnarna för tre företagsmärken.
- Yet another recreational schackproblem: peacableArmyOfQueens.mzn.
Raymond Smullyans logiska pyssel
Så till det jag satt med i helgen.
I den underbara boken What is the name of this book? beskriver Raymond Smullyan ett stort antal logiska pyssel, de allra flesta är skapade av Smullyan själv.
Några av de mest kända pysslen från denna bok är "Knights and Knaves"-problemen från kapitel 3 (som heter just "Knights and Knaves"): Alla "knights" talar alltid sanning och alla "knaves" ljuger alltid. Senare i kapitlet kommer även "Normals" med, sådan ljuger ibland och talar sanning ibland, och så tillkommer speciella giftasregler mellan de olika typerna. Problemet är att försöka lista ut vem som är vad med ledtråd av några få ledtrådar.
De allra flesta problemen från kapitel 3 finns modellerade i respektive modell:
- smullyan_knight_knaves.mzn: bara knights och knaves
. Problem 26 till och med 35. (Problem 36, 37 och 38 har av olika skäl inte modellerats.)
- smullyan_knight_knaves_normals.mzn: här finns även normals
. Problem 39 till och med 42 (modellen för 43 är inte korrekt).
- smullyan_knight_knaves_normals_bahava.mzn, med speciella giftoregler mellan knights, knaves och normals. Problem 44, 45 och 46.
Wikipedia har mer info om Knights and Knaves.
Uppdatering något senare
Några fler problem från samma bok:
- De första problemen om Lion och Unicorn från kapitel 4 "Alice in the Forest of Forgetfulness": smullyan_lion_and_unicorn.mzn. Lejon och enhörningar ljuger vissa dagar och talar sanning andra dagar. Här gäller det att lista ut vilken dag de säger olika saker.
- De första problemen från kapitel 5 "The mystery of Portias Caskets" smullyan_portia.mzn.
Posted by hakank at maj 26, 2008 06:54 EM Posted to Constraint Programming | Pyssel