別解問題の計算量と完全性、およびパズルへの応用
スポンサーリンク
概要
- 論文の詳細を見る
問題IIに対する別解問題(ASP)というのは、IIのインスタンスxとそれに対する1つの解sが与えられた時に、xのs以外の解を求める問題のことである。(新しい問題クラスとしてのASPの概念はUedaとNagaoによる。)本論文ではn個の解が与えられた時にもう1つの解を求める問題(n-ASP)について考察する。特に、対応する解への変換も多項式時間で行えるような多項式時間parsimonious還元に関する完全性であるASP完全性について考察する。応用として、本論文では3つの有名なパズル、スリザーリンクとカックロ(クロスサム)とナンバープレース(数独)についてそのASP完全性(NP完全性を含意する)を示す。
- 2002-11-08
著者
関連論文
- 1-B-1 内航海運における在庫計画型の配船計画問題の必要性について(輸送・交通)
- 複数オーダーの同時積み付けを考慮したケミカルタンカーの船舶スケジューリング
- 叩くと光って音が鳴る打楽器 V850マイコン基板を使って電子打楽器「カホン」を製作
- 内航船の環境調和型運航支援システムに関する研究開発について (特集号 GHG)
- 数理計画を用いたセメント船団の船舶スケジューリング (オーガナイズドセッション(OS7) 船舶のルーティング及びスケジューリング問題について)
- 2-D-24 集合分割を用いた鉄鋼製品輸送船の船舶スケジューリング(物流)
- 別解問題の計算量と完全性、およびパズルへの応用
- 一般化詰将棋の余詰判定の指数時間完全性
- Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete(Discrete Mathematics and Its Applications)
- 集合被覆法を用いた船舶スケジューリングにおける複数オーダの同時積み付け計画の立案について
- 環境にやさしい運航支援--内航船の配船ソリューション
- Complexity and Completeness of Finding AnotherSolution and Its Application to Puzzles
- カックロの計算量
- 数理計画を用いたセメント船団の船舶スケジューリング(所外発表論文等概要)
- 内航船の環境調和型運航支援システムに関する研究開発について(GHG)
- 内航海運における在庫管理型の配船計画問題の必要性について(所外発表論文等概要)
- 集合被覆法を用いた船舶スケジューリングにおける複数オーダーの同時積み付け計画の立案について(所外発表論文等概要)
- 2-B-5 セメント船団に対する配船最適化システム適用実験(スケジューリング(2))
- 指向性アンテナを用いた船間無線LAN通信実験
- AIS情報からのデータマイニング
- 数理計画法を用いた内航最大規模の配船計画の最適化
- 集合被覆法を用いた船舶スケジューリングにおける複数オーダーの同時積み付け計画の立案について
- 集合被覆法を用いた船舶スケジューリングにおける複数オーダーの同時積み付け計画の立案について
- 2-B-11 衛星AISを用いた船舶の運行状況の分析
- 指向性アンテナを用いた船間無線LAN通信実験-II : 行会い状態における実海域実験
- 2-E-5 動的計画法を用いた船舶の速度計画最適化におけるキャッシングによる計算高速化について(輸送・交通(1))
- 動的計画法を用いた船舶の速度計画最適化におけるキャッシングによる計算高速化について(所外発表論文等概要)
- AISデータからの統計的海流推定(所外発表論文等概要)
- 2104 指向性アンテナを用いた無線LANによる船舶間通信実験(OS5-2 運転支援,OS5 安全・安心・防災,オーガナイズド・セッション(OS))
- 船間無線LAN通信による海上リアルタイムハザードマップの構築(航法システム研究会)