著者

二村 良彦 二村 夏彦 遠藤貢一 平井 利治

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.32, pp.5-12, 1995-03-17

被引用文献数

4

---

数列が整列されている度合を表す事前整列性測度Leaves(葉数),および事前整列性のよい数列については高速にソートをする適応整列法LOASとその実現法について報告する.LOASはまず与えられた数列を葉数個の区間にO()時間で分割し,次にそれをO( log葉数)時間でマージする整列法である.本稿ではまず葉数とLOASを定義し,次にLOASがLeavesに関して最適であることの証明を与える.最後にLOASの実現法およびその他の適応ソートや実用的なQUICKソート,MERGEソート等との性能比較結果を示す.We propose a new presortedness measure leaves and a new sorting algorithm LOAS (Leaves Optimal Adaptive Sort) which is optimal with respect to the measure. LOAS divides a given sequence X into Leaves (X) sorted subsequences in O(n) time. Then it merges the sequences in O(n log Leaves(X)) time. Implementation techniques and proof of the Leaves-Optimality of the algorithm are described. In order to prove that LOAS is an efficient sorting algorithm, we have conducted systematic evaluation of several sorting algorithms including Quicksort, merge sort, Skip sort and MEL sort.

著者

川口 喜三男 呉敬軍 和田 幸一

出版者

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

雑誌

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

巻号頁・発行日

vol.1993, no.48, pp.119-126, 1993-05-28

---

一定の面積の自動倉庫を十分利用するためにより多くの部品を保管し,かつ効率よい出荷作業が要求されている.それを実現するために,平面自動倉庫に置ける荷台の移動操作の最小歩数についての研究がなされている.本論文は,未だ解決されていない三つの空位を持つN×M(≧)平面自動倉庫において任意の位置にある荷台を自動倉庫の出口まで移動するのに要する最小歩数関数を決定する.又,M=2の場合の最小歩数関数は一般の場合の解においてM=2と置く事によっては解は得られないので,M=2の場合に対して最小歩数関数を別個に決定する.The minimum number of sliding operations (steps) for moving a palette in an automatic warehouse was considered. In this paper, we consider the function of the minimum number of steps for a palette at any position in the aotumatic warehouse of size N×M(M≧2) with three spaces to be moved to the exit of the automatic warehouse.

著者

伍偉鴻 二村 良彦

雑誌

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

巻号頁・発行日

vol.2000, no.5(1999-AL-071), 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の高速性を示す.

著者

安田 覚 阪本 清和 中野 秀男

雑誌

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

巻号頁・発行日

vol.1990, no.58(1990-AL-016), pp.15-21, 1990-07-16

---

離散最適化問題に用いられる近傍探索法の良さの推定を、近似解を探索している途中で得られるデータから確率的に推定する方法について考察する。本報告では対象とする問題とその近傍探索法として、巡回セールスマン問題とλ最適法を取り上げる。50都市程度の問題例での計算結果から、あらかじめ最適値を予測した上での推定法が近似解の出現頻度推定に有効である事を確かめた。

著者

慶祐 俊文 高藤 大介 田岡 智志 渡邉 敏正

雑誌

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

巻号頁・発行日

vol.2006, no.7(2006-AL-104), pp.67-74, 2006-01-20

---

最小費用流問題とは,「有向グラフG(V E)と各辺(i j)∈Eに対する単位フローあたりの非負整数コストc(i j),各辺に流すフロー上界値の非負整数容量u(i j)及び始点から終点に流す最大フローkが与えられたとき,流量がkでありかつ,各辺に流れるフローf(i j)とコストc(i j)の積の総和で求められるz(f)が最小であるフローfを求めよ」と定義される.本問題は輸送計画問題などに広く応用され,本問題を高速に解くことは重要である.本稿では,最小費用流問題における既存解法アルゴリズムの性能を計算機実験により評価を行い,RELAXが最も高速な解法であることを示す.

著者

池田 崇博 今井 浩 西村 茂樹 下浦 弘 橋本 武夫 天目 健二 三藤 邦彦

雑誌

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

巻号頁・発行日

vol.1994, no.69(1994-AL-040), pp.89-96, 1994-07-22

---

