著者

湊 真一

雑誌

情報処理

巻号頁・発行日

vol.54, no.11, pp.1152-1159, 2013-10-15

---

「おねえさんの問題」と呼ばれる格子グラフ上の経路数え上げ問題が,アルゴリズムの専門家のみならず,情報処理関連の研究者・技術者の間でも広く注目を集めている.本稿では,まず「おねえさんの問題」という名称の由来について述べ,この問題を効率よく解くためのデータ構造「ZDD」とKnuth のZDD 構築アルゴリズムについて簡単に解説する.次に,この問題が知られるきっかけになった日本科学未来館における研究成果展示とYouTube 動画の反響について振り返り,最近達成された世界記録の状況について述べる.最後に,この問題が高速に解けることで今後どのような応用が期待できるかを展望する.

著者

湊 真一

雑誌

人工知能

巻号頁・発行日

vol.31, no.3, 2016-05-01

著者

吉仲 亮 岩下 洋哲 川原 純 斎藤 寿樹 鶴間 浩二 湊 真一

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

オペレーションズ・リサーチ : 経営の科学 (ISSN:00303674)

巻号頁・発行日

vol.57, no.11, pp.616-622, 2012-11-01

---

本稿では,フロンティア法による,与えられたグラフ上の特定の制約を満たす部分グラフ抽出の具体的応用例として,ナンバーリンクとスリザーリンクと呼ばれるパズルそれぞれのための解答器と問題生成器のアルゴリズムを提案し,実験結果を報告する.また,この技術を用いたスリザーリンクの問題作成支援についても議論する.

著者

湊 真一

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.54, no.11, pp.1152-1159, 2013-10-15

---

「おねえさんの問題」と呼ばれる格子グラフ上の経路数え上げ問題が,アルゴリズムの専門家のみならず,情報処理関連の研究者・技術者の間でも広く注目を集めている.本稿では,まず「おねえさんの問題」という名称の由来について述べ,この問題を効率よく解くためのデータ構造「ZDD」とKnuth のZDD 構築アルゴリズムについて簡単に解説する.次に,この問題が知られるきっかけになった日本科学未来館における研究成果展示とYouTube 動画の反響について振り返り,最近達成された世界記録の状況について述べる.最後に,この問題が高速に解けることで今後どのような応用が期待できるかを展望する.

著者

湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.31-38, 2005-05-13

被引用文献数

6

---

二分決定グラフ(BDD)は, 大規模な論理関数データを効率よく表現する技法として広く利用されている.BDDの中でも, ゼロサプレス型BDD(ZBDD)と呼ばれるデータ構造は, 大規模な組合せ集合を非明示的に列挙し効率よく演算処理するのに適しており, 情報科学における様々な問題に適用できる.我々は, 数式により組合せ集合の演算を記述し, これをZBDDを用いて計算するプログラム「VSOP」を開発した.VSOPは単なる組合せ集合演算だけでなく, 集合の各要素に整数値(係数あるいは重み)を定義し, 加減乗除や大小比較等の算術演算を含む数式を処理できることを特長とする.本稿では, VSOPの内部データ構造や演算方法, データ表示形式について述べ, いくつかの応用例を示す.

著者

戸田 貴久 斎藤 寿樹 岩下 洋哲 川原 純 湊 真一

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.34, no.3, pp.3_97-3_120, 2017-07-25 (Released:2017-08-09)

---

列挙問題とは,与えられた条件を満たす対象(解)をすべて求める問題であり,電力網解析など社会のさまざまな問題への応用がある.さまざまな組合せ列挙問題に対して,問題の解集合を表現するデータ構造ZDDを高速に求める方法(トップダウンZDD構築法)を通して元の問題を効率的に解く汎用的な手法の研究が近年盛んに行われている.本論文ではトップダウンZDD構築に焦点を絞り,基礎となるアルゴリズムから,複雑な問題制約に対処するための発展的手法,プログラミングツールTdZddの基本的な使い方,さらに,具体的な応用問題を例にしたプログラミングまで解説する.

著者

渕本 壱真 湊 真一 植野 真臣

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.37, no.5, pp.A-M23_1-11, 2022-09-01 (Released:2022-09-01)

参考文献数

34

---

Recently, the necessity of“ parallel test forms ”for which each form comprises a different set of items, but which still has equivalent measurement accuracy has been emerging. An important issue for automated test assembly is to assemble as many parallel test forms as possible. Although many automated test assembly methods exist, the maximum clique using the integer programming method is known to assemble the greatest number of tests with the highest measurement accuracy. However, the method requires one month or more to assemble 450,000 tests due to the high time complexity of integer programming. This study proposes a new automated test assembly using Zerosuppressed Binary Decision Diagrams (ZDD). A ZDD is a graphical representation for a set of item combinations. This is derived by reducing a binary decision tree. In the proposed method, each node in the binary decision tree corresponds to an element of an item bank and has two edges if the item (node) is contained in a uniform test. Furthermore, all equivalent nodes (having the same measurement accuracy and the same test length) are shared. Finally, this study provides simulation and actual data experiments to demonstrate the effectiveness of the proposed method. The proposed method can assemble 450,000 tests within 24 hours.

著者

鈴木 浩史 孫 浩 湊 真一

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会全国大会論文集

巻号頁・発行日

vol.2016, pp.1D5OS02b3, 2016

