Oblázková hra - Pebble game

Desková hra viz Go (hra).

v matematika a počítačová věda, a oblázková hra je typ matematická hra hraje přesunutím „oblázků“ nebo „značek“ na a řízený graf. Existuje celá řada různých oblázkových her. Specifická definice oblázku je uvedena níže.

  • Pebbling je hra, která zahrnuje umisťování oblázků na vrcholy směrovaného acyklického grafu G podle určitých pravidel.
    • Daný krok hry spočívá buď v umístění oblázku na prázdný vrchol G nebo odstranění oblázku z dříve oblázkového vrcholu.
    • Vrchol lze oblázkovat, pouze pokud všichni jeho předchůdci mají oblázky.
    • Cílem hry je postupně oblázkovat každý vrchol G (v libovolném pořadí) a zároveň minimalizovat počet oblázků, které jsou kdy v grafu současně.
  • Délka: Triviálním řešením je oblázkovat n-vertexový graf v n kroky pomocí n oblázky. Hopcroft, Paul a Valiant [1] ukázal, že jakýkoli vrchol an n-vrcholový graf lze oblázkovat pomocí O (n/ log n) oblázky, kde konstanta závisí na maximálním stupni. To jim umožnilo dokázat to DTIME (F(n)) je obsažen v DSPACE (F(n) / logF(n)) pro všechny časově konstruovatelný F. Lipton a Tarjan [2] ukázal, že každý n-vrchol rovinný acyklický řízený graf s maximálním stupněm k lze oblázkovat pomocí O (√n + k log2 n) oblázky. Rovněž dokázali, že je možné dosáhnout podstatného snížení počtu oblázků při zachování polynomu vázaného na počet kroků oblázkování s teorémem, že jakýkoli n-vertex planární acyklický orientovaný graf s maximálním stupněm k lze oblázkovat pomocí O (n2/3 + k) oblázky v O (n5/3) čas. Alon, Seymour a Thomas [3] ukázal, že každý n-vertexový acyklický směrovaný graf s č kh-Méně důležitý as maximem stupeň k lze oblázkovat pomocí O (h3/2 n1/2 + k log n) oblázky.
  • Rozšíření této hry, známé jako „černo-bílé oblázky“, vyvinula společnost Stephen Cook a Ravi Sethi v dokumentu z roku 1976.[4] Přidává také bílé oblázky, které lze umístit na libovolný vrchol podle libosti, ale lze je odebrat pouze v případě, že jsou oblázkovány také všechny vrcholy okamžitých potomků vrcholu. Cílem zůstává umístit černý oblázek na cílový vrchol, ale oblázkování sousedních vrcholů může být provedeno pomocí oblázků každé barvy.
  • Takumi Kasai et al. vyvinuli hru, ve které lze oblázek přesouvat podél hranové šipky na neobsazený vrchol, pouze pokud je druhý oblázek umístěn na třetím, řídícím vrcholu; cílem je přesunout oblázek na cílový vrchol. Tato variace dělá z oblázkové hry zevšeobecnění her, jako jsou Čínská dáma a Halma. Určili výpočetní složitost verze této hry pro jednoho hráče a pro dva hráče a její zvláštní případy. Ve verzi pro dva hráče se hráči střídají v pohybu oblázků. Mohou také existovat omezení, na kterých oblázcích se hráč může pohybovat.[5]
  • K prodloužení lze použít štěrk Hry Ehrenfeucht – Fraïssé.[6]

Viz také

  • Oblázkové grafy: Určitý počet oblázků je rozložen mezi vrcholy neorientovaného grafu; cílem je přesunout alespoň jeden na konkrétní cílový vrchol. Chcete-li však přesunout jeden oblázek na sousední vrchol, je třeba zahodit další oblázek na stejném vrcholu.
  • Věta o planárním oddělovači

Reference

  1. ^ J. Hopcroft, W. Paul a L. Valiant, On Time versus Space, J. Assoc. Comput. Mach. 1977
  2. ^ Richard J. Lipton a Robert E. Tarjan, Aplikace věty o planárním oddělovači, SIAM J. Comput. 1980
  3. ^ Noga Alon, Paul Seymour, Robin Thomas, The Separator Theorem for Graphs with a Exposed Minor and its Applications, ACM, 1990.
  4. ^ Stephen Cook; Ravi Sethi (1976). "Požadavky na úložiště pro deterministické polynomiální časově rozpoznatelné jazyky". Journal of Computer and System Sciences. 13 (1): 25–37. doi:10.1016 / S0022-0000 (76) 80048-7.
  5. ^ Takumi Kasai; Akeo Adachi; Shigeki Iwata (1979). "Třídy oblázkových her a úplné problémy". SIAM Journal on Computing. 8 (4): 574–586. doi:10.1137/0208046.
  6. ^ Straubing, Howard (1994). Konečné automaty, formální logika a složitost obvodů. Pokrok v teoretické informatice. Basilej: Birkhäuser. str.39–44. ISBN  3-7643-3719-2. Zbl  0816.68086.

Další čtení