著者

堀山 貴史 庄子 亘

雑誌

研究報告アルゴリズム(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) (ISSN:21888566)

巻号頁・発行日

vol.2023-AL-191, no.2, pp.1-8, 2023-01-12

---

d 次元の n 個のベクトル列が与えられたとき,列ベクトルを並べ替えて d×n の行列として考える.行列の様子は列ベクトルの順序によるが,これを目的関数を最大/最小にするような列ベクトルの順列を見つける問題として定式化する.目的関数は,行列の各行に対するファーストフィット非減少部分列の要素の効用の和で定義することで,最大化問題をソーティング問題の自然な一般化として考えることができる.本論文では,d が定数の場合には,多項式時間アルゴリズムが構成できることを示し,d が一般である場合に対しては,集合被覆問題や劣モジュラ最適化との関係を調査し,計算複雑度を考察する.

著者

沖 忠親 田岡 智志 渡邉 敏正

雑誌

研究報告アルゴリズム(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} のとき線形時間で解けることを示す.

著者

馬場 雅大 小野 廣隆 定兼 邦彦 山下 雅史

雑誌

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

巻号頁・発行日

vol.2014-AL-148, no.17, pp.1-6, 2014-06-06

---

本稿では,k- 縮退グラフに含まれる誘導木 (連結かつ非巡回な誘導部分グラフ) を,効率よく列挙するアルゴリズムを与える.グラフ G=(V,E) が k-縮退 (k-degenerate) であるとは,G の任意の部分グラフが高々 k の次数を持つ頂点を含むときをいう.これまで,制約のある誘導部分グラフの列挙に関しては,連結な誘導グラフ (Avis,Fukuda,DAM,1996) や,コードレスパス,コードレスサイクル (宇野,第 92 回アルゴリズム研究会,2003) の列挙に関する先行研究があるが,誘導木については知られていない.最大次数が d のとき,誘導木 1 つ当たり O(d) 遅延の列挙アルゴリズムは容易に構成できるが,これをどの程度まで改善できるかは未解決の問題である.我々のアルゴリズムは,入力グラフ G が k- 縮退グラフであるとき,誘導木を 1 つ当たりならし O(k) 時間で列挙する.系として,k が定数ならば,誘導木を 1 つたり,ならし定数時間で列挙可能である.

著者

宇野 毅明

雑誌

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

巻号頁・発行日

vol.2020-AL-177, no.2, pp.1-7, 2020-03-09

---

データ研磨は,データのゆらぎを除去することで中小規模の構造を明確化し,マイニングアルゴリズムの効率や精度を高める手法である.例えば,ネットワーククラスタリングの場合,グラフの密な部分をクリークにし,疎な部分を独立集合とすることで,クラスタ構造を明確にする.通常のクラスタリングが,比較的大きなクラスタを見つけることが上手であるのに対して,データ研磨によるクラスタリングは,小さくてまとまりの良いクラスタを網羅的に,かつ独立性高く,適切な個数で見つけることができる.実際にそのクラスタは意味解釈がしやすく,新聞記事やツイッターのクラスタリングによりトピックを網羅的に見つけることが可能である.また,アルゴリズムの挙動も極めて安定しており,大規模なデータでも数十の反復で収束に至ることがほとんどである.データ研磨のアルゴリズムの基本的なデザインはシンプルであり,根拠となるデータに対する観察も明らかである.一方,収束性や得られた解と数理構造との対応は不明瞭であり,いわば実行可能仮説寄りのモデルである.本稿では,データ研磨アルゴリズムの数理的な側面を明らかにすべく,その挙動に関する数理的な解析や確率的な解析を行い,データ研磨アルゴリズムの現実データでの挙動の良さを数理的に裏付ける.

著者

戸田貴久

雑誌

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

巻号頁・発行日

vol.2013-AL-145, no.3, pp.1-8, 2013-10-30

---

論理関数の CNF が与えられるとき,その論理式を表す二分決定グラフ BDD を構築するための新しい手法を提案する.CNF は従来から用いられている論理関数の伝統的な表現法の一つである.BDD には論理関数を操作するための様々な演算が備わっているので,CNF よりも BDD を用いる方が適切な多くの問題がある.しかし,CNF から BDD の構築は自明な計算ではない.本稿では,まず CNF を表す中間表現を計算し,それから BDD に変換する二段階の BDD 構築法を提案する.さらに,提案法で中間表現として用いられるデータ構造は,BDD 構築だけでなく,有向グラフ上の列挙問題など様々な問題に対して有用であることも示す.

著者

大戸 康紀

雑誌

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

巻号頁・発行日

vol.2020-AL-180, no.23, pp.1-10, 2020-11-18

---

本論文では,NP 完全問題の一つである k-Clique 問題の最適化バージョンである最大クリーク問題が多項式時間で解けることを証明します.入力グラフ G を辺に有理数の重みを持つ Undirected graph へ拡張します.すべての辺が重み 1 であり,すべての頂点が他の頂点との間に辺を持つ Subgraph をクリークとします.最大クリークの一つを多項式時間で抽出するアルゴリズムを構成する上で必要な証明を行うとともに,そのアルゴリズムを擬似コードの形で与えます.Adjacency matrix の -1 以下の固有値の個数を km(G) とすると,Cauchy Interlacing Theorem により最大クリークの頂点数 k は km(G) +1 以下となります.アルゴリズムでは,km(G) の変化を用いて,頂点を削除したときに最大クリークサイズを変化させない頂点を削除していきます.このアルゴリズムの計算量は O(n8) です.この結果は complexity class NP と P が同じであることを示しています.

著者

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

雑誌

研究報告アルゴリズム(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 通りであることを初めて明らかにした.本稿ではその計算方法について述べる.