Sirupeli

Sirupeli on eräänlainen matemaattinen peli , jossa peli koostuu "merkkien" tai "merkkien" siirtämisestä ohjatussa kaaviossa . Erilaisia sirupelejä on suuri määrä.

Sirujen kulku

Nappulan syöttö on peli, jossa nappuloita asetetaan suunnatun asyklisen graafin G kärkipisteille joidenkin sääntöjen mukaisesti.
- Pelin kulku koostuu joko sirun sijoittamisesta graafin G kärkeen tai sirun poistamisesta sirun varaamasta kärjestä.
- Token voi olla kärjessä vain, jos kaikki sen edeltäjät ovat läsnä.
- Pelin tavoitteena on vierailla onnistuneesti graafin G kaikissa pisteissä (missä tahansa järjestyksessä) mahdollisimman pienellä määrällä pelimerkkejä samaan aikaan.

Peliaika

Triviaali ratkaisu on täyttää n -pisteen graafi n - pisteessä tokeneilla käyttämällä n merkkiä . Hopcroft, Paul ja Valient [1] osoittivat, että missä tahansa graafin kärjessä, jossa on n kärkeä, voidaan vierailla tokeneilla, joissa vakio riippuu maksimikäyntiasteesta. Tämän ansiosta he pystyivät todistamaan, että DTIME sisältyy DSPACE -funktioon kaikille aikakonstruoiduille funktioille f . Lipton ja Tarjan [2] osoittivat, että mikä tahansa n -pisteinen tasosuuntainen asyklinen graafi , jonka inaste on maksimi k , voidaan kulkea merkkien avulla . He myös osoittivat, että on mahdollista saada merkittävä vähennys merkkien määrään samalla kun säilytetään polynomisidottu merkkien sijoitusaskeleiden määrä, mikä todistaa lauseen, että mikä tahansa n -pisteinen tasomainen asyklinen suunnattu graafi, jonka inaste on suurin k , voidaan kulkea rahakkeita ajoissa . Alon, Seymour ja Thomas [3] osoittivat, että mikä tahansa n -pisteen asyklinen suunnattu graafi ilman k h - molliarvoja ja suurinta astetta k voidaan kulkea merkkien avulla . $O(n\log n)$ ${\näyttötyyli (f(n))}$ $(f(n)\log f(n))$ $O({\sqrt {n}}+k\log _{2}n)$ $O(n^{\tfrac {2}{3}}+k)$ $O(n^{\tfrac {5}{3)))$ $O(h^{\tfrac {3}{2}}n^{\tfrac {1}{2}}+k\log n)$

Mustivalkoisten osien kulku

Tämän pelin yleistyksen, joka tunnetaan nimellä mustavalkoinen passi, kehittivät Stephen Arthur Cook ja Ravi Seti vuoden 1976 artikkelissa [4] . Peliin on lisätty valkoisia tokeneita, jotka voidaan sijoittaa mihin tahansa haluamaamme kärkeen, mutta sellaisen tunnuksen voi poistaa vain, jos kaikki välittömät lapsipisteet ovat myös rahakkeiden varassa. Tavoite pysyy samana - asettaa musta siru kohdepisteeseen, mutta vierekkäisten kärkien täyttäminen siruilla voidaan tehdä minkä tahansa värisillä siruilla.

Muut vaihtoehdot

Takumi Kasai, Akeo Adachi ja Shigeki Iwata kehittivät pelin, jossa nappula voi liikkua reunaa pitkin vapaaseen kärkeen vain, jos toinen nappula sijaitsee kolmannessa ohjauspisteessä. Tavoitteena on viedä siru eteenpäin kohdepisteeseen. Nämä muunnelmat tekevät sirupelistä yleistyksen sellaisista peleistä kuin kiinalainen tammi ja halma . Ne määrittelevät pelin yhden ja kahden pelaajan versioiden ja niiden erikoisversioiden laskennallisen monimutkaisuuden. Kahden pelaajan versiossa pelaajat siirtävät nappuloita vuorotellen. Pelaaja voi siirtää nappuloita rajoituksia [5] .

Peli nappuloiden syöttämisellä voidaan yleistää Ehrenfeucht-Frais -peliksi [6] .

Katso myös

Piirien läpikulku graafissa : ohjaamattoman graafin huipuissa on tietty määrä alibittejä. Tavoitteena on saavuttaa kohdepiste, mutta jotta nappula siirrettäisiin viereiseen kärkipisteeseen, samassa kärjessä on poistettava toinen nappula.

Muistiinpanot

↑ Hopcroft, Paul, Valiant, 1977 .
↑ Lipton, Tarjan, 1980 .
↑ Alon, Seymour, Thomas, 1990 .
↑ Cook, Sethi, 1976 , s. 25–37.
↑ Kasai, Adachi, Iwata, 1979 , s. 574–586.
↑ Straubing, 1994 , s. 39–44.

Kirjallisuus

Hopcroft J., Paul W., Valiant L. On Time versus space // J. Assoc. Comput. Mach.. - 1977.
Richard J. Lipton, Robert E. Tarjan. Tasoerotinlauseen sovellukset // SIAM J. Comput.. - 1980.
Noga Alon, Paul Seymour, Robin Thomas. Erotinlause kaavioille, joissa on poissuljettu sivu ja sen sovellukset // ACM. – 1990.
Stephen Cook , Ravi Sethi. Tallennusvaatimukset deterministisille polynomiaikatunnisteisille kielille // Journal of Computer and System Sciences . - 1976. - T. 13 , no. 1 . — S. 25–37 . - doi : 10.1016/S0022-0000(76)80048-7 .
Takumi Kasai, Akeo Adachi, Shigeki Iwata. Pikkupelien luokat ja täydelliset ongelmat // SIAM Journal on Computing . - 1979. - T. 8 , no. 4 . - doi : 10.1137/0208046 .
Howard Straubing. Äärilliset automaatit, muodollinen logiikka ja piirin monimutkaisuus. - Basel: Birkhäuser, 1994. - (Teoreettisen tietojenkäsittelytieteen edistyminen). — ISBN 3-7643-3719-2 .
Nicholas Pippenger. Pikkukivi. Tekninen raportti RC 8258, IBM Watson Research Center // Proceedings of the 5th IBM Symposium on Mathematical Foundations of Computer Science, Japani. – 1980.
Jakob Nordström. Pebble-pelit, todisteiden monimutkaisuus ja aika-avaruuden kompromissit // Tietojenkäsittelytieteen loogiset menetelmät . - 2013. - syyskuu ( nide 9 , numero 3 ).

Lue lisää lukemista varten

Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Marx Maarten, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein. Äärellisen mallin teoria ja sen sovellukset. - Berlin: Springer-Verlag , 2007. - (Tekstit teoreettisessa tietojenkäsittelytieteessä. EATCS-sarja). - ISBN 978-3-540-00428-8 .