幾何的配置問題の計算量限界と近似可能性の研究

几何布局问题的计算极限与逼近性研究

• 批准号: 16092214
• 负责人: 加藤 直樹
• 金额: $ 8.32万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092214/
• 关键词: 幾何的最適化問題; ラーマングラフ; 一様三角形メッシュ; 最短避難経路問題; コンプライアントメカニズム; 最適避難経路問題; テンセグリティ; 最適避難計画; 近似アルゴリズム; 配送計画; 構造最適化; 計算幾何学; 組合せ最適化; トポロジー最適化; 長方形検出; 三角形メッシュ生成; 折れ線近似

1.前年度に開発した無交差ラーマングラフをすべて列挙するアルゴリズムにおいて、実用的な観点から、出力されるグラフのクラスに制限を課した列挙アルゴリズムを開発した。一つは最大次数の上限が与えられている場合で、もう一つはあらかじめ辺集合を指定し、それらを含まないグラフに限定するものである。これらは、いずれも計算困難であることが予想されるが、実用的なアルゴリズムを開発した。2.逆探索法によって列挙された静定構造物(ラーマングラフ)に対して,節点座標と部材断面積を連続変数として,指定された性能(大変形挙動)を満たすコンプライアントメカニズムを求めた。また,節点数と計算量の関係を検討し,最適な解を求める際の計算量限界を明らかにした。3.無交差全域木の高速列挙アルゴリズムを開発した。その計算時間の理論的性能評価とともに、計算機実験をおこない、その実用的な性能を評価した。4.火災等の発生時における建物内部から安全な外部への最適避難経路(最大移動時間最小化問題)や、津波や大地震発生時に安全な建物・地域への最適避難経路を求める問題を考察した。実用的な観点から、格子状ネットワーク、木構造ネットワークに限定し、通路幅一定、途中での枝分かれを許さない、経路が交差しない等の制約下での最適経路群を求めた。またGISや実データを利用し、通行可能経路が確率的に定まるような実際的な問題への導入も検討した。5.LRTなどを模した線的施設配置問題について研究した。駅と線路からなる平面上の全域木において、利用者の総移動時間を最小化するような、ネットワークのトポロジーを求めるヒューリスティクスを開発した。

1. In the past year, the development of non-cross-cutting equipment has been carried out in the field, and the development of practical equipment has been carried out in the field. The maximum number of times a set can be specified, and the maximum number of times a set can be specified. This is the first time I've ever seen a computer. 2. The inverse search method is used to determine the static structure, node coordinates, component cross-sectional area, and specified performance. The relationship between the number of nodes and the amount of computation is discussed, and the optimal solution is determined. 3. The high-speed train of the cross-free global wood has been developed. Evaluation of theoretical performance of computing time, computer performance and practical performance 4. The optimal evacuation route for the internal and external safety of buildings during the occurrence of fire (minimizing the maximum travel time), earthquake, earthquake, etc. are investigated. The optimal path group is obtained under the constraints of the actual point, lattice, wood structure, path width, branch and intersection. GIS is used to determine the accuracy of traffic flow and to investigate the import of traffic flow problems. 5. Research on the configuration of LRT line. The whole area of the line is located in the middle of the plane, and the user's movement time is minimized.

项目成果

A direct approach to design of geometry and forces of tensegrity structures

张拉整体结构几何和力设计的直接方法

• 发表时间: 2006
• 期刊: Int.J.Solids and Struct. 43・7
• 作者: J.Zhang;M.Ohsaki;Y.Kanno
• 通讯作者: Y.Kanno

内向木による有向グラフの被覆

用向内树覆盖有向图

• 发表时间: 2008
• 作者: 神山直之;加藤直樹
• 通讯作者: 加藤直樹

単一パス長ネット.ワークにおける避難計画問題に対する効率的なアルゴリズム

单路径长度网络疏散规划问题的高效算法

• 发表时间: 2007
• 作者: 神山 直之;加藤 直樹;瀧澤 重志
• 通讯作者: 瀧澤 重志

Stability conditions for tensegrity structures

• DOI: 10.1016/j.ijsolstr.2006.10.027
• 发表时间: 2007-06
• 期刊: International Journal of Solids and Structures
• 影响因子: 3.6
• 作者: Jingyao Zhang;M. Ohsaki

Enumeration of optimal pin-jointed bistable compliant mechanism

最优销接双稳态柔顺机构的枚举

• 发表时间: 2009
• 期刊: Structural and Multidisciplinary Optimization 37 (6)
• 作者: Naoki Katoh;Makoto Ohsaki;Takuya Kinoshita;Shin-ichi Tanigawa;David Avis;Ileana Streinu
• 通讯作者: Ileana Streinu