算法的发现(IV)——论组合优化的特性清单

ON DISCOVERY OF ALGORITHMS(Ⅳ) ——A Property List in Combinatorial Optimization

组合优化问题的定义［１］是定义１问题ＸＹＺ是指：对于每一个π（１）－集合Ｓ，从其诸π（２）－子集合中找出π（３）－（优）集合Ｓ＊．本文直接从它出发，§§２－５讨论诸π（ｉ）－集合（ｉ＝１，２，３）的某基本特性（ｐｒｏｐｅｒｔｙ），公理（ｐｏｓ－ｔｕｌａｔｅ），或者特殊情形（ｐａｒｔｉｃｕｌａｒｃａｓｅ）．列出了一个清单ＰＰＰ，叫做特性清单．它远非完善，但已经可以用来讨论不少问题．§６起简单地讨论若干个子清单，所对应的问题类，并讨论求解它们的一些方法．

The definition of combinatorial optimizdtion problem is the following: [WT5”HZ〗Definition 1 Problem XYZ is that for each π (1) set S, among all its π (2) sets it finds out its π (3) (iptimum) set(s) S . Starting from the definition, the article lists first (§§2-5) certain properties, postulates and particular cases of π (i) sets(i=1,2,3). They form a property list, denoted by List PPP. It is far from perfect, but it is good enough to develoge some basic matters. §§6—9 briefty discuss five sub property lists, the relevant categories of problems and their basic methods for solving the problems. Finally,§10 mentions the algorithm problem about the maximum weighted matching problem.