著者

加賀谷 光祐 冨澤 眞樹 遠山 宏明

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J105-D, no.3, pp.144-153, 2022-03-01

---

Lunar Lockoutは解の存在を判定する問題がNP困難であることが知られているスライディングブロックパズルである.また,Generalized Lunar Lockout Variantは動かない駒の使用を認めたLunar Lockoutであり,解の存在を判定する問題はPSPACE完全であることが示されている.本研究では,Generalized Lunar Lockout Variantに対して,各駒の移動回数を高々k回に制限した解が存在するか否かを判定する問題を導入し,k≧ 3のときNP完全であることを証明した.

著者

遠山 宏明 足立 暁生

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.37, no.11, pp.1886-1896, 1996-11-15

参考文献数

8

---

混合グラフのもとでのチャイニーズ・ポストマン問題(CPP)はNP完全であることが示されている. すべての辺の長さが等しい混合グラフ 平面混合グラフ 最大次数を3に制限した混合グラフのもとでさえNP完全である. 一方 グラフを全有向 または全無向に制限したCPPは多項式時間アルゴリズムを持つ. 本論文では 各辺の通行回数をたかだか2回に制限したCPP (2-CPP)がNP完全であり ちょうど1回に制限したCPP(1-CPP)はPに属することを示した. また CPP に関連する2つの興味ある関数の計算量も示した: (i)2-CPPにおいて 配達路の数を計算する関数は#P完全である (ii)CPPにおいて コスト k 以下で配達するためには 同一辺を少なくとも何回通行しなければならないかを計算する関数は多項式時間階層のクラスΔ^P_2に属する.The Chinese Postman Problem (CPP) on the mixed graphs is shown to be NP-complete. It remains NP-complete even if restricted to those whose edges all have equal length, or to the one on the mixed planner graphs, or to the one on the mixed graphs with nodes of degree three. CPP can be solved in polynomial time if the graph is either directed or undirected. In this paper, we show that even if the number of traverses for each edge is restricted to at most twice, CPP on the mixed graphs (called 2-CPP) is NP-complete, and if the number of traverses for each edge is restricted to exactly once, CPP on the mixed graphs (called 1-CPP)is in P. We also show complexity of two related functions: (i) in 2-CPP the function that calculates the number of delivery paths is #P-complete, oh the other band, (ii) in CPP the function that calculates the minimum of the maximum traverse numbers for each delivery path of cost k or less belongs to the class AZ in the polynomial time hierarchy.

著者

遠山 宏明 足立 暁生

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

no.950, pp.39-45, 1996-05