Matematické Fórum

zajca · 03. 03. 2012 15:03

Zdravím,
potřeboval bych help. Snažím se popsat něco jako sudoku pomocí minimalizace ILP. Tak abych upravil data pro solver, který to vyřeší, ale nějak jsem se zasekl.
Mám nějaké vstupní data, kde mám dimezi matice a nějaká pravidla: jako třeba prvek matice x13 > x9 nebo prvek x7 = 1;
Klasicky nemůžu mít v jednom slouci nebo řádku dvě stejná čísla a to je můj problém jak tady to přepsat pro ILP.příklad řeším pomocí lp_solve.

lp_solve samozřejmě nezná nonekvivalenci takže nemůžu zadat x1 != x2.

může mi někdo pomoct?
můj lp soubor pro lp_solve

Code:

/*minimalizovaná funkce je součet všech prvků*/
min: x1 + x2 + x3 +x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13 + x14 + x15 + x16;
/*omezení na sloupce a řadky*/
x1 + x2 + x3 + x4 = 10;
x5 + x6 + x7 + x8 = 10;
x9 + x10 + x11 + x12 = 10;
x13 + x14 + x15 + x16 = 10;
x1 + x5 + x9 + x13 = 10;
x2 + x6 + x10 + x14 = 10;
x3 + x7 + x11 + x15 = 10;
x4 + x8 + x12 + x16 = 10;
/*další omezení*/
x13 - x9 >= 1;
x2 - x6 >= 1;
x12 - x8 >= 1;
x16 = 2;
x7 = 1;
/*omezení velikosti proměnné*/
1 <= x1 <= 4;
1 <= x2 <= 4;
1 <= x3 <= 4;
1 <= x4 <= 4;
1 <= x5 <= 4;
1 <= x6 <= 4;
1 <= x7 <= 4;
1 <= x8 <= 4;
1 <= x9 <= 4;
1 <= x10 <= 4;
1 <= x11 <= 4;
1 <= x12 <= 4;
1 <= x13 <= 4;
1 <= x14 <= 4;
1 <= x15 <= 4;
1 <= x16 <= 4;
/*celočíselné prvky*/
int x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16;

Sulfan · 04. 03. 2012 14:51 — Editoval Sulfan (04. 03. 2012 14:52)

↑ zajca: Je nutné si vytvořit binární proměnnou, která bude říkat, jestli je na dané pozici (x,y) prvek s hodnotou c, kde $c= 1,2,3,4$ . Potom se udělá jednoduchá podmínka na součet, že se v každém sloupci (řádku) bude vyskytovat ta číslice právě jednou.

Pěkně je to vysvětlené v této bakalářské práci na straně 17. Je zde naformulován celý matematický problém dokonce pro sudoku 9x9.

zajca · 04. 03. 2012 16:01

↑ Sulfan:
no jo, ale jak to popsat tak aby to přežvýkal lp_solve, nenašel sem v dokumentaci nic jako if or nebo něco použitelného pro tento případ.

zajca · 09. 03. 2012 20:57

tak vyřešeno:
pokud to někoho bude zajímat tak v LP_solve to jde popsat takto

x0 - x1 + n*c0 >= 1;
x1 - x0 + n*c1 >= 1;
0 <= c0 <= 1;
0 <= c1 <= 1;
c0 + c1 = 1;

koeficient "n" je vlastně maximální hodnota pokud tedy máme prvky 1,2,3,4 tak je to 4.

a do poslendího řádku s int: taky přidat tyto proměnné aby měli opravdu hodnotu 0 1

na popsaní matice 4x4 je třeba těchto proměnných 96 na 8x8 896

kdyby někdo chtěl program co jsem řešil, můžu mu ho poslat je to asi 500řádků v ruby. Co do efektivnosti nic moc :D

Matematické Fórum

#1 03. 03. 2012 15:03

Sudoku popsané jako problém celočíselného lineárního programování

Code:

#2 04. 03. 2012 14:51 — Editoval Sulfan (04. 03. 2012 14:52)

Re: Sudoku popsané jako problém celočíselného lineárního programování

#3 04. 03. 2012 16:01

Re: Sudoku popsané jako problém celočíselného lineárního programování

#4 09. 03. 2012 20:57

Re: Sudoku popsané jako problém celočíselného lineárního programování

Zápatí