BDD/ZDDを用いたペントミノパズルの解の列挙
スポンサーリンク
概要
- 論文の詳細を見る
二分決定グラフ(BDD)は,論理関数のグラフ表現であり,大規模な論理関数データでも比較的コンパクトなデータ構造として表現できる.さらに,BDDの特殊な型であるゼロサプレス型BDD(ZDD)は組合せ集合データの表現・処理に適しており,情報科学における様々な問題に応用できる.その一つの例が制約充足問題である.制約充足問題を解くために多くのアルゴリズムが考案されているが,その一方で,解集合の解析や新たな制約を加えて別の制約充足問題を解くということは,また別の問題として残っている.そこで,BDDまたはZDDで解全体を同時に表現することで,それらを効率よく行う方法を述べる.本稿では,古くから親しまれてきたペントミノパズルを取り上げ,これを制約充足問題として定式化した上でBDDとZDDに基づいた解法を示す.
- 2009-05-19
著者
-
野中 源一郎
九州大学薬学部
-
林 達哉
旭川医科大学耳鼻咽喉科・頭頸部外科学講座
-
湊 真一
北海道大学大学院情報科学研究科
-
湊 真一
函館五稜郭病院
-
鈴木 拡
北海道大学大学院情報科学研究科
-
湊 真一
北海道大学大学院情報科学研究科:科学技術振興機構erato湊離散構造処理系プロジェクト
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
北海道大学 大学院情報科学研究科
関連論文
- 自然地震観測におけるMEMS型加速度センサーの特性評価(首都直下地震防災・減災特別プロジェクトPart 2)
- IH(Induction Heating)ヒーターの補綴臨床における有用性
- 157 脳脊髄液減少症に五苓散が有効であった症例(漢方処方・湯液7,一般演題,伝統医学のあるべきかたちとは-世界の潮流と日本の役割-,第59回日本東洋医学会学術総会)
- 膵頭十二指腸切除術後の膵液瘻に対するドレーン排液中のアミラーゼ濃度と排液量に関する検討
- EVA シートを用いたロストワックス法によるCMG の製作
- 肩甲骨関節窩骨折に対して関節鏡を併用して内固定を行った 2 症例
- 評価の個人差に着目したアイデア分析に基づく創造的コラボレーション支援(機械要素,潤滑,設計,生産加工,生産システムなど)
- 不均一混合気の自着火過程を考慮したディーゼル燃焼モデル(熱工学,内燃機関,動力など)
- ドップラー速度と航跡を照合するクラッタ環境向け目標追尾開始方式(航行・誘導・制御方式,通信の未来を担う学生論文)
- 19.気管切開術施行後に喉頭気管分離術を施行した17症例の検討(一般演題,第20回日本小児呼吸器外科研究会)
- 高分子安定化法によって安定化したベンドセルの過渡応答特性のセル厚依存性
- 水産業における情報技術の活用について-V : マリンブロードバンドの活用
- UV硬化型液晶性ポリマー膜によるSS-FLCにおけるジグザグ欠陥の解消
- 光導電アンテナにおける連続テラヘルツ波に対するマイクロ波応答を用いたテラヘルツ周波数の測定
- RDS/VRDS-RFCCプロセスと触媒の技術進歩による残油アップグレーディング性能の向上
- ブロイラー胸肉の遊離アミノ酸含有量と肉の軟化に及ぼすブロメライン処理効果
- 6.高性能ルータ・スイッチの低消費電力化動向と光ネットワークデバイス技術の活用検討(グリーンICTに向けた光ネットワーク技術)
- 2004年台風15号(MEGI)により東北・北陸地方の日本海沿岸で発生した水稲の潮風害
- P3-423 分娩時の血清尿酸濃度は,妊娠高血圧症候群(以後,PIH)妊婦では児の出生体重の予測因子となりうる(パイロットスタディ)(Group149 妊娠高血圧3,一般演題,第62回日本産科婦人科学会学術講演会)
- 627 18Mn5Cr 鋼の冷間拡管加工後の残留応力分布におよぼす拡管加工温度の影響 : 高 Mn Cr 系オーステナイト鋼の冷間加工に関する研究 1(二相ステンレス鋼, 非磁性鋼, 材料, 日本鉄鋼協会第 113 回(春季)講演大会)
- 96 ESR のフラックスと溶解条件とプール深さの関係について(ESR, 製鋼, 日本鉄鋼協会 第 97 回(春季)講演大会)
- 20pPSA-39 ホーランダイト型マンガン酸化物の高圧合成と物性(20pPSA 領域8ポスターセッション(低温II(Cu,Ru,Mn,Co酸化物など,磁束量子系)),領域8(強相関系:高温超伝導,強相関f電子系など))
- 16 心療内科での治療介入時に精巣性女性化症候群であることが判明しうつ状態の増悪をきたした一例(一般演題D「多岐にわたる女性心身医療2」,これからの女性心身医学におけるサイエンスとその展望:分子レベルから臨床医学まで,第39回日本女性心身医学会学術集会)
- 内部統制構築の実際とPMOの活動--エンジニアリング会社の事例 (特集 内部統制)
- P-175 土壌中からの放出される水銀ガス量と地質構造との関連(27.環境地質,ポスター発表,一般講演)
- 平成10年度改訂学習指導要領下の「保健」授業におけるストレスマネジメント教育に関する研究
- P2-419 OK432投与により生児を得た胎児胸水症の2症例(Group95 胎児・新生児7,一般演題,第62回日本産科婦人科学会学術講演会)
- ポートフォリオ評価支援システムの実践と評価(情報教育と学習支援システム/一般)
- 急性虫垂炎における腹腔鏡下虫垂切除術と開腹虫垂切除術の比較検討
- 25pZW-6 スペース重力波アンテナDECIGO計画XIII : 設計・計画・パスファインダー(重力波(招待講演),宇宙線・宇宙物理領域)
- 壁面衝突噴流における渦形成と乱れエネルギー生成のPIV計測(熱工学,内燃機関,動力など)
- 司会のことば
- 急性・慢性中耳炎よりの検出菌の動向 : 第4回耳鼻咽喉科領域感染症臨床分離菌全国サーベイランスより
- (24)大型建築物の屋根雪堆積に関する研究(3基礎研究の推進)
- 10aSF-1 高輝度偏極光源の為の新型レーザー蓄積共振器の開発I(加速器,ビームライン,素粒子実験領域)
- 418 切除不能膵癌に対する消化管バイパス術の有用性について
- F-23)髄膜腫との鑑別を要した左後頭部腫瘍の乳児例(F 中枢神経系腫瘍,2009年小児腫瘍症例検討会)
- ロボットを対象とした新しい相互作用のデザインの試み--函館観光振興用ロボットIKABOを例として (特集 デザイン学)
- False-profile 像についての基礎的、臨床的検討
- 長距離移動するマガンの飛び立ち地点からの距離と飛行高度との関係
- B-1-72 衛星搭載用フェーズドアレーアンテナの機械変形に対する校正方法の校正精度改善(B-1.アンテナ・伝播B(アンテナ一般),一般セッション)
- B-1-77 60GHz帯ミリ波ブロードバンド通信システム用ポスト壁導波管スロットアレーアンテナ(B-1.アンテナ・伝播B(アンテナ一般),一般セッション)
- 衛星搭載用フェーズドアレーアンテナの機械的な変形を補正するビーム指向校正方式と校正精度に関する検討(アダプティブアンテナ,MIMO及び無線信号処理技術,無線通信一般)
- フェーズドアレーアンテナ指向性校正の校正精度に関する検討
- B-1-115 フェーズドアレーアンテナ指向性校正の校正精度に関する検討(B-1.アンテナ・伝播B(アンテナ一般),一般セッション)
- AlGaN/GaNヘテロ接合への低抵抗V/Al/Mo/Auオーミック電極の形成(窒化物及び混晶半導体デバイス)
- 置換法を用いた表面プラズモン共鳴免疫センサによるトリニトロトルエンの高感度検出(センサーデバイス,MEMS,一般)
- 223 無尾翼羽ばたき機を用いた蝶の飛行メカニズムの研究(S38-2 小型飛翔体(2),S38 生物飛行と小型飛翔体)
- 障害者スポーツ医学の最先端 : —残存骨格筋は内分泌器官である—
- Photonics West BiOS 2010 にみるレーザー医療・バイオ研究の最新動向
- 心臓再同期療法が奏効した, 拡張相肥大型心筋症(DHCM)の1例
- 肺クリプトコックス症に対する外科切除例の検討
- 術中止血困難な急速大量出血例に対するダメージコントロール時の圧迫留置ガーゼの留置期間とガーゼ感染
- 歯科患者ロボット : 歯科病院における矯正治療シミュレーション
- 頭頸部癌再発症例, 肺転移症例に対する外来化学療法としてのTS-1使用効果
- 72. イネ糊粉層に存在するβ-Yariv試薬反応性アラビノガラクタン蛋白質群の単離・同定
- 25pYC-2 有機超伝導体における一軸性圧縮効果(電荷秩序,電荷揺らぎ,非線形伝導,領域7,分子性固体・有機導体)
- JPEG2000の解像度スケーラビリティを利用した自由視点テクスチャフィルタリング法の一検討 (ITS)
- 19aXB-13 HERMESを用いた中性子線ホログラフィー測定の試み(X線・粒子線(中性子),領域10,誘導体,格子欠陥,X線・粒子線,フォノン物性)
- K2-16 体外循環併設肝切除時における循環態度の検討 : 門脈血脱血ルートの違いによる比較(第47回日本消化器外科学会総会)
- PP-2-240 肝切除後SIRS・合併症例における肝線維化マーカーの有用性についての検討
- 手打ちうどんの物性と食味に及ぼす澱粉・活性グルテン添加の影響
- 統合地震シミュレーションの高度化
- 28aRE-10 三角格子反強磁性体CuCrO_2における電気分極反転の外場による調節(フラストレーション系(三角格子・マルチフェロイック),領域3,磁性,磁気共鳴)
- サードラインで用いたS-1が有効であった印環細胞成分を有する肺腺癌の1例
- スサビノリ水溶性低分子画分のHL-60細胞の増殖に及ぼす影響
- 糸魚川-静岡構造線活断層系北部大町地域の浅層反射法地震探査
- 頭蓋底・顔面深部へのアプローチについて
- アメリカの影響力衰退とアメリカ精神の試練
- 50年前-胎動の頃
- 耳管機能障害の新しい手術治療『人工耳管』開発の試み ; 耳管開放症・閉鎖不全症での使用経験
- 水田における脱塩・乾燥クラゲの肥料効果と雑草抑制効果(日本作物学会四国支部第46回講演会講演要旨)
- 突発性難聴におけるパルクス^の使用経験
- 1022 Brugada症候群患者におけるdisopyramide静注時の右室流出路壁運動の変化 : 超高速CTを用いた検討
- SF7b-1 短期免疫抑制を用いた凍結保存異種気管移植の可能性
- 地上デジタル放送用フィルタ(チャンネルイレーサー「凸凹くん」)開発
- 広帯域エルビウムドープ光ファイバ増幅器の検討
- エレクトロパラトグラフィ (EPG) を用いた口蓋裂術後症例の歯茎音構音動態の分析 : —「口蓋化構音」は“palatalized”か“retracted”か—
- 焼酎粕ペレット飼料が繁殖豚の健康、同腹仔数、分娩子豚の生存率に及ぼす影響
- OP-1-082 進行大腸癌術後補助化学療法としてのlow dose 5-FU/CDDP療法の評価(大腸3)
- 教育現場における著作権保護の配慮と非常に簡単な操作での電子化された著作物の配布を実現可能にする資料複製・配布システム
- 3.血痰を初発症状とした甲状腺癌の1例(第22回日本気管支学会北海道支部会)
- 慢性気管支炎の急性増悪に対する biapenem の治療効果と臨床用量の検討
- 人工股関節置換術後, カップの弛みから広範な骨欠損を呈したにも関わらず歩行能力が維持されている1症例
- QT延長症候群(先天性・二次性)とBrugada症候群の診療に関するガイドライン(循環器病の診断と治療に関するガイドライン(2005-2006年度合同研究班報告))
- 21)心電図正常のサルコイドーシス症例における心病変合併頻度について
- FASEモデルにおけるシミュレーション思考の特性評価 : デザイン思考のクリエイティビティ(2)
- 清酒に含まれる有機酸の酸味に及ぼす飲用温度の影響
- FSS-2-2 女性心臓血管外科医の方法論と今後に望むこと(女性外科医の抱える問題とその対策,第109回日本外科学会定期学術集会)
- ダルベポエチン休薬により血小板減少を認めた維持透析患者の2症例 : ―Erythropoiesis stimulating agent（ESA）投与中止が血小板数に及ぼす影響―
- 先天性脛骨偽関節における組織およびNF1遺伝子の解析
- 1.免疫吸着療法(イムソーバTR)におけるブラジキニン産生についての検討(一般演題 : セッション1,日本アフェレシス学会第16回関東甲信越地方会抄録)
- 4.うま味の内臓感覚を介する食欲および嗜好性の調節(摂食機能と味覚・うま味の関連-4)
- まぐろ延縄漁業における混獲回避技術
- 癌性髄膜炎を発症した印環細胞を主とするS状結腸粘液癌の1例
- マハタへの経口投与におけるアルギン酸オリゴ糖の吸収性と免疫機能への影響
- 微細化可能な時間分解能型オールディジタルAD変換器TAD : あらゆるセンサのディジタル化を目指して(アナログ,アナデジ混載,RF及びセンサインタフェース回路)
- β受容体過剰刺激時におけるAT-II受容体拮抗薬と心筋保護薬JTV-519による心筋筋小胞体機能におよぼす影響(第82回日本循環器学会中国地方会)
- 24) 左主幹部病変に対してPTCAを施行し得た一例
- P443 心疾患における左房容積と肺動脈血中ANP濃度との関係 : シネモードMRIによる検討