WEKO3
-
RootNode
アイテム
しりとりゲームのNP困難性
https://ipsj.ixsq.nii.ac.jp/records/97526
https://ipsj.ixsq.nii.ac.jp/records/975263d5e4013-ace7-4776-865a-00f4d13d7186
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GPWS2002021.pdf (209.7 kB)
|
Copyright (c) 2002 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Symposium(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2002-11-15 | |||||||
| タイトル | ||||||||
| タイトル | しりとりゲームのNP困難性 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | NP-hardness of Word Chain Games | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 東京大学情報基盤センター | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Information Technology Center, University of Tokyo | ||||||||
| 著者名 |
田中, 哲朗
× 田中, 哲朗
|
|||||||
| 著者名(英) |
Tanaka, Tetsuro
× Tanaka, Tetsuro
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 「しりとりゲーム」はしりとりを完全情報化して定義したゲームである．完全情報ゲームなので，使用可能な文字の種類，使用可能な単語の集合と開始文字を決めれば，勝敗は決定可能である．「しりとりゲーム」の勝敗に関してはグラフとして表現した時に勝敗が同じで辺の少ないグラフに簡約する方法，文字の種類をnとしたとき，n=3までは定数時間で勝敗を決定可能であることが分かっているが，nを増やしていったときに，効率的に勝敗を決定するアルゴリズムがあるかは分かっていなかった．本論文では，しりとりゲームの勝敗の決定問題が文字の種類nに対してNP困難であることを示した．これにより，文字の種類によらずに，しりとりゲームの勝敗を効率的に求めるプログラムを書くのが困難であることが分かる． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The word-chain game (SHIRITORI in Japanese) in which two players are assumed to know all the words can be modeled as a game on graph. When given a set of words with a word to start, it is theoretically possible to decide whether the first player can win the game or not because it is a game with perfect information. As the alphabet size become bigger, problems become more difficult. In this paper, we show that problem is NP-hard. | |||||||
| 書誌情報 |
ゲームプログラミングワークショップ2002論文集 巻 2002, 号 17, p. 140-142, 発行日 2002-11-15 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
