著者
堀山 貴史 庄子 亘
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2012, no.9, pp.1-8, 2012-05-07

多面体の展開図 (辺展開とも呼ばれる) は,多面体を辺に沿って切り開くことで得られる多角形である.切り開く辺が異なっても,同型な展開図が得られることがある.例えば,立方体には 384 通りの展開の仕方 (つまり辺の切り開き方) があるが,同型なものを除去することで,11 種類の本質的に異なる (非同型な) 展開図が得られる.本稿では,任意の多面体に対し,非同型な展開図の個数を数え上げる方法について述べる.また,この手法をすべての整面凸多面体 (正多面体,半正多面体,ジョンソン・ザルガラーの多面体,アルキメデスの角柱と反角柱) に適用し,それぞれの非同型な展開図の個数を示す.たとえば,角切り二十面体 (サッカーボールフラーレン) には 375,291,866,372,898,816,000 通りの展開方法があるが,同型なものを排除することで 3,127,432,220,939,473,920 種類の異なる展開図が存在することが分かった.An unfolding (also called an edge unfolding) of a polyhedron is a simple polygon obtained by cutting along the edges of the polyhedron and unfolding it into a plane. Different edge-cuts of a polyhedron may have the same (i.e., isomorphic) unfolding. For example, a cube has 384 way of unfolding (i.e., cutting its edges). By omitting mutually isomorphic unfoldings, we have 11 essentially different (i.e., nonisomorphic) unfoldings. In this paper, we propose how to count the number of nonisomorphic unfoldings for any polyhedron. We also give the number of nonisomorphic unfoldings for all regular-faced convex polyhedra (i.e., Platonic solids, Archimedean solids, Johnson-Zalgaller solids, Archimedean prisms, and antiprisms). For examaple, while a truncated icosahedron (a Buckminsterfullerene, or a soccer ball fullerene) has 375,291,866,372,898,816,000 way of unfolding, it has 3,127,432,220,939,473,920 nonisomorphic unfoldings. (This article is a technical report without peer review.)
著者
方波見 尚之 築地 立家
出版者
一般社団法人情報処理学会
雑誌
研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.2009, no.9, pp.51-58, 2009-01-23

はさみ将棋とは、自分の駒を用いて相手の駒をはさんでとる 2 人対戦型ゼロサムゲームであり、日本のはさみ将棋、タイの Mak-yak などが有名である。本稿では、盤面を n×n に拡張した一般化はさみ将棋の計算複雑さについて考察する。ここでは、縦、横方向に自由に動く駒に加えて、不動駒も使用するものとする。また、縦横方向に加えて斜め方向の取りも許すものとし、相手の駒を先に 5 個取った方が勝ちとする。このとき、任意に与えられた一般化はさみ将棋の盤面について、勝ち・負け・引き分けのいずれであるかを判定する問題が、 EXPTIME 完全問題であることを証明する。Hasami-Shogi is a two-person zero-sum board game where each player aims to take a number of the opponent's pieces at once by making a sandwich position; a sandwich position occurs when the player's two pieces sandwich a number of the opponent's pieces placed consecutively on a row, a column, or a diagonal squares. In this paper, we generalize it to the n×n board, on which each piece moves like the rook. In addition, we allow a number of the immobile piece to exist. The winner is the player who takes at least 5 opponent's pieces at first. Then, we prove that the problem of determining whether a given position of the generalized Hasami-Shogi is either a player's winning position, or an opponent's winning position, or a draw position, is EXPTIME Complete.
著者
堀山 貴史 庄子 亘
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2012-AL-140, no.9, pp.1-8, 2012-05-07

多面体の展開図 (辺展開とも呼ばれる) は,多面体を辺に沿って切り開くことで得られる多角形である.切り開く辺が異なっても,同型な展開図が得られることがある.例えば,立方体には 384 通りの展開の仕方 (つまり辺の切り開き方) があるが,同型なものを除去することで,11 種類の本質的に異なる (非同型な) 展開図が得られる.本稿では,任意の多面体に対し,非同型な展開図の個数を数え上げる方法について述べる.また,この手法をすべての整面凸多面体 (正多面体,半正多面体,ジョンソン・ザルガラーの多面体,アルキメデスの角柱と反角柱) に適用し,それぞれの非同型な展開図の個数を示す.たとえば,角切り二十面体 (サッカーボールフラーレン) には 375,291,866,372,898,816,000 通りの展開方法があるが,同型なものを排除することで 3,127,432,220,939,473,920 種類の異なる展開図が存在することが分かった.
著者
若月 祐介 築地 立家
出版者
一般社団法人情報処理学会
雑誌
研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.2009, no.9, pp.43-50, 2009-01-23

