frikille:
na de hogy visszatérjek az irányítatlan gráf összes útjának meghatározására: nincs rá gyors algoritmus (értem itt hogy polinom időben megoldható). ha csak egy csúcsból kéne meghatározni, akkor talán a mélységi bejárás. de bármelyik lehet ebben az esetben a kiinduló csúcs. szóval marad az a lehetőség, hogy végignézed az összes lehetőséget. de ez egy nagyobb (~1000 csúcsot tartalmazó) gráfnál bármilyen gyors gépen se fog lefutni ebben az évszázadban (lehet hogy évezredben).
egyébként baromi kíváncsi vagyok hogy pontosan mi a probléma, amit ezzel lehet csak modellezni.
egy jatekot irok, amiben a jatekos egy x-szer y meretu tablan, amelynek minden mezojeben van egy szam 1tol z-ig, foglalhat el mezocsoportokat, amelyek olyan egymast atfedo (egymast metszo) szakaszokbol allnak, amik harom mezo hosszuak fuggolegesen vagy vizszintesen vagy atlosan, es novekvo vagy csokkeno szamsorozatot alkotnak. a jatekosnak nem muszaj egy teljes ilyen szakaszokbol allo utvonalat elfoglalnia, elfoglalhatja csak egy reszet is egy lepesben - ezert kell az osszes lehetseges reszgrafja (igy hivjak ezt magyarul?!) a grafnak. legalabbis ahhoz hogy validalni tudjam a lepest (jo, mondjuk ezt meg lehetne talan oldani mashogy is, de majd kell mashoz is az osszes lehetseges lepes).
merthogy azt gondoltam, hogy jo absztrakcioja a problemanak, hogy ezek a 3 mezo hosszu szakaszok egy graf csucspontjai, es a metszest mint viszonyt meg a graf elei jelentik. egy tablan az osszes ilyen harmas szakaszt (hivjuk tripletnek) eleg gyorsan megtalalom nyilvan, sot ezekbol a teljes, diszjunkt szigeteket alkoto “szupermezocsoportokat” is. de mint irtam, a jatekosnak nem kotelezo a teljes mezocsoportot elfoglalnia, amiben minden triplet metszi egymast, ezert egy ilyen csoporton belul kell az osszes valid kombinacio.
egyebkent amit az eredeti posztomban leirtam algoritmus nem is jo, ahogy arra jol ra is vilagitottal, mert mivel barmelyik csuccsal kezdodhet a bejaras, ezert tenyleg mindet hozza kell probalgatni mindhez, nem eleg csak a valamilyen sorrendben az adott csucs utan kovetkezo csucsokat. (hacsak nincs valami trukkos modja a helyes sorrend megallapitasanak, de akkor meg az visz el idot. meg nem is mindig van helyes sorrend.)
egyebkent ~1000 csucs nem annyira varhato talan, de azert jo lenne ha mondjuk egy akar 20x20as palyara is 1-2 masodperc alatt szamolna ki.
itt egy kep a tablarol, ha esetleg a leiras tul zavaros lenne. a bal felso sarokban van egy ilyen triplet-sziget egymast atfedo tripletekbol, amikbol a piros jatekos speciel nem foglalt el minden tripletet (egy jobbra-le atlos 321 kimaradt). tehat ha az osszes lehetseges lepes szerint akarom ervenyesnek elfogadni ezt a lepest, akkor az osszes lehetseges lepes kozt szerepelnie kell minden kibaszott reszgrafnak
Source: pblue
9 Notes/ Hide
-
pblue reblogged this from frikille and added:
egy jatekot irok, amiben...x-szer y meretu tablan, amelynek minden mezojeben van egy szam...
-
frikille reblogged this from pblue and added:
teljesen értem ezt...problémát. miért kell...összes út?...
-
beforezero liked this
-
wice reblogged this from pblue and added:
sajnos fingom sincs,...kell megcsinalni, de...minden...
-
regnisalram reblogged this from samli and added:
@magicmate? @diesbrothers?
-
szarpeniszszexmajom liked this
-
perfectvillain liked this
-
perfectvillain reblogged this from pblue and added:
érdekesen hangzik, remélem...válaszol. ráadásul teoretikusan még tökre értem
- samli reblogged this from pblue
-
pblue posted this
