著者

角 浩二 田中 寿俊 榎原 博之 中野 秀男

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1994, no.82, pp.57-64, 1994-09-21

被引用文献数

2

---

近年,コンピュータ技術の発展により,その用途は多様化している。その中の一つに、点と線であらわされる図形をグラフとしてモデル化し、描画させるという用途がある。一般のグラフの描画では、「見やすさ」の基準を考える必要があるが,各個人の主観による部分があり、簡単には「見やすさ」の評価をすることは出来ない。そこで本報告では、グラフの「見やすさ」に対する一般的な基準を考え、定量的に評価することを試みる。さらに、一般グラフを描画する、スプリングモデルに基づいた2つのアルゴリズムとそれらの改良版について、描画したグラフから各アルゴリズムを定量的に評価する。Recently, the applications of computer have increased because of the developing of computer technology. Graph drawing is in one such applications, where graphs are modeled as pictures represented by points and lines. General graph drawing problems involve aesthetics, that is difficult to evaluate because aesthetics depends on an individual view. In this paper, the general aethetics standards are represented quantitatively. Moreover, two general graph drawing algorithms based on spring model, and their revised algorithms are evaluated.

著者

稲垣 宏 杉原 厚吉

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1994, no.26, pp.41-48, 1994-03-17

被引用文献数

1

---

筆者らは,文献[1][2]において,位相構造を優先することで数値的安定化を図った3次元Voronoi図構成法を提案した.また,文献[3]では,このアルゴリズムを利用して,双対図形である3次元Delaunay図を生成する方法を提案した.本稿では,位相構造を優先させたVoronoi図構成法が,制約つきDelaunay図の構成にも利用できることを示す.ここで提案する算法では,制約を満たすように数値判定をねつ造しているために,正しいボロノイ図は出力されない.しかし,その双対を求めると,制約つきDelaunay図になっているのである.また,本算法を適用した3次元の制約つきDelaunay図構成プログラムを作成し,計算機実験により,その有効性を実証した.In our previous paper[2], we proposed a numerically robust algorithm for constructing the three-dimensional Voronoi diagram. In this paper, we show that this algorithm can be applied not only to the construction of the ordinary Delaunay triangulation but also to the construction of the constrained Delaunay triangulation. In order to construct the constrained Delaunay triangulation, we invent numerical results on the way to the construction of the Voronoi diagram in such a way that they satisfy the constraints. Moreover we implemented the algorithm as a computer program, and verified the validity of the algorithm by computational experiments.

著者

阿久津 達也

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1993, no.88, pp.27-34, 1993-10-01

被引用文献数

1

---

文字列の近似マッチング・アルゴリズムとしてLandauとVishkinによるアルゴリズムが良く知られている。本稿では彼らのアルゴリズムを基に開発した、Don't Care記号付き文字列に対する逐次および並列の近似マッチング・アルゴリズムを示す。なお、nをテキスト文字列の長さ、mをパターン文字列の長さ、Σを文字集合、kを許容誤差とした場合に、逐次アルゴリズムはO(√<km> n log|Σ|log^2 m/k log log m/) 時間で動作し、並列アルゴリズムはCRCW?PRAM上でO(√<m/k> n log|Σ|log m/k log log m/)個のプロセッサを用いてO( log )時間で動作する。さらに、より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す。This paper presents parallel and serial approximate matching algorithms for strings with don't care characters. They are based on the approximate string matching algorithm developed by Landau and Vishkin. The serial algorithm works in O(√<km> n log|Σ|log^2 m/k log log m/k) time and the parallel algorithm works in O(k log m) time using O(√<m/k> n log|Σ|log m/k log log m/k)processors on a CRCW-PRAM, where n denotes the length of a text string, m denotes the length of a pattern string k denotes the maximum number of differences and Σ denotes the alphabet (i.e. the set of characters). Several extensions of algorithms are described, too.

著者

桜井 裕邦 今井 桂子

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1999, no.26, pp.47-52, 1999-03-15

参考文献数

9

---