DNA コンピュータを用いれば,ナノスケールの計算素子として DNA 分子を利用することにより,超並列計算を実現することができる.実際, Adleman らは, DNA コンピュータが DES 暗号を効率的に解読できることを示した.そこで,本論文では, AES 暗号を効率的に解読するような,複数の DNA アルゴリズムを示す.ところで, AES は DES よりもはるかに解読が難しい暗号として知られている.実際, Adleman らの DES 解読アルゴリズムを単純に拡張した AES 解読アルゴリズムでは, DNA メモリコンプレックスの長さが 7 倍以上になってしまう.我々のアルゴリズムを用いれば, DNA を切り離すための制限酵素を使用することにより,高々 1.3 倍の長さのメモリコンプレックスで AES コードが解読できることが示される.DNA computer utilizes DNA molecules as nanoscale computational elements to provide efficient computations for currently intractable problems. Actually, Boneh, Dunworth, Lipton showed that a DNA computer can efficiently decrypt DES encryption codes. In this paper, we show a couple of algorithms decrypting given AES codes by a series of parallel DNA operations. Since AES is known as much harder than DES to be decrypted, e.g. AES uses 128 bits, while DES uses 64 bits, of the hidden key, a simple extension of their algorithm requires DNA memory complexes of 7 times longer than the previous ones. One of our results shows that, by inserting restriction enzyme DNA cutting operations, much shorter memory complex is enough to decrypt given AES codes.
著者
菊地 洋右
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2010-AL-131, no.7, pp.1-4, 2010-09-15

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury’s Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury’s Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。
著者
保木邦仁
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2012, no.5, pp.1-1, 2012-03-07

将棋は西洋のチェスと同じルーツを持つゲームと考えられている。そのため、将棋とチェスのルールには類似点が多い。その一方で、持ち駒ルールのように異なった性質もある。このようなルール上の違いは、人工知能及びアルゴリズム設計の難易度に大きな影響を与えた。実際、IBM ディープ・ブルーが 1997 年にチェスの世界チャンピオンを破った時でも、当時のコンピュータ将棋の棋力は通常のアマチュアプレイヤー以下であった。コンピュータ将棋が人間トップに迫るほどの棋力を獲得したのはごく最近である。2010 年はあから 2010 が清水市代女流王将に勝利し、2011 年には Ponanza が著名なインターネット対局場 (将棋倶楽部 24) の短時間対局で最高レーティングを獲得、また 2012 年にはボンクラーズが米長邦雄永世棋聖に勝利した。本公演では、最近のコンピュータ将棋の動向に加えて、強いプログラムの一つである Bonanza の思考の仕組みを紹介する。高精度評価関数の最適化や、力ずく探索の枝刈り手法について、将棋とチェスの違いを示す。
著者
馬場 雅大 小野 廣隆 定兼 邦彦 山下 雅史
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2010-AL-129, no.1, pp.1-8, 2010-02-26

