算法的发现（Ⅱ）──对称差（的）分解法及其应用

ON DISCOVERY OF ALGORITHMS(Ⅱ)──SYMMETRY-DIFFERENCE DECOMPOSITION METHOD WITH APPLICATIONS

本文摹仿古典数学的导数、差分概念，在组合优化中建立枚举章法下的一个方法一一对弥差分解法，给出一个求解某些问题的一般模式。用它统一地讨论组合最优化的六个基本图论问题：最短路问题，最小生成树问题，匹配问题，巡迥商问题，中国邮路问题和最大流问题。讨论表明，Ｂｅｌｌｍａｎ最优性原理，交错链，增值路等概念都是对称差分解法在具体问题中的自然结果。还表明，涉及上述大个问题的２０多个著名定理都是定理４的具体推论。

Modelling afterthe definitions of derivative and differenceinclassicalmathematics,it presents a so-called s ymmetry-difference decomposition methodand solves some combinatorial optimization problelns.The method belongstothetype of enumeration approach discussed in(I).It solves six basicgraphproblemsina unified fashion.They are shortest path problem,minimumspanning tree problem, travelling salesman problem,matching problem,Chinesepostman problem and maximum flow problem.It shows that some basic concepts,such as Bellman′sprjnciple of optimality,aIternating path,incrmenting pathand others,are the natural products of the symmetrydifference decompositionmethodinthe problem discussed.It shows also that twenty well-knowntheorems relevant to thesixproblems mentioned are the easy corollaries ofTheorcm 4。