本稿では3次元における凸多面体の表面に沿った近似最短経路問題に対し,HershbergerとSuriの2倍近似アルゴリズム[5]を計算機実験にて評価をおこなう.ChenとHanはO(n^2)時間で正確な距離を見つけるアルゴリズム[3]を示した.また,近似最短経路問題においては,単純なO(n)時間での近似アルゴリズムが[5]にて提案され,そのアルゴリズムは最適な距離の高々2倍の距離を与える.本稿ではこれらのアルゴリズムを実装し,理論値と実際の性能との比較をおこなう.In this paper, we consider the shortest path problem between two points on the surface of a convex polytope in three dimensions. Chen and Han presented an algorithm for determining the exact shortest path in O(n^2) time. For the approximate shortest path problem, a simple O(n) approximation algorithm are proposed in [5], and the algorithm produces a path of length at most 2 times the optimal. We implement these alogorithms and compare their theoretical and practical performances.

著者

関根 京子 今井 浩

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.100, pp.25-32, 1996-10-17

---

ネットワーク信頼度計算の問題は,一般に#P完全な問題で,大規模ネットワークの信頼度を厳密に実用的時間内で求めることは難しいと思われている.そのため,近似解法として,信頼度の上限下限を多項式時間で求めること,またモンテカルロ法で確率的に近似解を求めることが考えられてきた.後者について,計算量・アルゴリズム理論的観点から,近年,ランダム化(andomizatio)を用いたランダム化FPTAS (andomized Fully Polynomial?Time Approximation Schem)が開発されている.一方,関根,今井は,BDDを援用したネットワーク信頼度の厳密求解法を提案している.本稿では,ネットワーク信頼度計算に対するランダム化FPTAS解法(モンテカルロ法)とBDDを援用する厳密解法の2つについて,後者で得たある程度大きいグラフの厳密な信頼度関数とモンテカルロ法で得た値の比較などを行ない,両者の種々の場面での性質について論じる.Computing the network reliability is a #P-complete problem, and is believed hard to solve if the problem size is large. Recently, randomized fully polynomial-time approximation schemes for computing the network reliability have been developed by Alon, Frieze, Welsh [1] and Karger [15]. There are also proposed several enhanced Monte Carlo methods which utilize lower and upper bounds for the reliability, etc. On the other hand, Sekine and Imai [24] propose an exact approach based on BDDs. By this method, the reliability of a moderate-size network can be computed rigorously. They also present a polynomial-time algorithm for the case of complete graphs. This paper performs compurational experiments, and discusses features of these methods.

著者

金子 美博 谷口泰一

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.109, pp.9-15, 2004-11-05

---

ネットワーク構造のシステムにおいて,ある頂点のbetweenness値は,他の2頂点間の最短路に,その頂点がどの程度深く関わっているかを示す尺度の一つである.一般的に,全点対最短路問題を解けば,頂点数nのグラフに対して,O(n3)でbetweenness値は容易に求められる.本報告では,無向の区間グラフを扱う.考察の結果,そのようなグラフでの1個の頂点のbetweenness値をO(n)で求めるアルゴリズムを提案する.In a network system, the betweenness of a vertex is one of measures that shows how deeply that vertex relates to shortest paths between other vertices.Generally,based on all pair shortest path algorithms,we can easily obtain all betweenness for graphs with n vertices in O(n*n*n) time complexity. In this report, we deal with betweenness of vertices on undirected interval graphs.We propose an O(n ) algorithm to calculate betweenness of one vertex on such graph with n vertices.

著者

田村慶一

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.24, 2008-03-07

---