大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた.本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる.提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり,右の子へ巡回するといった操作を定数時間で行うことができる.また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す.
著者
斎藤 寿樹 川原 純 吉仲 亮 鈴木 拡 湊 真一
出版者
情報処理学会
雑誌
研究報告アルゴリズム(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.
著者
鈴木 浩史 中野 裕太 住谷 陽輔 湊 真一 前田 理
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2018-AL-169, no.7, pp.1-6, 2018-08-27

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

近年では社会の複雑化に伴って,より巨大なグラフに対する最短経路問題の解決が求められるようになってきている.しかし,巨大なグラフに対する最短経路問題を実際に計算機上で解くためには,グラフの大きさに比例した多くのメモリが必要になる.本研究では,平面上の最短経路問題を解く実用的でメモリ効率の良いアルゴリズムの開発を行う.また,現場では障害物をある対価を払って通過することがあり,そのような障害物に重みがついている場合への拡張も行う.
著者
藤田 実沙 木村 貴幸 神野 健哉
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2016-AL-158, no.20, pp.1-6, 2016-06-17

ノード V,エッジ E,エッジのコスト関数 c からなる無向グラフ G = (V,E,c) とターミナル T ∈ V が与えられたとき,T の全てを連結する閉路のない部分グラフをシュタイナー木と呼ぶ.特に,入力されたグラフに対する最小コストのシュタイナー木を求める問題をシュタイナー木問題と呼ぶ.シュタイナー木問題は NP 完全な組合せ最適化問題であるため,近似解を求めるのが一般的である.本研究では,シュタイナー木問題に対してネットワーク中心性を考慮した解構築手法を提案する.ネットワーク中心性のうち媒介中心性は,ネットワーク中の全最短経路に多く使用されるノードやエッジを中心とするネットワーク評価指標である.媒介中心性が高いノードやエッジをシュタイナー木に含むことにより,コストの小さいシュタイナー木を得ることができると考えられる.本稿では,媒介中心性を考慮したシュタイナー木構築手法の性能を,ベンチマーク問題を用いて評価する.数値実験の結果から,媒介中心性を考慮することにより,従来法と比較してコストの小さいシュタイナー木を得られることを確認した.
著者
小西 達也 小島 英春 中川 博之 土屋 達弘
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2017-AL-165, no.28, pp.1-6, 2017-11-09

本論文では,ソフトウェアテストの 1 つ,組み合わせテストについて議論する.具体的には,組み合わせテストで使用するテストケース集合の1つ, ロケーティングアレイに焦点を当てる.ロケーティングアレイは,与えられたパラメータ値の組み合わせをすべて網羅しているだけでなく,実行結果から不具合の原因となる組み合わせを特定することができる.ロケーティングアレイの生成手法に関する研究はまだ少なく, また,多くの場合について構成に必要な最小のテストケース数がわかっていない.そこで,SAT ソルバを使用したロケーティングアレイの生成手法を提案する. また,実際にロケーティングアレイを求め,得られた最小のテストケース数についても報告する.
著者
吉田 拓弥 川原 純 井上 武 笠原 正治
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2017-AL-165, no.16, pp.1-7, 2017-11-09

ネットワーク信頼性評価とは,ネットワークの各リンクに静的な故障確率が設定されている場合に,2 頂点間が通信可能である確率を求める問題である.確率を厳密に計算する手法として,二分決定グラフ (BDD) を用いた計算方法が知られている.BDDは 論理関数を圧縮して効率よく表現できるデータ構造である.本稿では,ネットワークの 2 つ以上のリンクの故障に依存関係がある場合の信頼性評価を行う.本手法では,リンク間に存在する依存関係を BDD で表現し,依存関係を考慮しない場合に構築した BDD との二項演算を行うことで,依存関係を考慮した信頼性 BDD を生成し,確率を計算する.本手法を 3 つの計算方法で実装し,各方法を処理時間と生成される BDD のノード数の観点から比較を行う.
著者
加藤 剛 湊 真一
雑誌
研究報告アルゴリズム(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 通りであることを初めて明らかにした.本稿ではその計算方法について述べる.
著者
小池 敦 定兼 邦彦
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2016-AL-159, no.7, pp.1-8, 2016-09-16

本論文では,道路ネットワーク上の経路探索クエリについて,新しいアルゴリズムを提案する.提案手法は Hub Labeling や Pruned Highway Labeling と同様,ラベリング法に基づくものである.前処理において,入力グラフを複数の木に分解し,各ノードが hub ノード集合の代わりに木の ID の集合を保持することでラベルサイズを削減させる.本論文ではアルゴリズムを実装し,米国の道路ネットワークを用いて評価を行うことで,提案アルゴリズムの有効性を示す.
著者
御船 雄太 宮北 和之 中野 敬介
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2014, no.13, pp.1-6, 2014-11-13

比較的長い通信遅延を許容して情報伝送を行うためのネットワークを遅延耐性ネットワーク (Delay Tolerant Network: DTN) と呼ぶ.本報告では,無線端末同士の情報交換および移動により情報拡散を行うエピデミック伝送により実現される DTN を考える.エピデミック伝送の用途としてはある特定の端末に対する情報配信の他に,地域情報配信や災害時情報配信のように,ある特定の空間にいる不特定の端末への情報伝達も考えられる,このとき,特定の場所や空間に情報を "滞留" させておく必要があり,エピデミック伝送を用いた情報滞留が検討されている.本報告では,エピデミック伝送による情報滞留の応用として,商店街においてクーポンを情報滞留させ,景品の引換所に客を誘導することにより商店街全体で客を誘導することを考える.ここでは,情報の過度な拡散を防ぐために,端末の情報の送信を空間的に拡散制御しながら実現する情報滞留を考え,情報の魅力度,および景品の交換所の数や設置場所が客の誘導に与える影響について計算機シミュレーションにより評価する.A network that enables us to exchange information by tolerating a long delay time is called a Delay Tolerant Network (DTN). In this report, we consider DTNs realized by epidemic transmissions, in which information is spread by wireless transmission between nodes and mobility of the nodes. A DTN can be used to transmit information to unspecified nodes in a specific area. Such situations can be seen in information delivery in a local area and that in disaster situations. For this purpose, information has to be floated in the destination space so that nodes entering the space later get the information as well as nodes being there. In this report, we consider to steer nodes toward a shopping area by floating electric coupons that can be exchanged into a gift at exchange places in the shopping area. We consider to realize information floating by epidemic transmissions with spatial transmission control for suppressing useless information spreading, and evaluate the effects of attractiveness of information, the number and locations of exchange places on the effectiveness of steering the nodes by computer simulation.
著者
中原 孝信 宇野 毅明 羽室 行信
出版者
一般社団法人情報処理学会
雑誌
研究報告アルゴリズム(AL) (ISSN:09196072)
巻号頁・発行日
vol.2013, no.27, pp.1-8, 2013-10-30

本研究は,Twitter の投稿内容に,データ研磨技術を用いたマイクロクラスタリングを利用することで,単語の共起関係に基づいたクラスタによる概念を構築する.そして興味対象となるツイートをできる限り多く被覆するような少数のクラスタを,ナップサック制約付き最大被覆問題を用いて抽出することで,投稿内容の要約を行う.抽出されたクラスタは,ある特定のツイート群の文章を特徴付ける単語のグループとして捉えることができ,それらを概念として扱う事で,単語を独立に扱った場合に比べて,すぐれた要約になっていることを示す.計算実験では,テレビアニメーション番組「宇宙兄弟」に関する投稿内容を対象にして提案手法を適用した.This research proposes a method to detect the contents of Twitter posts by analyzing the contents of tweets posted by viewers watching a specific TV program whenever the number of posts increase dramatically and then to summarize that content. First the proposed method creates concepts from clusters based on the co-occurrence of words. Then posts during tweet bursts are taken to be tweets of interest, and a minimal number of clusters that cover as much as possible those tweets are extracted using a knapsack-constrained maximum covering problem. A computational experiment shows the effectiveness of the proposed method with reference to a TV animation program "Space Brothers."
著者
沖 忠親 田岡 智志 渡邉 敏正
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2010-AL-129, no.7, pp.1-8, 2010-02-26

2 部グラフの k 辺連結化問題 (以下,UW-Bipartite- (k+1) ECA (*, MA) と略記) は以下のように定義される: 「無向 2 部グラフ G = (V + ∪V-,E) が与えられたとき,辺付加後のグラフ G' = (V + ∪V- ,E∪E') が (k + 1) 辺連結 2 部グラフであるような最小の付加辺集合 E' を求めよ.」本稿では,G が k 辺連結であるときに最適解を算出する高速アルゴリズムを提案し,k ∈ {1, 2} のとき線形時間で解けることを示す.
著者
Tadachika Oki Satoshi Taoka Toshimasa Watanabe
雑誌
研究報告アルゴリズム(AL)
巻号頁・発行日
vol.2010-AL-131, no.10, pp.1-8, 2010-09-15

The k-edge-connectivity augmentation problem with multipartition constraints (kECAM for short) is defined by “Given an undirected graph G = (V, E) and a multipartition π = {V1, . . . , Vr} of V with Vi ∩ Vj = ∅ for ∀i, j ∈ {1, . . . , r} (i ≠ j), find an edge set E' of minimum cardinality, consisting of edges that connect distinct members of π, such that G' = (V, E ∪ E') is k-edge-connected.”In this paper, we propose a fast algorithm for finding a solution to (σ+1)ECAM when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}. The main idea is to reduce (σ + 1)ECAM to the bipartition case, that is, (σ+1)ECAM with r = 2. Moreover, we propose a parallel algorithm for finding a solution to (σ + 1)ECAM, when a structural graph F(G) which represents all minimum cuts of G is given and σ is odd.
著者
奥山 拓哉 吉村 地尋 林 真人 田中 咲 山岡 雅直
雑誌
研究報告アルゴリズム(AL) (ISSN:21888566)
巻号頁・発行日
vol.2016-AL-158, no.14, pp.1-7, 2016-06-17

組合せ最適化問題を省電力かつ高速に解くため,イジングモデルの基底状態探索問題に変換して回路動作で解探索するイジング計算機が提案されている.半導体回路で空間的に効率良く表現可能なイジングモデルは規則的な構造であり,任意の最適化問題を解くためには基底状態を保持しつつモデルを変換する必要がある.本報告では Contractive graph minor-embedding を提案する.提案手法により対角線付き格子グラフに対してスピン数 100 のイジングモデルを 1 秒以内に変換する見込みを得た.