最短路問題は、あらゆる分野での応用が考えられる最も基本的な問題の1つであり、近年急速に普及しつつある経路誘導システムとも深いつながりを持っている。本研究では、2点間の最短路問題に関して、ダイクストラ法・A^*・アルゴリズム・両方向探索といった従来のアルゴリズムを概観し、新しい手法に基づくA両方向探索アルゴリズムを提案する。また、実際の道路網のデータにこのアルゴリズムを適用した結果を基に、実際の効率及び特徴について論じる。

著者

八登 崇之 瀬田 剛広

出版者

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

雑誌

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

巻号頁・発行日

vol.2002, no.103, pp.9-16, 2002-11-08

---

問題?に対する別解問題(ASP)というのは、?のインスタンスxとそれに対する1つの解sが与えられた時に、xのs以外の解を求める問題のことである。(新しい問題クラスとしてのASPの概念はUedaとNagaoによる。)本論文ではn個の解が与えられたときにもう1つの解を求める問題(n-ASP)について考察する。特に、対応する解への変換も多項式時間で行えるような多項式時間parsimonious還元に関する完全性であるASP完全性について考察する。応用として、本論文では3つの有名なパズル、スリザーリンクとカックロ(クロスサム)とナンバープレース(数独)についてそのASP換算製(NP完全性を含意する)を示す。The Another Solution Problem (ASP) of a problem II is the following problem: for a given instance x of II and a solution s to it, find a solution to x other than s. (The notion of ASP as a new class of problems was first introduced by Ueda and Nagao.) In this paper we consider n-ASP, the problem to find another solution when n solutions are given. In particular we consider ASP-completeness, the completeness with respect to the parsimonious reductions which allow polynomial-time transformation of solutions. As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place.

著者

チャンドラバルン ハルダースソンマグナス

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.32, pp.69-76, 1995-03-17

参考文献数

12

---

散乱問題は,点の集合を可能な限り互いに離して配置する問題である.この問題は,施設の位置の選定や経営決定学の分野に,多くの応用をもつ.現在までの重要な研究は,二つの特定の散乱の尺度に着目してきている.我々は,現実の問題に動機づけられ,いくつかの自然な遠隔の尺度を導入し,考察する.そして,自明でないパーフォマンスの境界をもつ,最初のアルゴリズムを示す.Dispersion problems involve arranging a set of points as far away from each other as possible. They have numerous applications in the location of facilities and in management decision science. Must work to date has focused on two particular measures of the dispersion. We study and introduce several natural measures of remoteness, motivated by real-life problems, and present the first algorithms with non-trivial performance bounds.

著者

大芝 猛

雑誌

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

巻号頁・発行日

vol.1991, no.69, pp.1-9, 1991-07-22

---

1階術語論理の論理式Aが妥当性を肯定的に検証されるとき得られるguide情報を利用するならば,証明図(型)を試行錯誤なくかき上げるアルゴリズムをすでに提示下が、更に人間の理解しやすい証明形式(等)へ変換するアルゴリズムを連結し,自然な証明を一貫した自動証明手続きで得ることへのアプローチを問題とする。このとき完成した前者に続き,後者のLK→NK変換の結果が内容的にも自然なものとするため,まずLKから(+排中律)体系への変換を行うアルゴリズムを提示した。LKの推論の要素はA_1<&・・・&>A_m&xrArr;B_1^<or・・・or>B_nの意味をもつsequent形式で,右辺がn&ge;2のとき理解しにくい。これを右辺がn&le;1のLJ型sequentからなる証明図に一たん分解し,排中律の拡張を用いて再び結合することによりアルゴリズムを実現したが,このとき,人間の証明としても自然な三段論法が導入される。A Convert algorithm LK to (LJ+excluslve middle) and its application to automatic theorem proving are discussed. In LK system, inference rules for sequents of the form A_1,・・・,A_m→B_1,・・・,B_n(n&le;2) is different from human reasonig. In fact, it is difficult to translate directly LK-proofs into proors on natural deduction system such as NK. Then we present an algorithm which converts an arbitrary LK-proof to a proof which consists of LJ-sequents whose right side has at most one formula. In application of this algorithm, decreasing process of the number of right side formulas, derives naturally syllogisms whose cut formulas are generalized exclusive middles.

