著者
八登 崇之
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.2000, no.84, pp.25-31, 2000-09-21
被引用文献数
3

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.For many of the widely played games and puzzles, their computational complexities have been analyzed. In this paper, we consider a sort of puzzle "Slither Link" and prove that the problem which determines whether or not a given instance of puzzle has any solutions is NP-complete, by using a polynomial time reduction from the Hamilton Path Problem with respect to restricted graphs. In addition we consider Another Solution Problem for the puzzle, the problem which determines, for a given instance and its solution, whether there is another solution for the instance. We provide a strategy to prove its NP-completeness.

言及状況

はてなブックマーク (1 users, 1 posts)

Twitter (4 users, 11 posts, 4 favorites)

こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 https://t.co/SrmYvFl4de 現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析さ…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 https://t.co/SrmYvFl4de 現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析さ…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 https://t.co/5hZ2jCwmbD 現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析さ…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 https://t.co/5hZ2jCwmbD 現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析さ…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 https://t.co/5hZ2jCwmbD 現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析さ…
TVねた:深夜映画の影響で、論文ったーも釣られてるw QT ronbuntter: こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 http://id.CiNii.jp/LxnYL 現在多くの人に遊ばれてい…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 http://id.CiNii.jp/LxnYL 現在多くの人に遊ばれてい…
こんな論文どうですか? スリザーリンクのNP完全性について(八登 崇之),2000 http://id.CiNii.jp/LxnYL 現在多くの人に遊ばれてい…
5限の授業中にふとスリザーリンクってNP完全なのかなーと思って携帯で検索してみたら論文がすぐに見つかった。そりゃ考える人いるよねw http://ci.nii.ac.jp/naid/110002812406

収集済み URL リスト