離散的な構造を持つ非凸計画問題に対する実用的なアルゴリズムの開発及び性能評価

离散结构非凸规划问题实用算法的开发和性能评估

• 批准号: 10780274
• 负责人: 戴 陽
• 金额: $ 0.9万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10780274/
• 关键词: minimum weight triangnlation; Local optimality; dynamic programing; optimal triangnlation; LMT-skeleton

点集合の3角形分割とは、2次元平面上の点集合が与えられたとき、その凸包を、与えられた点を頂点とする3角形に分割することである。3角形分割を行う際に、応用上重要なのは、偏平な3角形をできるだけ作らないことであり、その観点から従来、角度、辺長和を用いた最適性の基準が用いられている。本研究では建築構造設計上などに応用があると思われる三つの新しい最適性の基準を提案する。(1)分割された3角形の最小角と最大角にそれぞれ下限値と上限値の制約を設けたときの辺長和を最小にする基準;(2)各3角形の面積の平方和を最小にする基準;(3)各3角形の最大角と最小角の比の和を最小にする基準。そして、それぞれの基準を満たす3角形分割を求める問題を非凸の計画問題に定式化することによって、統一な枠組で、解を求あることができた。具体的には、局所最適解を発見的な手法によって、多項式時間で最適解の部分集合(この場合は3角形分割にはいる枝の集合)を構築し、動的計画法によって最適な3角形分割にあるすべての枝を見つけるようなアルゴリズムを提案した。これらの問題の計算複雑さはまだ明らかになっていないにもかかわらず、計算機実験では、このアルゴリズムは点数500点以下の問題であれば、かなり高速に最適な3角形分割を見つけることが確かめた。

一个点集的三角剖分是将凸壳划分为三维平面上给定点作为顶点的给定点的三角形的过程。执行三角剖分时，应用程序是为了避免尽可能多地制作平坦的三角形，从这个角度来看，过去已经使用了使用角度和侧面长度和总和的最佳标准。这项研究提出了三个新的最佳标准，这些标准可能在建筑结构设计等中具有应用。 （2）最小化每个三角形区域的平方之和的标准； （3）最小化每个三角形的最大和最小角度比率的标准。通过制定找到三角剖分的问题，将每个标准符合非凸准计划问题，我们能够在统一框架中找到解决方案。具体而言，我们提出了一种算法，其中通过使用启发式方法在多项式时间内构造最佳解决方案（三角剖分中的一组分支）的子集，并在多项式时间内构建局部最佳解决方案，并使用动态编程在最佳三角测量中找到所有分支。尽管尚未揭示这些问题的计算复杂性，但计算机实验已证实，如果问题小于500点，则该算法可以在相当快的速度下找到最佳的三角剖分。

项目成果

Y.DAI: "On computing new classes of optimal triangnlation with angular condition" Lecture Notes of Computer Science. 1449. 15-24 (1998)

Y.DAI：“关于用角度条件计算新类别的最佳三角剖分”计算机科学讲义。