Page 240 - 《软件学报》2025年第8期

李睿智 等: 局部搜索算法求解最小弱连通支配集问题 3663

最后, 本文引用了一个候选集合 SWCE 来保存当前解的弱连通元素, 以确保添加的顶点能够使解变得可行. 基于以
上讨论, FPLS_Search 过程在算法 3 中得到了详细描述.

算法 3. FPLS_Search 过程.
输入: 初始解 W, 最大循环迭代次数 ITEM_NUM;
输出: 局部最优的弱连通支配集 W'.

1. W' ← W;
2. it ← 1;
3. Noimprovestep ← 1;
4. WHILE it < ITEM_NUM DO
5. WHILE 当前解 W 是一个弱连通支配集 DO
6. IF |W| < |W'| THEN
7. W' ← W; /*更新最小解*/
8. Noimprovestep ← 1;
9. ELSE
10. Noimprovestep ++;
11. 根据移除顶点规则 1 从当前解 W 中挑选一个顶点 w;
12. W ← W\{w};
13. 根据格局更新规则 3 更新顶点 w 的 2 层邻居内所有顶点 v 的格局值 ConfChange;
14. 根据年龄更新规则 3 更新顶点 w 的年龄值 age[w] 为 1;
15. 根据移除顶点规则 2 从当前解 W 中挑选一个顶点 w;
16. W ← W\{w};
17. 根据格局更新规则 3 更新顶点 w 的 2 层邻居内所有顶点 v 的格局值 ConfChange;
18. 根据年龄更新规则 3 更新顶点 w 的年龄值 age[w] 为 1;
19. IF Noimprovestep%50 = 0 THEN
20. FOR i = 1 TO 0.01×|V|
21. 根据移出顶点规则 2 从当前解 W 中挑选一个顶点 w;
22. 将挑选的顶点 w 从当前解 W 中移出;
23. 根据格局更新规则 3 更新每一个移出顶点 w 的 2 层邻居内所有顶点 v 的格局值 ConfChange;
24. 根据年龄更新规则 3 更新顶点 w 的年龄值 age[w] 为 1;
25. WHILE 存在没有被支配的顶点 DO
26. 根据添加顶点规则 2 从当前解 W 的 2 层邻居中挑选一个顶点 w;
27. W ← W ∪ {w};
28. 根据年龄更新规则 2 更新顶点 w 的年龄值 age[w] 为 1, 其余顶点 v 的年龄值 age[v] 加 1;
29. 根据格局更新规则 2 更新顶点 w 的 2 层邻居内所有顶点 v 的格局值 ConfChange;
30. add_frequency[w]++;
31. WHILE 当前解 W 不是一个弱连通支配集 DO
32. 更新当前解的弱连通元素集合 SWCE;
33. 根据添加顶点规则 3 从当前解的弱连通元素集合 SWCE 中挑选一个顶点 w;
34. W ← W ∪ {w};
35. 根据年龄更新规则 2 更新顶点 w 的年龄值 age[w] 为 1, 其余顶点 v 的年龄值 age[v] 加 1;