约束满足与欧几里得TSP问题的优化策略

### 约束满足与欧几里得TSP问题的优化策略 在约束满足领域以及欧几里得旅行商问题（TSP）求解中，有许多值得深入研究的技术和策略。下面我们将详细探讨相关的算法和方法。 #### 1. 约束满足中的一致性交织算法 在约束满足问题里，为了提高求解效率，人们尝试了多种一致性交织算法。 ##### 1.1 AC - 4风格交织算法 为了判断弧一致性（AC）交织是否有益，我们可以通过测试某类中的一些问题来确定。同时，人们还设想使用更高效的交织形式来解决问题，于是基于AC - 4数据结构的算法应运而生（这里仅考虑其二进制形式）。 AC - 4算法包含两个阶段： - **阶段1**：检查所有值组合，建立表示支持集的数据结构，涵盖每个约束下各值支持的值列表（支持集）、统计每个值在各约束下支持数量的计数器，以及指示给定域中值是否仍可行的二进制值数组。 - **阶段2**：从在某些约束下无支持的值（“坏列表”）开始，利用这些值减少与每个坏值关联的支持集中各成员的计数器。若某个计数器归零，则将新值添加到坏列表中，直至坏列表为空或出现擦除情况。 以下是结合NSAC - 1使用AC - 4的伪代码： ```plaintext Procedure NSAC - 1AC4 1 OK ← AC4(P) 3 Repeat /* if OK */ 4 Changed ← false 5 Foreach Xi ∈ X 6 Foreach vj ∈ dom(Xi) 7 dom (Xi) ← {vj} 8 If AC3(Xi + neighbours(Xi)) leads to wipeout 9 dom(Xi) ← dom(Xi)/vj 10 Set entry for vj in mark array to false 11 and set badlist to ((Xi, vj)) 12 OK ← AC4phase2(P) 13 Changed ← true 14 Until Changed == false or not OK ``` 当与NSAC结合时，AC - 4用于初始的AC传递。在后续的（N）SAC处理中，只要基于SAC的处理证明某个值可丢弃，就会继续使用支持计数系统。因此，阶段1的设置只需进行一次。不过，实际情况是，至少在当前实现中，关于AC - 4阶段2效率的假设被证明是错误的。该算法通常比基于AC - 3的算法慢一个数量级，这可能是因为不断更新大量条目必然会耗费时间，但这又是保证算法正确性所必需的。 ##### 1.2 其他交织方式 除了上述方法，还测试了使用NSAC进行交织的情况，其中SAC作为基本算法。最简单的组合是先使用NSAC，然后运行SAC算法。使用SACQacn算法时，在某些情况下（如RLFAPs）可提高效率达30%，但在个别情况（如驾驶员日志问题）下会导致效率降低10%。关键因素似乎是NSAC相对于SAC的有效性，如果NSAC几乎与SAC一