一般化詰将棋の余詰判定の指数時間完全性

スポンサーリンク

概要

• 論文の詳細を見る

• サイズn×nに一般化した詰将棋(一般化詰将棋;GTS)の局面と作意手順が与えられたとき,余詰(作意以外の詰手順)の有無を判定する問題を余詰問題という.本研究ではGTSに対応する関数問題を適切に定義することで,余詰問題をこの関数問題の別解問題(ASP;事例と解が与えられたとき,与えられた解以外の解の有無を判定する問題)として定式化した.また,与えられた手順が正しい詰手順かどうかの判定は容易ではないため,プロミスの付いた関数問題のASPを取り扱う枠組を構築し,余詰問題をプロミス問題として取り扱った.これにより,GTSの指数時間完全性を示すのに用いた既存の還元をそのまま用いて余諸問題がプロミス指数時間完全であることを示した.

• 社団法人電子情報通信学会の論文
• 2004-06-18

著者

• 瀬田 剛広

  (独)海上技術安全研究所

• 伊藤 剛志

  東京大学大学院情報理工学系研究科

• 瀬田 剛広

  独立行政法人海上技術安全研究所(海技研 Nmri)

• 八登 崇之

  東京大学大学院情報理工学系研究科

• 瀬田 剛広

  東京大学大学院情報理工学系研究科

関連論文

• 1-B-1 内航海運における在庫計画型の配船計画問題の必要性について(輸送・交通)
• 複数オーダーの同時積み付けを考慮したケミカルタンカーの船舶スケジューリング
• 叩くと光って音が鳴る打楽器 V850マイコン基板を使って電子打楽器「カホン」を製作
• 内航船の環境調和型運航支援システムに関する研究開発について (特集号 GHG)
• 数理計画を用いたセメント船団の船舶スケジューリング (オーガナイズドセッション(OS7) 船舶のルーティング及びスケジューリング問題について)
• 有向グラフの推移閉包問題に対するFully Dynamicアルゴリズムの再定式化と実装
• 2-D-24 集合分割を用いた鉄鋼製品輸送船の船舶スケジューリング(物流)
• 別解問題の計算量と完全性、およびパズルへの応用
• 一般化詰将棋の余詰判定の指数時間完全性
• 長距離・短距離通信が混在する環境でのTCP/IPのデータ転送速度の理論的解析
• 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通信による海上リアルタイムハザードマップの構築(航法システム研究会)

もっと見る 閉じる

スポンサーリンク