構造解析を基にした組合せ最適化アルゴリズムの効率化に関する研究

基于结构分析的组合优化算法效率提升研究

基本信息

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

项目摘要

今年度は以下の3つ(a)「0-1多面体の構造解析」(b)「重み付きグラフにおける全域木の重み順全列挙アルゴリズムの開発」(c)アルゴリズムの平均的な振る舞いの評価に関する研究」を研究目的とした。(a)に関しては、グラフの最大安定集合問題、グラフの辺(または頂点)の彩色問題に関連した0-1多面体の特殊な面がある半順序集合のイデアル全体から作られる0-1多面体と合同であるという構造を明らかにした。また、この構造を利用し、最大安定集合問題などに対する発見的な方法を提案した。この成果は論文としてまとめ、アメリカ合衆国のミシガン大学で開催された第15回数理計画国際シンポジウム(15th International Symposium on Mathematical Programming)や福岡で開催された第3回アジア太平洋地区オペレーションズ・リサーチ会議(The Thrid Conference of the Association of Asian-Pacific Operational Societies within IFORS)など国内外の会議において口頭発表し、国際的論文誌であるMathematical Programmingに掲載されることになった。(b)に関しては、重み順ではないがグラフの全域木を列挙する時間計算量の意味でも空間計算量の意味でも最適なアルゴリズムを開発した。既存のアルゴリズムで二つの計算量の意味で最適なものはなく、このアルゴリズムが初めてのものである。この研究成果は、論文としてまとめ、第15回数理計画国際シンポジウムや第3回アジア太平洋地区オペレーションズ・リサーチ会議など国内外の会議において口頭発表し、国際的な論文誌であるSIAM Journal on Computingに投稿した。研究目的(c)に関しては、今年度中には論文として発表できるような成果は残念ながら得られなかったが、今後も継続して研究をしていく。本年度は、補助金によって設備としてX端末を購入し、現有設備であるワークステーション(平成4年度科研費により購入)と接続し、論文や発表原稿・OHPの作成、実験結果のグラフィック表示など有効利用した。

今年，研究目标是以下三（a）：0-1多面体的结构分析，b）：在加权图中为跨越树的加权枚举算法的开发，c）研究评估算法的平均行为。关于（a），我们已经揭示了以下结构，即它与从部分有序的设置问题的整个理想制成的0-1多面体是一致的，与图表的最大稳定设置问题相关的0-1多面体的特殊面孔以及图表的边缘（或角度）的着色问题。使用这种结构，已经提出了针对最大稳定的设置问题等提出的启发式方法。这一发现已汇编成一份论文，并在国内和国际会议上进行了口头介绍，包括在美国密歇根大学举行的第15届国际数学节目研讨会，并在Fukuoka和International撰写的《 Internictical》中，在富尔库卡（Fukuoka）中举行的第三次亚太运营社会，并在国际上刊登了国际刊物。关于（b），我们开发了一种最佳的算法，该算法不是重量的顺序，而是在时间和空间计算方面，列出了图中的生成树。从两个计算复杂性方面，没有现有的算法是最佳的，这是第一次制作。这项研究的结果汇编成论文，并在国内和国际会议上口头介绍，例如第15届国际科学与计划研讨会以及第三届亚太地区运营研究会议，并提交给《国际暹罗计算杂志》。关于研究目的（c），不幸的是，我们无法在本财政年度内获得可以作为论文发表的结果，但是我们将来将继续进行研究。今年，X终端是通过补贴作为设施购买的，并连接到当前的设施，工作站（由1992年研究基金购买），并有效地使用了X终端，包括创建论文，发表的手稿和OHP，以及实验结果的图形显示。