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

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

• 批准号: 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角形分割を見つけることが確かめた。

点集的三角剖分意味着，给定二维平面上的点集，将其凸包划分为以给定点为顶点的三角形。当执行三角测量时，在实际应用中重要的是尽可能避免创建平坦三角形，并且从这个角度来看，传统上已经使用使用角度和边长之和的最优标准。在这项研究中，我们提出了三个新的最优标准，预计将在建筑结构设计中得到应用。 （1）当所划分的三角形的最小和最大角度分别受下限和上限约束时，最小化边长之和的准则；（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：“关于用角度条件计算新类别的最佳三角剖分”计算机科学讲义。