权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

動的環境における最適化問題の幾何手法によるアルゴリズムの研究開発

动态环境下优化问题几何方法的研究与开发

基本信息

批准号：
06750072
负责人：
今井桂子
金额：
$ 0.58万
依托单位：
Chuo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06750072/
关键词：
動的計算幾何学最適化問題 Voronoi図

项目摘要

離散的な問題において,その離散構造が動的に変化していくような場合にも最適化問題を解く必要に迫られている.静的な離散最適化問題は以前からその重要性が認識され,積極的に研究がなされてきた.また,静的な場合の線形な最適化問題に対しては,線形計画法に関する多くの研究が古くから行なわれており,様々な有用な研究結果が得られている.しかし,交通量が時間と共に変化していくなかでの最短路問題や,移動体通信などにおいて施設が移動できるような状況での最適施設配置問題のような動的な環境における最適化問題においては,非線形な問題を扱わなければならない場合が数多くあり,そのような問題に対する取り組みは始まったばかりである.そこで,本研究では,動的環境において,非線形な問題に対して,問題の持つ離散構造を詳しく解析し,申請者が研究を行なってきた動的計算幾何学における結果をさらに拡充し,利用することによって幾何的手法による解法を開発してきた.具体的には,まず,現実の場面に現れる最適化問題のうち動的な問題に拡張して効率良く解く要請のある問題の調査を行ない,その幾何構造の性質などを詳しく調べた.その結果,計算幾何学の重要な概念として多くの問題に利用できるVoronoi図などの概念が動的な環境においても,拡張でき,有効であることがわかったので,動的環境にそれらの概念を拡張し,それらを基に最適化問題の解法の開発をしてきた.特に,球面上にVoronoi図を拡張し,施設が球面上を移動する場合の解析を行なった.また,本研究で得られた成果に関しては学術論文や研究資料などで発表し,研究成果の公表を行なった.

Discrete optimization problems are solved by discrete structures, and optimization problems are solved by discrete structures. The importance of static discrete optimization problems has been recognized and actively studied. The linear optimization problem in static situations is related to linear planning method. Many studies have been carried out. The useful results have been obtained. The shortest path problem of traffic volume change in time and the optimal configuration problem of mobile communication equipment change in environment optimization problem of non-linear equipment change in number of situations change in group problem In this study, the dynamic environment, non-linear problems, and discrete structure of the problem are analyzed in detail. The applicant studies the results of dynamic computational geometry and develops solutions using geometric techniques. In the case of concrete optimization problems, the properties of geometric structures are investigated in detail. As a result, important concepts in computational geometry are used to solve multiple optimization problems. In particular, Voronoi on the sphere is stretched, and the analysis of the case of movement on the sphere is performed. The results of this research are related to the academic papers and research data.