平面上における近似割当てアルゴリズムの解析

山田　正一郎  原嶋　勝美  笠井　保  

誌名
電子情報通信学会論文誌 A   Vol.J69-A   No.1   pp.1-8
発行日: 1986/01/25
Online ISSN: 
DOI: 
Print ISSN: 0373-6091
論文種別: 論文
専門分野: 基礎一般
キーワード: 


本文: PDF(523.3KB)>>
論文を購入



あらまし: 
平面上で定義される（一次）割当て問題を効率よく解くための近似アルゴリズムの理論的解析について述べる．ここで取り扱う割当て問題の評価関数すなわち割当てコストは，二つの点集合に含まれる点間のユークリッド距離の二乗和とした．本文では，まず，与えられた平面を縦または横に分割する方法に基づいた近似割当てアルゴリズムを示し，次に，点集合が単位正方形平面上に一様分布していると仮定した場合について，このアルゴリズムの平均値解析を行なった結果について述べている．解析の結果，点集合の大きさをn，近似アルゴリズムにおける分割段数をhm，n→∞としたときの平均割当てコストをÎとすると，Îのnに対する増加率はhmが大きくなるにつれて単調に減少すること，また，hmが最大の場合，Îは（1/4）log2nとなることなどが明らかになった．また，理論的解析結果と実験結果との比較検討も行なっている．