並列タイトル等Development of Geometric Clustering Algorithms and Applications to VLSI Design
タイトル（掲載誌）平成2(1990)年度 科学研究費補助金 一般研究(C) 研究成果報告書概要 = 1990 Fiscal Year Final Research Report Summary
一般注記金沢大学 / 大阪電気通信大学
本研究では、最初に対毎に類似度が与えられたとき、距離が類似度に反比例するように対象を2次元の平面に写像する方法について考察し、主軸変換法がこの目的に適していることを確かめ、実際にプログラムを作成した。次に平面に与えられた多数の点に対して、最も一様に点が分布するようにこれらを直線上に写像する問題について考察し、従来の結果を非常に改善する結果を得た。本研究では平面上分点集合を2分割する問題を主に考察したが、そのままの形で扱うよりも双対平面上で考えた方が見通しがよい。実際、点を直線に、直線を点に変換すると、点集合は直線の集合に変換されるが、同じ分割を与える直線に対応する点は直線で区切られた同じ小領域に属するので、小領域を全て調べれば全ての(直線による)分割を調べたことになる。そのためにそれらの小領域を順序よく訪問する算法が必要になるが、従来は効率のよいものがなかった。本研究で開発した算法は、直線の本数に比例する記憶量さえあれば小領域の個数に比例する時間で探索を終えることができるので非常に効率がよい。本研究で開発された算法はVLSIの設計に応用することができる。実際、回路分割問題に適用した結果を論文の形にまとめ、近く投稿する予定である。この論文では、VLSIを構成するブロックとブロックを結ぶネットの集合が与えられたとき、ブロックの集合を2分割して2つの部分にまたがるネットの本数を最小にする問題について論じる。従来の方法はグラフ理論を用いていたが、いずれも定式化の段階ですでに問題を含んでいた。これに対して、本研究ではブロック間の接続度を計算した後、その情報に基づいて密接に連結されているブロックは近くに配置されるように写像を施す。その後で幾担学的変換法によって点を直線に変換し、トポロジカルウォ-クの算法を利用して最適な分割を求める。
Grouping similar objects is called cluster analysis. There have been considered a lot of algorithms. When we formulate this problem as a problem in Graph Theory, it may often become NP-complete. Therefore, we rely on heuristic algorithms. In this research we first presented an algorithm for mapping objects into points in the plane so that similar objects are placed closely, based on Principal Coordinate Analysis. Then, applying Geometric Transform, points are mapped into lines. Using Topological Walk Algorithm developed in the research, we can examine all possible regions defined by those lines. This corresponds to examination of all possible partitions of those points in the dual plane. The idea was applied to Circuit Partitioning in VLSI design.
研究課題/領域番号:01550295, 研究期間(年度):1989 - 1990
出典：「幾何学的クラスタリング算法の開発とVLSI設計への応用」研究成果報告書 課題番号01550295（KAKEN：科学研究費助成事業データベース（国立情報学研究所）） （https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/）を加工して作成
一次資料へのリンクURLhttps://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55709&item_no=1&attribute_id=26&file_no=1
関連情報https://kaken.nii.ac.jp/search/?qm=90113133
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-01550295/
https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-01550295/015502951990kenkyu_seika_hokoku_gaiyo/
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）