著者

林 達也 中野 浩嗣 オラリウステファン

出版者

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

雑誌

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

巻号頁・発行日

vol.1996, no.89, pp.23-30, 1996-09-13

参考文献数

19

---

要素数が合計がnのソートされたk個の列をマージして新しいソート列を求める問題をkマージ問題と呼ぶ。本論文では、単純で仕事・時間量が最適な3つのPRAM上のkマージ問題を解くアルゴリズムを示す。まず、EREW?PRAM上で、O(og )時間で仕事量がO( log )のkマージアルゴリズムと、CREW?PRAMとCRCW?PRAM上でO(oglog n+log )時間で仕事量がO( log )のkマージアルゴリズムを示す。また、これらのアルゴリズムが仕事量がO( log )である限り、高速化はできないことを示す。The k-merge problem, given a collection of k,(2〓k〓n), sorted sequences of total length n, asks to merge them into a new sorted sequence. The main contribution of this work is to propose simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models. Our k-merge algorithms runs in O(log n) time and performs O(n log k) work on the EREW-PRAM. and in O(loglog n+log k) time and O(n log k) work both on the CREW-PRAM and on the CRCW-PRAM. We also prove that the computing time of these algorithms cannot be improved provided that the amount of work is bounded by O(n log k).

著者

Boris Aronov 浅野哲夫 菊地洋右 SubhasC.Nandy 笹原 慎司 宇野 毅明

出版者

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

雑誌

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

巻号頁・発行日

vol.2005, no.26, pp.63-69, 2005-03-17

参考文献数

2

---

n×nの行列に整数0 ... n2-1を配置し、どの行和、列和も等しいものをsemimagic squareとよばれる。ここでは列和、行和のかわりにk×kの部分行列に含まれる要素の和を考え、この和が等しいn×n行列をzero k×k-discrepancy matrixとよぶ。そしてこのような行列はkとnがともに偶数であるとき存在し、kとnが互いに素であるとき存在しないことを示す。さらに、k m●2を整数としたときn=k*であるならばzerok×k-discrepancy matrix の存在がいえる。このzero k×k discrepancy matrixの恒星にはconstant-gap matricesを用いる。また、constant-gap matricesの特徴づけを行なう。A semimagic square of order n is an n×n matrix containning the integers 0,...,n2-1arranged in such a way that each row and column add up to the same value.We generalize this notion to that of a zero k×k-discrepancy matrix by replacing the requiremento tha the sum of each row and each column be the same by that of requiring that the sum of the entries in each k×k square contiguous sub matrix be the same.We show that such matrices exist if k and n are both even,and do not if kand n are are relatively prime.Further,the existence is also guaranteed whenever n=k ●,for some integers k,m●2. A class of matirices,called constant-gap matrices plays an important role.We give a characterization of such matrices.

著者

山下 慶子 浅野 孝夫

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.31, pp.33-40, 2000-03-21

被引用文献数

1

---

配送計画問題は近年活発に研究されている問題で,経済活動のさまざまな状況でおこる.この問題には幾つかの種類があり,容量kの巡回路被覆問題,容量kの配送巡回路問題,電話予約送迎問題などがその代表例である.本稿では最も一般的な枠組での配送計画問題である容量kの配送巡回路問題の代表的なアルゴリズムを実装し,その実際的性能を評価する.さらに,複数デポーの配送計画問題に対する近似アルゴリズムを提案する.このとき従来の目的である配送に要する総距離最小という指標から少し離れ,現実的に乗組員の仕事量均等化を考慮に入れることも試みる.そして配達時間帯指定の配送計画問題にも取り組み,ベンチマークデータを用いて計算機実験を行い,提案するアルゴリズムの実際的性能評価を行う.The vehicle routing problem has received much attention in recent year and occurs in many practical settings. There are several variants of this problem: the k-tour cover problem, the k-delivery TSP and the dial-a-ride problem or stacker crane problem. In this paper, we try to evaluate the practical performances of representative algorithms for the k-delivery TSP. Furthermore, we propose approximation algorithms for the multi-depot vehicle routing problem and the vehicle routing problem with time windows and evaluate their practical performances through the computational experiments based on bench-mark data.