ウェブログ(ブログ)の登場によりウェブに関する深い知識を持たない人々も容易に情報を発信できるようになっている.プログは個人の意見を反映したものが多く,世の中の動きを知る上でブログのデータから有益な知識を発見することが重要な課題となっている.特に,ブログは膨大なテキストデータだけではなく,データ同士がトラックバックやリンクなどにより"つながり"を持つことに特徴があり,この"つながり"に着目した解析が必要となる.本研究では,時系列ブログデータの "つながり"(ブロガー同士のつながり)から作成されるグラフ集合に着目し,データマイニングの技術を応用して,グラフの集合から有益な知識を取り出すことを研究の目的としている.具体的にはブログのトラックバックが形成するグラフ集合に焦点を当て,このグラフ集合から頻出かつ重複を許したコミュニティを発見する手法の開発を行ってきた.頻出なコミュニティとは,ある一定期間ごとに発生するグラフの中で,頻出する部分グラフであり,特定の話題を頻繁に扱っているブロガー群といえる.そのようなプロガー群を発見することは,ブログ検索クチコミ情報の信頼性の向上やブロガーヘの情報推薦などへの応用が期待することができる.本発表では 時系列ブログデータから頻出するコミュニティを抽出する方法,重複を許すコミュニティ抽出法とコミュニティ抽出法の高速化手法を説明するとともに,評価実験の結果などを示す.

著者

川村 聡明 玉木 久夫

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.25, pp.41-48, 2001-03-12

参考文献数

5

---

与えられた囲碁の局面に対して、最善の着手とその帰結を正確に求めるアルゴリズムを設計・実装した。この実装は、5×5盤の終盤問題集(福井正明八段:「五道盤上達法」)の問題のうち、30問を、10秒から29561秒の間の時間で解く。ルールは中国ルールに基づき、無限のゲームを無勝負と解釈する。We design and implement an algorithm that rigorously computes the best move and its outcome given a board configuration of GO game. Our implementation solves 30 of the 5×5 board endgame excersizes authored by Fukui in from 10 to 29561 seconds. Our rule is based on the Chinese rule and interprets an infinite game as a void.

著者

定兼 邦彦

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.84, pp.73-80, 2000-09-21

---

全文検索のための索引である接尾辞配列は,他の全文検索索引と比較すると省スペースであるが,転置ファイルのような単語索引と比較するとサイズが大きい.この問題を解決するために圧縮接尾辞配列が提案されたが,検索にはテキスト自身も必要であるため,索引サイズはテキストよりも小さくならない.本稿では圧縮接尾辞配列を用いた検索アルゴリズムを,テキスト自身が不要になるように変更する.また,テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する.これにより,テキストの圧縮と高速な検索の両立が可能となる.A compressed text database based on the compressed suffix array is proposed. The compressed suffix array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the text itself that occupies O(n log|Σ|) bits for the alphabet Σ. On the other hand, our data structure does not use the text itself, and supports important operations for text databases: inverse, search and decompress. Our algorithms can find occ occurrences of any substring P of the text in O(|P|log n + occ log^ε n) time and decompress a part of the text of length l in O(l+log^ε n) time for any fixed 1 > ε > 0. Our data structure occupies only 1/εnH_0 + n(6+3logH_0)<log^εn>/<log^εn-1>+2n+|Σ|log|Σ|+o(n) bits where H_0〓log|Σ| is the order-0 entropy of the text.

著者

定兼 邦彦 宋永健 姚兆明 林徳華

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.115, pp.19-26, 2001-11-27

---

文字列検索のための索引として接尾辞配列が有名であるが,そのサイズが問題となっている.圧縮接尾辞配列はそれを圧縮したもので,通常は元の文字列よりもサイズが小さくなる.ただし圧縮接尾辞配列を構成するアルゴリズムとしては一旦接尾辞配列を構成するものしか存在しないため,一時的だが大量のメモリが必要となる.本研究では長さ n の文字列に対し,$O(n)$ ビットの一時記憶を用いる O(n|Σ|log n)$ 時間 (|Σ|はアルファベットサイズ)のアルゴリズムを提案する.このアルゴリズムは短い文字列に対する圧縮接尾辞配列から長い文字列に対するものを徐々に作成するものになっており,データの追加を容易に行える点も利点である.Though the suffix array is now famous as an index for string matching, it has a problem of its size. The compressed suffix array is a compressed version of the suffix array whose size is usually smaller than the size of the string. However all known algorithms construct the compressed suffix arrays via uncompressed suffix arrays, which temporarily occupy huge amount of memory. This paper proposes an O(n|Σ| log n) time algorithm to construct a compressed suffix array of a string of length n on alphabet Σ using only O(n) bits temporal space. This is an incremental algorithm, which construct the compressed suffix array of a concatenation of a character and a string from that of the string. Therefore this algorithm also has the merit of appending data quickly.

