Chip spil

Et chipspil er en type matematisk spil , hvor spillet består i at flytte "chips" eller "markører" på en rettet graf . Der findes et stort antal forskellige chipspil.

Passage af chips

Piece passing er et spil, hvor brikker placeres på hjørnerne af en rettet acyklisk graf G ifølge nogle regler.
- Spillets forløb består enten i at placere en jeton i toppen af grafen G , eller i at trække en jeton tilbage fra det toppunkt, som chippen optager.
- Et toppunkt kan kun optages af et token, hvis alle dets forgængere er til stede.
- Målet med spillet er at besøge alle hjørnerne af grafen G (i vilkårlig rækkefølge) med det mindste antal jetoner placeret på grafen på samme tid.

Spilletid

En triviel løsning er at fylde en n -vertex-graf med tokens i n trin ved hjælp af n tokens. Hopcroft, Paul og Valient [1] viste, at ethvert hjørne af en graf med n hjørner kan besøges med tokens, hvor konstanten afhænger af den maksimale besøgsgrad. Dette gjorde dem i stand til at bevise, at DTIME er indeholdt i DSPACE for alle tidskonstruerede funktioner f . Lipton og Tarjan [2] viste, at enhver n -vertex plan rettet acyklisk graf med maksimal indegree k kan krydses med tokens. De beviste også, at det er muligt at opnå en signifikant reduktion i antallet af tokens, mens man opretholder et polynomium, der er bundet til antallet af tokenplaceringstrin, hvilket beviser sætningen om, at enhver n -vertex plan acyklisk rettet graf med maksimal indegree k kan krydses med tokens i tide . Alon, Seymour og Thomas [3] viste, at enhver n -vertex acyklisk rettet graf uden k h - mindre og maksimal indegree k kan krydses med tokens. $O(n\log n)$ $(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)$

Passage med sorte og hvide brikker

En generalisering af dette spil, kendt som sort-hvid aflevering, blev udviklet af Stephen Arthur Cook og Ravi Seti i et papir fra 1976 [4] . Der tilføjes hvide tokens til spillet, som kan placeres på et hvilket som helst toppunkt, vi ønsker, men et sådant token kan kun fjernes, hvis alle umiddelbare underordnede hjørner også er optaget af tokens. Målet forbliver det samme - at placere en sort chip på målspidsen, men at fylde tilstødende spidser med chips kan gøres med chips af enhver farve.

Andre muligheder

Takumi Kasai, Akeo Adachi og Shigeki Iwata udviklede et spil, hvor en brik kun kan bevæge sig langs en kant til et ubesat toppunkt, hvis den anden brik er placeret på det tredje kontrolpunkt. Målet er at føre chippen frem til målet vertex. Disse variationer gør chipspillet til en generalisering af spil som kinesisk dam og halma . De definerer den beregningsmæssige kompleksitet af en- og tospillerversionerne af spillet og deres specielle versioner. I versionen med to spillere flytter spillerne skiftevis brikkerne. Der kan være begrænsninger på, hvilke brikker en spiller kan flytte [5] .

Spillet med brikker kan generaliseres til Ehrenfeucht-Frais spillet [6] .

Se også

Gennemgang af chips i grafen : et vist antal chips er placeret i spidserne af en urettet graf. Målet er at nå målet vertex, men for at flytte en brik til et tilstødende toppunkt, skal en anden brik på samme toppunkt fjernes.

Noter

↑ 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.

Litteratur

Hopcroft J., Paul W., Valiant L. On Time versus space // J. Assoc. Comput. Mach.. - 1977.
Richard J. Lipton, Robert E. Tarjan. Anvendelser af en plan separatorsætning // SIAM J. Comput.. - 1980.
Noga Alon, Paul Seymour, Robin Thomas. En separatorsætning for grafer med et udelukket bifag og dets anvendelser // ACM. - 1990.
Stephen Cook , Ravi Sethi. Lagringskrav til deterministiske polynomiske tidsgenkendelige sprog // 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. Klasser af småstensspil og komplette problemer // SIAM Journal on Computing . - 1979. - T. 8 , no. 4 . - doi : 10.1137/0208046 .
Howard Straubing. Finite automater, formel logik og kredsløbskompleksitet. - Basel: Birkhäuser, 1994. - (Progress in Theoretical Computer Science). — ISBN 3-7643-3719-2 .
Nicholas Pippenger. Småsten. Teknisk rapport RC 8258, IBM Watson Research Center // Proceedings of the 5th IBM Symposium on Mathematical Foundations of Computer Science, Japan. - 1980.
Jakob Nordström. Pebble Games, Proof Complexity, and Time-Space Trade-offs // Logical Methods in Computer Science . - 2013. - September ( bind 9 , hæfte 3 ).

Læsning for yderligere læsning

Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Marx Maarten, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein. Finite model teori og dens anvendelser. - Berlin: Springer-Verlag , 2007. - (Texts in Theoretical Computer Science. An EATCS Series). - ISBN 978-3-540-00428-8 .