著者

藤原 直紀 徳山 豪

雑誌

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

巻号頁・発行日

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

---

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

著者

宇野 毅明

雑誌

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

巻号頁・発行日

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

---

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

著者

大戸 康紀

雑誌

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

巻号頁・発行日

vol.2016-AL-158, no.14, pp.1-7, 2016-06-17

---

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

著者

Amanj Khorramian Tomoko Taniguchi Takeaki Uno Ryuhei Uehara

雑誌

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

巻号頁・発行日

vol.2018-AL-168, no.2, pp.1-8, 2018-05-18

---

Othello, also known as Reversi, is a quite well known strategy board game for two players on a board of size 8 ×8. The set of all reachable patterns is not yet known for this game. In this paper, we finally obtain all reachable patterns on 5 × 6 board by developing nontrivial algorithm on a supercomputer. We observe the scale of complete search-tree is big even for a board of size 5 × 6 and parallelize a distributed frontier search using shared memory to reach the final depth of the tree. To reduce the memory requirement, the tree is horizontally compressed using a novel method, and the frontiers are maintained in a novel data-structure. Moreover, an efficient number system is proposed and utilized for representing the states of the game, and a symmetry of the states is applied during the search. We assume that the board and pattern are rotation symmetry, but we assume that the mirror symmetry gives the different pattern. Eventually, the whole tree is traversed in 2 hours by visiting 257,387,474,170 different states using random access memory shared among 576 processing cores. We aim to find specific font patterns among the states of the final depth. However, 83,175,694 of the states are located at the final depth, at which we start looking for font patterns. Before that, a set of 96 characters of size 6 × 6 is binarized, and their (5 × 6)-compatible patterns are taken for lookup by considering all possible symmetries. In this way, a font of 96 characters is designed.