Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 02. 06. 2014 20:43 — Editoval p4too (03. 06. 2014 21:37)

p4too
Příspěvky: 342
Reputace:   
 

diskretna optimalizacia/modelovanie a optimalizacia

Zdravim,
chcel by som spravit 'solver' pre hru flowgame. Problem mam s matematickym modelom...

popis hry:

Connect matching colors with pipe to create a flow. Pair all colors, and cover the entire board to solve each puzzle in Flow Free. But watch out, pipes will break if they cross or overlap!

screenshot:
http://www.html5games.net/wp-content/uploads/flow1.png

doterajsie riesenie:
Kazdej farbe by som priradil nieake cislo 1-zelena, 2-cervena ...
0 by bolo prazdne policko ....
premenne
$x_{i,j}$ policko i,j pouzita farba

ucelova funkcia by nebola
strukturalne podmienky:
$x_{i,j}>0$
$x_{2,2}=1$ ... tam kde su pevne zadane farby by som popriradoval cisla

a teraz neviem ako modelovat mozny pohyb, no iac menej sa dalej uz vobec neviem pohnut ...
myslite ze sa to vobec da nieako takto riesit ??

mam to riesit cez grafy skorej ??

dakujem za kazdu pomoc :)

Offline

 

#2 02. 08. 2014 11:45

FailED
Příspěvky: 1255
Reputace:   42 
 

Re: diskretna optimalizacia/modelovanie a optimalizacia

Ahoj,

někde jsem četl, že se umí dokázat, že je to těžké, takže to efektivně (polynomiálně) nikdo neumí.

Ke tvému modelu můžeš přidat
1) proměnné a podmínky kontrolující okolí každého čtverce (barevná čára spojuje čtverce stejné barvy, každým neterminálním čtvercem čára projde)

2) Proměnné a podmínky kontrolující souvislost barevných čar (mohlo by se stát, že dostaneš řešení s izolovanými cykly). Tohle se dá řešit tak, že si vybereš v každé barvě startovní políčko a pak budeš podle spojující čáry počítat vzdálenost od toho startovního políčka.

- Výsledná soustava nebude lineární program.
- Podobně by to šlo převést na SAT a nebo ILP, takže jestli máš k dispozici solver, můžeš to zkusit. Takové převody bývají hodně podobné, stačí se naučit pár triků. A asi by ti to pomohlo i s tvorbou modelu (hledej reduction to sat).
- Jestli může mít barva víc než 2 terminály, musel bys ve 2) postupně zkoušet všechny dvojice, které se mají spojit.


Řešit to backtrackingem na grafu bude názornější a můžeš využít strukturální vlastnosti té hry a podle toho ořezávat. (Třeba zastavíš výpočet, když si odřízneš terminály,...) Tak můžeš dostat i efektivnější algoritmus, solvery musí být obecné.

Offline

 

#3 02. 08. 2014 14:50

p4too
Příspěvky: 342
Reputace:   
 

Re: diskretna optimalizacia/modelovanie a optimalizacia

Dakujem za odpoved
Tak budem to riesit medotou grafov...
Napriklad kazdy jedeno policko/stvorec bude vrchol a medzi vsetkymi susednými vrcholmi budu hrany, cize ten graf bude mat vzdy rovnaku strukturu ....
http://forum.matematika.cz/upload3/img/2014-08/80679_a.png

Zadefinujem mnozinu vrcholov, ktore maju byt spojene.
to by bola inicializacia a algoritmus bude napr.

1.Pre kazdu dvojicu vrcholov vytvorim docasny podgraf tak, ze z povodneho odstanym vrcholi a hrany ktore idu z tych vrcholov ktore su v mnozine vrcholov, ktore maju byt spojene, okrem tych ktore hladam ...
1.1 V tom docasnom podgrafe najdem vsetky cesty, medzi tymi vrcholmi ktore hladam.
2. Zo vsetkych najdenych ciest budem kombinovat kym nenajdem taku kombinaciu, kde je kazdy vrchol pouzity prave raz ...


Uvediem na zjednodusenom priklade :
http://forum.matematika.cz/upload3/img/2014-08/82281_a1.png
mnozina vrcholov ktore maju byt spojene: {1,8,5,9}cize  {{1,8}; {5,9}}
Ten prvy sposob je jednoduchsi a aj potom sa vyuzije pri tom algoritme ... Proste mnozina bude mat vzdy parny pocet prvkou, ziadne sa nebudu opakovat a spojit sa budu mat i,i+1...

1.pre vrcholy 1,8
vytvorim podgraf z ktorho odstranym vrcholi {1,8,5,9}-{1,8}
http://forum.matematika.cz/upload3/img/2014-08/82794_a2.png
najdem cesty {{1,4};{4,7};{7,8}} tu je len jedna

2. pre vrcholy 5,9
http://forum.matematika.cz/upload3/img/2014-08/82965_a2.png
cesty su {{5,6};{6,9}}; {{5,2}, {2,3},{3,6},{6,9}}

3.kombinacia {{1,4};{4,7};{7,8}} a {{5,6};{6,9}} nevyhovuje lebo niesu pouzite vsetky vrcholy,
{{1,4};{4,7};{7,8}} a {{5,2}, {2,3},{3,6},{6,9}} je riesenie
http://forum.matematika.cz/upload3/img/2014-08/83286_a1.png

ak by to bolo 15x15 co je myslim max a bolo by tam malo farieb na spojenie cize obrovsky pocet kombinacii ciest bol

Offline

 

#4 02. 08. 2014 16:01 — Editoval FailED (02. 08. 2014 16:06)

FailED
Příspěvky: 1255
Reputace:   42 
 

Re: diskretna optimalizacia/modelovanie a optimalizacia

Přesně tak, těch cest může být opravdu hodně. Přitom budeš muset testovat spoustu nekompatibilních kombinací a hlavně si ty cesty pamatovat.

Paměť vyřešíš tím, že budeš generovat rovnou celé řešení (nějaký backtracking), na vylučování nekompatibilních kombinací můžeš vymýšlet heuristiky a vylučovat částečná řešení, o kterých umíš říct, že nejdou doplnit.

Offline

 

#5 17. 08. 2014 23:05

p4too
Příspěvky: 342
Reputace:   
 

Re: diskretna optimalizacia/modelovanie a optimalizacia

no mam problem najst vsetky cesty medzi dvoma vrcholmi. Myslel som že použijem prehľadávanie do hĺbky ale to zlyháva ...

Mozno do sirky ale to ani neviem implementovať ...

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson