摘要
本文对经典组合优化问题解的主要概率极限定理作一综述 ,并重点讨论零担售货员问题 ,极小生成树 ,匹配和最长单调增子列长度 .涉及的概率极限定理包括强大数律 ,收敛速度 ,依分布收敛和大偏差原理 .没有提供详细证明 。
A review was given of the principal probability limit theorems of solutions to classical combinatorial optimization problems. The emphasis was on the travelling salesman problems, minimal spanning trees, matching and lengths of the longest increasing subsequences. Probability limit theorems surveyed mainly involved strong laws of large numbers, rates of convergence, convergence in distribution and large deviation principles. No proofs were given. Some of the main open problems were described.
出处
《浙江大学学报（理学版）》
CAS
CSCD
2000年第6期700-713,共14页
Journal of Zhejiang University（Science Edition）
基金
Project supported by National Natural Science Foundation of China (No.1970 10 11)
关键词
极限定理
零担售货员
极小生成树
经典组合优化
limit theorems
matching
minimal spanning trees
travelling salesman problems