著者

ムハマド ホリルロハマン 湊 真一

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会全国大会論文集 第29回全国大会(2015)

巻号頁・発行日

pp.4E11, 2015 (Released:2018-07-30)

---

与えられたグラフのオイラー路を高速に列挙索引化するアルゴリズムを提案する。このアルゴリズムは、KnuthのSimpath法を拡張したもので、有向非巡回グラフ(DAG)を用いて各辺の接続関係を圧縮して表現することにより、高速な計算を実現した。本手法により、膨大な個数のオイラー路を、現実的な時間で正確に数え上げることが可能となった。

著者

斎藤 寿樹 川原 純 吉仲 亮 鈴木 拡 湊 真一

出版者

情報処理学会

雑誌

研究報告アルゴリズム(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.

著者

齋藤 高央 湊 真一 ツォイクマン トーマス

雑誌

情報科学技術フォーラム講演論文集

巻号頁・発行日

vol.7, no.2, pp.355-357, 2008-08-20

著者

鈴木 浩史1 湊 真一1 Suzuki 1 Hirofumi Shin-ichi Minato

雑誌

SIG-FPAI = SIG-FPAI

巻号頁・発行日

vol.B5, no.01, pp.41-46, 2016-08-01

著者

鈴木 浩史 中野 裕太 住谷 陽輔 湊 真一 前田 理

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2018-AL-169, no.7, pp.1-6, 2018-08-27

---

化合物にはひとつの組成に対して様々な分子構造が存在し,それぞれで異なる性質を有する.化学反応における反応経路ネットワークとは,分子構造を頂点とし,遷移可能な分子構造の間に辺を引いたグラフ構造を指す.反応経路ネットワークの解析は,反応設計に携わる化学者の助けとなる重要なタスクである.本稿では,分子構造間の遷移に必要なエネルギーに着目し,エネルギーを制限した反応経路ネットワークの上で,特定の分子構造を始点とする単純経路を列挙する.ただし,経路の総数は組合せ爆発を起こすため,明示的な列挙は避けなければならない.そこで,SIMPATH アルゴリズムにより,暗黙的に全経路を格納したゼロサプレス型二分決定グラフ (ZDD) という圧縮データ構造を構築する.さらに,ZDD が持つ効率的な絞込み機能を応用することで,エネルギーの上限に対する可能な経路の抽出を行う.

著者

鈴木 拡 湊 真一

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第72回, no.「情報爆発」時代に向けた新IT基盤技術, pp.245-246, 2010-03-08

著者

鈴木 拡 湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.54, pp.1-7, 2009-05-19

参考文献数

11

被引用文献数

1

---

二分決定グラフ(BDD)は,論理関数のグラフ表現であり,大規模な論理関数データでも比較的コンパクトなデータ構造として表現できる.さらに,BDDの特殊な型であるゼロサプレス型BDD(ZDD)は組合せ集合データの表現・処理に適しており,情報科学における様々な問題に応用できる.その一つの例が制約充足問題である.制約充足問題を解くために多くのアルゴリズムが考案されているが,その一方で,解集合の解析や新たな制約を加えて別の制約充足問題を解くということは,また別の問題として残っている.そこで,BDDまたはZDDで解全体を同時に表現することで,それらを効率よく行う方法を述べる.本稿では,古くから親しまれてきたペントミノパズルを取り上げ,これを制約充足問題として定式化した上でBDDとZDDに基づいた解法を示す.

著者

湊 真一

出版者

電子情報通信学会

雑誌

電子情報通信学会誌 (ISSN:09135693)

巻号頁・発行日

vol.75, no.11, pp.1146-1149, 1992-11

著者

加藤 剛 湊 真一

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2019-AL-171, no.7, pp.1-7, 2019-01-22

---

7 次対称方陣とは,中心に関して対称な位置にある 2 マスの和が常に一定であるような 7 × 7 の魔方陣である.現在知られている 6 次の半魔方陣 (斜めの和の条件を持たない魔方陣) の数え上げの方法を参考にして,方陣を 2 つに分割して数え上げる手法を用いて計算した結果,7 次対称方陣の解の総数は,回転や鏡像で同じ形になるものを除いて,1,125,154,039,419,854,784 通りであることを初めて明らかにした.本稿ではその計算方法について述べる.

著者

西野 正彬 安田 宜仁 湊 真一 片岡 良治

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.26, 2012

---

ゼロサプレス型二分決定グラフ(ZDD)を用いて二値疎行列を用いて表現することによって、行列とベクトルの乗算に必要な計算回数を削減する手法が知られている。しかし、現代のコンピュータアーキテクチャ上では、計算回数の削減に見合った計算時間の削減はできていなかった。本稿では、メモリアクセスの連続性に着目してZDDによる行列の表現方法を改良することによって計算時間を削減する手法を提案する。

著者

豊島 鑑 井上 武 上松 仁 高橋 宏和 仁科 五月 高木 剛 湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会総合大会講演論文集

巻号頁・発行日

vol.2008, no.2, pp."S-66"-"S-67", 2008-03-05

被引用文献数

2

著者

伊藤 華 井上 祐馬 湊 真一

出版者

FIT(電子情報通信学会・情報処理学会)運営委員会

雑誌

情報科学技術フォーラム講演論文集

巻号頁・発行日

vol.14, no.1, pp.115-116, 2015-08-24