周怀北英文文章及翻译

2020年12月11日发(作者：杨紫琼)
2.1 算法思想的提出
2.1 algorithm proposed ideas
所谓赋权汉密尔顿回路最小化问题是指，给定n个点及n个点两两之间
的距离(或权数)， 求一条回路，使之经过所有的点，且经过每个点仅一次，而
整条回路(也称路径或边界)的总距离(或总 权数)最小。
The so-called empowerment Hamilton loop minimization problem
is to point to that, given n points and n points of the distance
between (or opposite); a circuit weight, make through all the
points, and after each point only once, and the whole loop (also
called path or boundary) total distance (or total weighted function)
minimum.
这一问题总是可以通过枚 举法求出其解的，但由于枚举法的计算量过大，
达到(n－1)!的数量级，因而，不是可行的方法。由 此，人们提出了启发式算
法来求解问题的近似解。所谓启发式算法，一般地讲，就是发现某些最优解所具备的特征或不应具备的特征，对应有特征而言，求出含应有特征的可行
解；对不应有特征而言， 从解空间中剔除不应有特征的解，再从剩余空间中
找一个解。因而，启发式算法可以定义为：从最优解的 必要条件出发，设计
一个有效算法，使之求出的解满足这些必要条件。
This problem can always through the enumeration method find
out the solution, but due to the enumeration method of computing
dimension, achieve (n - 1)! The magnitude of the issue, therefore,
is not feasible method. Thus, people put forward to solve the
problem of heuristic algorithm approximate solution. Alleged
heuristic algorithm, generally speaking, is that some optimal
solution has the characteristics or not should possess the
characteristics of concerned, should ask the characteristics of
the feasible solution containing should have characteristics;
Should not have characteristics of concerned, from the solution
space to remove the solution should not feature, and again from
the remaining space looking for a solution. Therefore, heuristic
algorithm can be defined as: from the optimal solution of the
necessary conditions, and to design an effective algorithm, make
out the solution meet these necessary condition.
就一 般算法的本质而言，它是提供一种规范的过程，经由该过程得出的
解满足问题最优解的充分条件，即算法 应该是问题最优解的充分条件的一种
规范实现过程；而算法设计本身要求，算法必须给出解，因此，算法 实际上
还要满足最优解的必要条件，即算法可以定义为：算法是问题最优解的充分
必要条件的一 种规范实现过程。
The essence on the general algorithm, it is to provide a standard
of process through this process, that the optimal solution meet
problem, namely, the sufficient conditions for the existence of the
optimal algorithm should be problems the sufficient conditions for
the existence of a normal realization process; And algorithm
design itself requirements, algorithm, therefore, must be solution
algorithm actually also to meet the necessary conditions of the
optimal solution, namely algorithm can be defined as: algorithm
is the optimal solution of the problem, the sufficient and
necessary conditions of a normal realization process.
启发式算法只满足了算法的必要性条件，而没有满足其 充分性条件，就一般
意义而言，其结果不是问题的最优解。基于这一思路，经典启发式算法的做
法就是从满足必要条件的解空间中找出一个解，这就产生了一个问题：这样
的解是否还可以按某种规则改 进?这就涉及局部极值或重叠应用启发式算法
的问题。如果存在局部极值或进一步优化的规则，那么，在 已有解的基础上
继续运用这些规则会极大改进算法的性能，这就是本算法的基本思路。
Heuristic algorithm only satisfy the necessary condition of the
algorithm, and not meet its adequacy condition, general sense,
the result is not the problem of optimal solution. Based on this
idea, it is classic heuristic algorithm from meet the necessary
conditions in the solution space find a solution, which has a
problem: such a solution according to certain rules whether can
also improve? This will involve local extremum or jackknife
application of heuristic algorithm. If there are local extremum or
further optimized rules, then, on the basis of the existing solution
continued to use these rules will greatly improve performance of
the algorithm, this is the basic thought of this algorithm.
2.2 算法的规则分析
Rules of 2.2 algorithm is analyzed
依据上述局部优化的算法思想，对赋权汉密尔顿最小化问题进行分析。
对该问题的一般形式 (包括平面和非平面)给出一条规则：最优路径上各点在插
入路径时，其路径变化量最小。
Based on the above local optimization algorithm for
empowerment Hamilton thoughts, analyzes minimization
problem. The general form of the problem and the plane
(including plane are one rule:) the optimal path is inserted in
different points on the route, the minimum amount of path
changes.
这是本文给出优化算法的基础。关 于该规则，用反证法可以简单地证明，
即若最优路径上有某一点在插入路径时，其路径变化量不是最小， 那么，至
少还有一种插入法的路径变化量更少，则以路径变化量更小的插法来代替原
插入方法， 由此形成的回路其路径更短，而这与原路径最短的假设矛盾，所
以，规则成立。
This is the basis of optimization algorithm are given in this paper.
About the rules, with counter- evidence method can simply proof,
the optimal path sacrificed if a certain point when inserted in, its
path path is not the smallest amount of variation, then, there is at
least a insertion method path variation less, criterion with path
variation inserted more small method to replace the former insert
method, thus forming a loop its path, and this more short with the
original path the shortest hypothesis is contradictory, so, rules
established.
依据上面的分析，给出相应的算法。
Based on the above analysis, and gives corresponding
algorithm.
2.3.1 优化方法
2.3.1 optimization method
第0 步，确定一个初始的循环起点。即以汉密尔顿回路上的某一点作为
循环的起点，以该起点为当前点，转入 第1步。
The first 0 step, sure an initial cycle starting point. Namely to
Hamilton back at some point as a way of starting point and by the
cycle for current points, to start the first step.
第1步，跨线切割形成孤立点。即在已形成的汉密尔顿回路上，以当前
点为 跨线的起点，按路径方向作跨线，用跨线切割中间点，使该中间点成为
孤立点，而该跨线成为一条边；此 时，回路的路径上不包含全部点，故非然
汉密尔顿回路，转入第2步。
Step 1, cross line form outlier. The Hamilton has formed namely
in road, by current points to the starting point for cross line
direction, by path across lines, use cross line middle point, make
the intermediate point become isolated points, while the cross
line become an edge; At this time, circuit path does not contain
all points, so the ran Hamilton circuit, turn to step 2.
第2步，将孤立点重新连入路径中。按路径变化量最小原则，将被切割< br>下来的孤立点重新连入回路中；连入之后，回路的路径中包括全部点，故又
形成汉密尔顿回路，转 入第3步。
Step 2, will outlier to concatenation path. According to the
minimum amount of path changes, it will be cut down the
principle of outlier to concatenation loop; Concatenation, circuit
path after, so it is also include all the points, turn to form Hamilton
circuit for the first three steps.
第3步，如果产生了路径的变化，则以新路径 取代旧路径，但以原跨线
的起点为循环的新起点，也为当前点，返回第1步，继续计算；否则，走向下一点，以下一点为当前点，转入第4步。
Step 3, if produced path changes, criterion with new path to
replace the old path, but the starting point to the cross line for the
cycle of new starting point, but also for the current point, return to
step 1, continue to computing; Otherwise, toward the next point,
the following point for the current point, turn to step 4.
第4步，判断一个循环是否完成，即当前点是 否是循环的起点。如是，
则算法结束；如不是，则转入第1步。(算法描述完毕)
Step 4, judge a cycle is completed, namely the starting point of
the point is cycle. If yes, then algorithm ended; If not, then turn to
step 1. (arithmetic description finished)
当算法结束时，回路上的每一个点相对于其它点都是最优，即回路达到
其局部极值。
When algorithm end, back every point on relative to the other
point is the optimum, namely loop achieve its local minima.
对平面问题，为简化计算，当跨线为内 连线时，不作变动，向下一点走；
当跨线为外连线时，切割其中间点，然后再将被切掉的中间点重新连入 路径
中。
On planar problem, for the simplified calculation, when cross line
is the attachment, does not make the change, down a little walk;
When cross line cutting to the attachment, between point of, and
then will be cut off to the middle point scored path.