- 著者
- 吉仲 亮 岩下 洋哲 川原 純 斎藤 寿樹 鶴間 浩二 湊 真一
- 出版者
- 公益社団法人日本オペレーションズ・リサーチ学会
- 雑誌
- オペレーションズ・リサーチ : 経営の科学 (ISSN:00303674)
- 巻号頁・発行日
- vol.57, no.11, pp.616-622, 2012-11-01
本稿では,フロンティア法による,与えられたグラフ上の特定の制約を満たす部分グラフ抽出の具体的応用例として,ナンバーリンクとスリザーリンクと呼ばれるパズルそれぞれのための解答器と問題生成器のアルゴリズムを提案し,実験結果を報告する.また,この技術を用いたスリザーリンクの問題作成支援についても議論する.
2 0 0 0 OA ZDDと列挙問題―最新の技法とプログラミングツール
- 著者
- 戸田 貴久 斎藤 寿樹 岩下 洋哲 川原 純 湊 真一
- 出版者
- 日本ソフトウェア科学会
- 雑誌
- コンピュータ ソフトウェア (ISSN:02896540)
- 巻号頁・発行日
- vol.34, no.3, pp.3_97-3_120, 2017-07-25 (Released:2017-08-09)
列挙問題とは,与えられた条件を満たす対象(解)をすべて求める問題であり,電力網解析など社会のさまざまな問題への応用がある.さまざまな組合せ列挙問題に対して,問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り,基礎となるアルゴリズムから,複雑な問題制約に対処するための発展的手法,プログラミングツールTdZddの基本的な使い方,さらに,具体的な応用問題を例にしたプログラミングまで解説する.
2 0 0 0 ZDDを用いたパスの列挙とその性能評価
- 著者
- 斎藤 寿樹 川原 純 吉仲 亮 鈴木 拡 湊 真一
- 出版者
- 情報処理学会
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:21862583)
- 巻号頁・発行日
- vol.2011, no.17, pp.1-6, 2011-02-28
- 被引用文献数
- 1
与えられたグラフ中のパスを列挙する問題は古典的な問題である.これまで,解を列挙するアルゴリズムや解の数を数えるアルゴリズムがいくつか提案されているが,一般に解の数は極めて多く,解の数を求める問題は #P-完全であるため,満足のいく高速な列挙アルゴリズムの実現は難しい.近年 Knuth は,ZDD (Zero-suppressed Binary Decision Diagram) を用いた任意のグラフの任意の 2 点間を端点とするパスを列挙するアルゴリズムを提案した.ZDD とは集合族を圧縮して表現できるデータ構造である.グラフの経路を辺の集合と同一視することによって,経路の集合は ZDD で表現することができる.提案されたアルゴリズムは,出力結果がパス集合の ZDD による圧縮表現であり,従来手法に比べ高速に動作する.本発表では,まず Knuth のアルゴリズムを紹介し,次に Knuth のアルゴリズムを基にした筆者らによる多項式回の ZDD の基本演算でパスの列挙を行うアルゴリズムを提案する.これらの手法と既存手法との比較実験を行い,ZDD によるパスの列挙手法の利を論ずる.The listing of all paths in a given graph is a classical problem. Although there are known algorithms for the problem, the number of the solutions tends to be huge and the counting problem is #P-hard. Recently, Knuth has proposed an algorithm for enumerating paths by using the ZDD (zero-suppressed binary decision diagram). The ZDD is a condensed representation of a family of sets. By identifying a path in a graph as a set of edges, the sets of paths can be represented by ZDD. His algorithm outputs a ZDD representing a set of paths. In this paper, we first introduce Knuth's algorithm, and propose an algorithm where ZDD operations implemented polynomial many times by extending Knuth's algorithm. We experiment with these algorithms and a known enumeration algorithm, and discuss the advantage of the algorithms using ZDD from the experimental result.
1 0 0 0 超スケーラブル汎用ブロック・チェーン技術に向けた情報学的研究
仮想通貨の基盤技術であるブロック・チェーンには,分散性・安全性・拡張性の三要素を同時に満たすことができないトリレンマ関係が存在し,そのため不特定多数の参加ノードからなる分散システム上で,高度なセキュリティを保証しかつ高速なトランザクション承認を提供するブロック・チェーンの実現が不可能と言われている.本研究課題では,ブロック・チェーンのトリレンマを克服するための方法論を情報学横断的に探求する.本研究で得られる成果はブロック・チェーン・ トリレンマの解決という意義に加え,IoTやフィンテック,ヘルスケア,行政・物流とい った幅広い分野での応用が期待される.
- 著者
- 吉田 拓弥 川原 純 井上 武 笠原 正治
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:21888566)
- 巻号頁・発行日
- vol.2017-AL-165, no.16, pp.1-7, 2017-11-09
ネットワーク信頼性評価とは,ネットワークの各リンクに静的な故障確率が設定されている場合に,2 頂点間が通信可能である確率を求める問題である.確率を厳密に計算する手法として,二分決定グラフ (BDD) を用いた計算方法が知られている.BDDは 論理関数を圧縮して効率よく表現できるデータ構造である.本稿では,ネットワークの 2 つ以上のリンクの故障に依存関係がある場合の信頼性評価を行う.本手法では,リンク間に存在する依存関係を BDD で表現し,依存関係を考慮しない場合に構築した BDD との二項演算を行うことで,依存関係を考慮した信頼性 BDD を生成し,確率を計算する.本手法を 3 つの計算方法で実装し,各方法を処理時間と生成される BDD のノード数の観点から比較を行う.
1 0 0 0 OA 思春期のメンタルヘルスと心身症(<特集>現代の若者のメンタルヘルス)
- 著者
- 小川原 純子 横山 祐子 森下 勇 一條 智康 加藤 直子 山岡 昌之
- 出版者
- 一般社団法人 日本心身医学会
- 雑誌
- 心身医学 (ISSN:03850307)
- 巻号頁・発行日
- vol.55, no.12, pp.1335-1342, 2015-12-01 (Released:2017-08-01)
思春期には体も心も大きく変化する.身体的発達のみならず,自我同一性(identity)の確立などこの時期の正常な心の発達を知ることは,思春期のうつ病や,摂食障害などの心身症を診察する際,その病態の基本的理解として欠かすことができない.また,思春期の患者がもつ生来の言語能力や社会適応力・認知力といった各人の能力を見極めることは,患者の感じている困難感の分析に有用である.さらに思春期に至るまでの生育環境や養育者との基本的信頼関係の構築の有無などの情報は,思春期の患者の心の発達過程での問題点を推測する重要な手掛かりとなる.
- 著者
- 小川原 純子 横山 祐子 森下 勇 一條 智康 加藤 直子 山岡 昌之
- 出版者
- 一般社団法人日本心身医学会
- 雑誌
- 心身医学 (ISSN:03850307)
- 巻号頁・発行日
- vol.55, no.12, pp.1335-1342, 2015-12-01
思春期には体も心も大きく変化する.身体的発達のみならず,自我同一性(identity)の確立などこの時期の正常な心の発達を知ることは,思春期のうつ病や,摂食障害などの心身症を診察する際,その病態の基本的理解として欠かすことができない.また,思春期の患者がもつ生来の言語能力や社会適応力・認知力といった各人の能力を見極めることは,患者の感じている困難感の分析に有用である.さらに思春期に至るまでの生育環境や養育者との基本的信頼関係の構築の有無などの情報は,思春期の患者の心の発達過程での問題点を推測する重要な手掛かりとなる.