著者

山中 克久 川野 晋一郎 菊地 洋右 中野 眞一

雑誌

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

巻号頁・発行日

vol.2006, no.7(2006-AL-104), pp.27-34, 2006-01-20

---

本文では 正の整数 n の整数分割を列挙するアルゴリズムを与える.この問題は 組み合わせ論において基本的な問題の1つであり 長い間 広く研究されてきた.これまで 整数分割1つ当たり平均定数時間で列挙する方法しか知られていなかった.我々は 与えられた整数の整数分割を 最悪でも1つ当たり定数時間で重複なく列挙するアルゴリズムを与える. また 条件付きの整数分割を定数時間で列挙するアルゴリズムをいくつか与える.

著者

塩浦 昭義 徳山 豪

出版者

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

雑誌

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

巻号頁・発行日

vol.2004, no.76, pp.43-50, 2004-07-27

---

本稿では、二項木モデル上でのヨーロピアンアジアンオプションの価格付けに対する効率的かつ正確な乱択近似アルゴリズムを提案する。nステップの二項木上での行使価格Xのオプションと任意の正整数kが与えられたとき、我々のアルゴリズムはnに依存しない誤差O(X/k)の範囲の近似値をO(kn^2)時間で求める。我々のアルゴリズムはAingworth Motwani および Oldham (2000) による近似アルゴリズムを乱択アルゴリズムへ修正したものであり、近似精度を理論的にも実用的にも改善している。We propose an efficient and accurate randomized approximation algorithm for computing the price of a European-Asian option on the binomial tree model. For an option with the strike price X on an n-step binomial tree and any positive integer k, we give an O(k n^2) time algorithm with the error bound O(X/k) which is independent of n. Our algorithm can be seen as a modification of the approximation algorithm developed by Aingworth, Motwani, and Oldham (2000) into a randomized algorithm, which improves the accuracy theoretically as well as practically.

著者

謝旭珍 柳浦睦憲 小野 孝夫 平田 富夫

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.66, pp.31-38, 2007-07-03

---

グラフの均等辺彩色とは,多重無向グラフと色数が与えれたとき,任意の頂点と任意の2色に対して,その頂点に接続する辺のうちそれぞれの色で塗られているものの本数の差が高々2であるような辺彩色である.与えられたグラフの頂点数を$n$,辺数を$m$とし,色数を$k$とする.謝らは,任意の多重グラフを$O(m2/k)$時間で均等辺彩色するアルゴリズムを提案した.本論文では,彼らのアルゴリズムに変更を加え,初期辺彩色をランダムに与える場合の実行時間を解析する.そして,任意の定数$\varepsilon >0$に対し,実行時間が高い確率で$O(n^{1/2} m^{3/2+\varepsilon })$となることを示す.それは,グラフが密で$k$が小さいときには,既存のアルゴリズムよりも速くグラフを均等辺彩色できることを示す結果である.Given a multigraph $G=(V,E)$ with $n$ vertices and $m$ edges and a color set${\cal C}=\{1,2,\ldots,k\}$, the nearly equitable edge coloring is an assignment of given colors to edges in $G$ such that, among the edges incident to each vertex, the numbers of edges colored with any two colors differ by at most two. Xie~et~al. presented an algorithm to solve this problem in $O(m2/k)$ time. In this paper, we investigate the running time of a modified version of their algorithm in which the initial edge coloring is generated randomly. The new time complexity is proved to be $O(n^{1/2} m^{3/2+\varepsilon })$for arbitrarily small constant $\varepsilon >0$with high probability for sufficiently large $n$,which is better than Xie at al.'s original algorithm when the graph is dense and $k$ is small.

著者

金丸 直義 西関 隆夫 浅野 哲夫

雑誌

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

巻号頁・発行日

vol.1992, no.27(1991-AL-026), pp.25-32, 1992-03-23

---

本報告では,与えられた凸m角形内部のすべての整数格子点を列挙するO(+m+log )時間のアルゴリズムを与える.ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである.さらに,m個の制約式を持つ2変数整数計画問題を解くO( log m+log )時間のアルゴリズムを与える.ここでnは計画問題の許容解空間である凸多角形の大きさを表す.このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している.