著者

伍偉鴻 二村 良彦

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.5, pp.73-79, 2000-01-17

---

現在,実際的に最速と考えられている整列法はBentleyのQuicksort(BQ法)である.本稿では,整列済みに近いデータに対してはBQ法の約2倍高速であり,かつ一様乱数列に対してもBQ法よりも高速な整列法LOAS (Leaves Optimal Adaptive Sort)の2つの実現法について報告する.一つは高速であるがスペースをO(N)要し、もう一方は性能は多少落ちるが、スペースをO(√<N>)要するものである。LOASは,数列の葉(数列において自分より小さい隣接要素を持たない要素)の数について最適な整列法である.即ち,数列の長さと葉数を各々Nおよびmとすると,LOASはO(N log m)時間で整列を完了する.実用に供されている4つの整列法(BQ法,GNU Quicksort,GNU Merge sort,多重分割ソートMPS)を含むいくつかの整列法と比較することにより,LOASの高速性を示す.Two implementations of LOAS(Leaves Optimal Adaptive Sort) are proposed. One implementation is optimized in running time which needs O(N) extra working space and is faster than the fastest Quicksort known, Bentley's Quicksort, by a factor of 2 in practice, the other needs O(√<N>) extra working space which is more practical but loss in efficiency. LOAS runs in O(N log Leaves) time and is optimal with respect to the presortedness measure Leaves which is the number of elements smaller than their neighbors in a given sequence. Evaluation of LOAS together with four other sorting algorithms (Bently's Quicksort, GNU Quicksort, GNU Merge Sort and Multi Partition Sort MPS) is conducted to show the efficiency of LOAS.

著者

宮澤 雅史 曽培峰 磯 直行 平田 富夫

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.103, pp.43-49, 2002-11-08

---

ユークリッド距離変換はパターン認識やモルフォロジーフィルターなど画像処理の様々な分野で応用されている。本論文ではユークリッド距離変換のための、シストリックアレイを用いたハードウェアアルゴリズムを提案する。計算時間の効率化と乗算器などのハードウェア資源を削減するための工夫をし、サイズ$N ?times N$の2値画像に対しクロック数$3N-1$でユークリッド距離変換処理を実行する。そのために必要なハードウェア量は$O(N^2)$である。The Euclidean distance transform is applied in various fields of image processing, such as pattern recognition and morphological filter.In this paper, we propose a hardware algorithm using a systolic array that performs Euclidean distance transform. It is designed so that hardware resources, such as multipliers and comparators, are reduced and processing speed is efficient. It performs Euclidean distance transform for an input of $N \times N$ binary image in $3N-1$ clocks, and the size of the required hardware resources is $O(N^2)$.

著者

結城 匡人 徳山 豪

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.53, pp.9-16, 2003-05-23

---

地図製作やコンピュータグラフィックスの分野では、曲線を表現するのに、その上のサンプル点の列を使用するが、データ量を圧縮するために、曲線の単純化が必要となる。多角形曲線を単純化する近似アルゴリズムとして、Frechet distanceを利用したFrechetSimp法を使用し、二分探索法を用いて、O(nlog n)で計算できる。FrechetSimp法を実装し、複雑に折れ曲がった曲線でも、その特徴を残したまま単純化できることを紹介する。FrechetSimp is an approximation algorithm for that applies the concept of Frechet distance. The algorithm is based on binary search and its complexing is O(n log n). We implement this algorithm and report some experimental results.

著者

奥田 剛 井上 克司 井上敦之 伊藤暁

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.110, pp.17-24, 2005-11-11

---

