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
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗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
Stránky: 1
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » diskretna optimalizacia/modelovanie a optimalizacia
#1 02. 06. 2014 20:43 — Editoval p4too (03. 06. 2014 21:37)
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:
doterajsie riesenie:
Kazdej farbe by som priradil nieake cislo 1-zelena, 2-cervena ...
0 by bolo prazdne policko ....
premenne 
policko i,j pouzita farba
ucelova funkcia by nebola
strukturalne podmienky:
... 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
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
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 ....
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 :
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}
najdem cesty {{1,4};{4,7};{7,8}} tu je len jedna
2. pre vrcholy 5,9
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
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)
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
Stránky: 1
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » diskretna optimalizacia/modelovanie a optimalizacia