著者

大西建輔 星 守

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.93, pp.67-74, 2001-09-25

---

確率分布を与えた場合に路長の期待値を最適とする二分探索木 最適木と呼ぶ が二分木の内点数の二乗で計算できることは Kunthによりすでに証明がなされている. 前回の発表では、確率分布のパラメタ空間をそれぞれの最適木に対応する領域に分割する手法について述べた.本稿では、どのような二分探索木でも 最適木となるりうるのか?これらの領域がどのような場合に接するのか?という問題に対して 二分探索木の回転操作を用いた条件を与える.For a given probabilistic distribution, a binary search tree with optimal path length among all trees is called optimal tree. Knuth showed that such a tree is computed in the time of square of the number of nodes of binary search tree. In our previous paper, we showed algorithms that the parametric space of discrete probabilistic distribution is divided into regions corresponding with binary search tree. In this paper, we investigate that any binary search tree can become optimal tree and which two optimal regions are adjacent. Some conditions related with single rotation is showed.

著者

今井 浩

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.79, pp.1-6, 2001-07-27

被引用文献数

1

---

Shannonのエントロピーのもつ離散構造として、同時分布の周辺分布のエントロピーの 集合関数がポリマトロイドとなることが藤重により示されている。本稿では、量子情報理論のvon Meumannエントロピーについて、完全に古典確率の場合を含んだ形でこの 結果が拡張できることを示す。As discrete structure of the Shannon entropy, the entropy of marginal distributions forms a polymatroid, as shown by Fujishige. In this paper, we extend this result for the von Neumann entropy in quantum information theory.

著者

久保 典弘 村本 勝洋 下薗真一

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.84, pp.49-56, 2000-09-21

---

平面上に与えられた点をすべてを通過し最初の点に戻ってくる最も短い巡回路を求める問題の,非常に高速なアルゴリズムについて述べる.本アルゴリズムは非常に単純なアルゴリズムなので実装が簡単である.また,n個の点が与えられたときにO(n log n)時間,O(n)領域で計算を行う.アルゴリズムは,平面を分割し,点をソートして分割領域内の順路を求め,各領域内の順路をつなぎ合わせる構成をとる.ランダムに点が分布するときは確率的に定数近似アルゴリズムである.このアルゴリズムをKarpの分割アルゴリズム,Lin-Kernighanの局所探索,Aroraの近似スキームなどと比較した結果,実行時間は最も速く精度は同じかより良いという結果が得られた.We present a quite simple, fast and practical algorithm to find a short cyclic tour that visits a set of points distributed on the plane. The algorithm runs in O(n log n) time with O(n) space, and is simple enough to easily implement on resource restricted machines. It constructs a tour essentially by axis-sorts of the points and takes a kind of the 'fixed dissection strategy.' We show that the algorithm is a 'probabilistic' constant-ratio approximation algorithm for uniform random distributions. We made computational comparisons of our algorithm, Karp's partitioning, Lin-Kernighan local search, Arora's PTAS, etc. The results indicate that in running time our algorithm overwhelms existing ones, and the average approximation ratio is better or competitive.

著者

藤重 悟 牧野 和久 高畑 貴志 柏原 賢二

出版者

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

雑誌

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

巻号頁・発行日

vol.2001, no.7, pp.51-58, 2001-01-19

---

各辺ベクトルの台の大きさが2以下である多面体のクラスについて考える.このような凸多面体を複基多面体と呼び,頂点をもつ任意の多面体P⊆R^Vについて,次の3つが等価であることを示す.(1) Pが複基多面体である.(2) 台Vの法線ベクトルをもつPの各面は,ある基多面体の反転および軸方向のスケーリングによって得られる.(3) Pの支持関数は,R^Vの各象限上の劣モジュラ関数である.We consider a class of pointed convex polyhedra in R^V whose edge vectors have the support of size at most 2. We call such a convex polyhedron a polybasic polyhedron and show that for a pointed polyhedron P ⊆ R^V the following three statements are equivalent: (1) P is a polybasic polyhedron. (2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes. (3) The support function of P is a submodular function on each orthant of R^V.