Pシステムは、生物学上の特徴をもつセルを用いた並列計算モデルであり,本論文ではこのモデルを利用した1つの触手をもつ通信機能のあるPシステムを取り上げる.これをCommunicating P System with One Tentacle (1CPST)と呼ぶ.研究では、次の結果を示す.意の有限オートマトンMが与えられたとき Mが受理する言語L(M)を受理するような1CPSTを構成する方法.T ={0}なる入力テープ集合は深さ2の1CPSTでは受理できるが 深さ1の1CPSTでは受理できない.意の正則表現が与えられたとき その正則表現を表す言語を直接受理するような深さ2の1CPSTを構成する方法.P system is a parallel computing model that uses the cell having the biological feature. This paper investigates the P system that has the communicating function with one tentacle, called Communicating P System with One Tentacle (1CPST). In this study, the following results are obtained. A method of constructing a 1CPST that accepts the same language as that of arbitrary finite automaton. It is impossible for 1CPST's of depth 1 to accept the set T = {0}, which can be accepted by a 1CPST of depth 2. A method of constructing a 1CPST of depth 2 that directly accepts the languages expressed by arbitrary regular expressions.

著者

萩原 洋一 池田 諭 中森 眞理雄

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1999, no.33, pp.33-40, 1999-05-10

---

マージソートは時間計算量がO(n log n)(nはソートされるレコードの個数)であり高速であるが,内部ソートとして実行する場合,作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では,作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量はO(n log^2 n)であり,従来のアルゴリズムより悪いが,これは作業場所とのトレードオフの結果である.Mergesort is one of the fastest sorting algorithm, since it requires only O (n log n) of computing time. Mergesort, however, requires an array of size n as working area, when executed as an internal sort. In the present paper, we propose an algorithm which is a modified version of mergesort. The space complexity of the proposed algorithm is only O. The time complexity is O (n log^2 n), which is worse than the existing merge sort and is the result of the tradeoffs between time and space complexities.

著者

森田 昭広 古賀 久志 渡辺 俊典 横山 貴紀

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.30, pp.49-54, 2006-03-17

---

グラフのマッチング問題は一般に計算量が膨大であるが,問題固有の属性情報などを用いて効率的な探索を実現できる可能性がある.本研究では,グラフマッチング問題が入力2グラフから生成される積グラフの最大クリークを抽出する問題へ還元できることに着目し,その効率化のために2つの属性情報利用アルゴリズムを考案した.1つ目はクリーク抽出の探索過程で属性情報を用いて探索領域を削減する方法,2つ目は積グラフの生成時に属性情報を用いて積グラフの規模自体を抑制する方法である.これらを計算機実験によって比較検証した結果,双方共に有効であるが,特に後者の有効性が顕著であることを確認した.Graph matching problem has a very high computational complexity. But we can reduce it by exploiting domain-specific information such as object's attributes. In this research, where we solve the graph matching problem by reducing it into a maximum clique problem in a product graph generated from the two input graphs, we propose two algorithms, both exploiting attribute information. One is the method of decreasing the search space by using attribute information in the process of maximum clique search. The other is the method of decreasing the size of the product graph by using attribute information during the product graph generation. Through experiments we showed that, although both are effective, the latter dominates the former.

著者

内田 次郎 MuzahidulA.K.MIslam 稲葉 直貴 片山 喜章 陳慰 和田 幸一

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.49, pp.33-40, 2006-05-18

---

センシング機能、通信機能を備えた小型センサーデバイスから構成されるネットワークをセンサーネットワークという。センサーネットワークに対し、"オーバーヘッドやエネルギー消費量の最小化"などの利点を持つアーキテクチャの構築方法としてクラスタリングが挙げられる。本研究では、[2]で提案されているアーキテクチャが持つ望ましい性質を維持しつつ改良を加え、タスクの完了時間やその拡張などの面においてよりよい性質を持った三つのアーキテクチャおよびそのメンテナンスのためのアルゴリズムを提案する。A sensor network is a collection of transmitter-receiver devices (referred to as nodes). Clustering is seen as the step to provide the flat sensor network topology with a hierarchical architecture with properties such as minimizing communication overhead and minimizing the overall power consumption. In this paper we improve the architecture [2] maintaining the desirable properties and propose three architecture and maintenance algorithms which has the better properties about the completion time of tasks, expansions of tasks, and so on.