人工智能 - CSPs 的现实世界示例

使用 CSP 算法解决旅行商问题

旅行商问题 (TSP) 是找到一条最短路径，该路径恰好经过每个城市一次并返回起始城市。作为一个约束满足问题，旅行商问题的变量、域和约束如下所示 −

• 变量： 图中的城市（节点）是变量。

• 域： 推销员访问的任意城市，除了已访问过的城市。

• 约束： 每个城市恰好被访问一次。旅行者返回起始城市，并使总旅行距离最小化。

回溯

回溯是一种深度搜索方法，用于为复杂问题找到解决方案。首先，我们按照约束逐步为变量从其域中赋值，如果发现约束被违反，则回退并为前面的变量尝试不同的值。

此代码利用 backtracking 找到有效路径，并根据以下约束决定最佳解决方案。

步骤 1：定义问题

图以距离矩阵的形式表示。在此，graph[i][j] 表示城市 i 和城市 j 之间的距离。例如，如果 graph[0][1] = 12，则城市 1 和城市 2 之间的距离为 12 个单位。

这里，n 表示城市的总数，start_node 表示算法开始搜索可能路径的起始城市。这种结构可以视为解决 Constraint Satisfaction Problem (CSP) 方法的基本路径查找。

# 第一步是定义图，节点和边表示城市及其距离。

# 以距离矩阵形式表示的图
graph = [
   [0, 12, 17, 22],  # 来自节点 1 的距离
   [12, 0, 27, 38],  # 来自节点 2 的距离
   [17, 27, 0, 32],  # 来自节点 3 的距离
   [22, 38, 32, 0]   # 来自节点 4 的距离
]
n = len(graph)  # 节点数量
start_node = 0  # 从节点 1（索引 0）开始

步骤 2：定义 TSP 求解器类

TSP 求解器使用 backtracking 探索所有可能路径并找到最优解。

图和 start_node 被存储，变量被初始化以跟踪 最佳路径 和 最小成本（best_path 和 min_cost）。

class TSP:
   def __init__(self, graph, start_node):
      self.graph = graph
      self.start_node = start_node
      self.best_path = None
      self.min_cost = float('inf')
   
   def solve(self):
      visited = [False] * len(self.graph)
      visited[self.start_node] = True
      self.backtrack([self.start_node], 0, visited)
      return self.best_path, self.min_cost
   
   def backtrack(self, path, current_cost, visited):
      # 基本情况：所有节点已被访问，返回起始节点
      if len(path) == len(self.graph):
         total_cost = current_cost + self.graph[path[-1]][self.start_node]
         if total_cost < self.min_cost:
            self.min_cost = total_cost
            self.best_path = path + [self.start_node]
         return
      
      # 尝试所有可能的下一个节点
      for next_node in range(len(self.graph)):
         if not visited[next_node] and self.graph[path[-1]][next_node] > 0:
            visited[next_node] = True
            self.backtrack(path + [next_node], current_cost + self.graph[path[-1]][next_node], visited)
            visited[next_node] = False         

步骤 3：求解 TSP 问题

我们创建 TSP class 的一个实例并调用 solve 方法。

然后调用求解器（solve 方法）来计算最优路径和最小成本，从指定节点开始，使用回溯逻辑遍历图。

tsp = TSP(graph, start_node)
best_path, min_cost = tsp.solve()

# 输出结果
print("Optimal Path:", [node + 1 for node in best_path])  # 转换为 1-based 索引
print("Minimum Cost:", min_cost)

完整代码

旅行商问题 (TSP) 求解器的完整实现如下所示，它使用回溯来确定成本最低的最优路径。

# 以距离矩阵形式表示的图
graph = [
   [0, 12, 17, 22],  
   [12, 0, 27, 38],  
   [17, 27, 0, 32],  
   [22, 38, 32, 0]   
]
n = len(graph)  
start_node = 0  

class TSP:
   def __init__(self, graph, start_node):
      self.graph = graph
      self.start_node = start_node
      self.best_path = None
      self.min_cost = float('inf')
   
   def solve(self):
      visited = [False] * len(self.graph)
      visited[self.start_node] = True
      self.backtrack([self.start_node], 0, visited)
      return self.best_path, self.min_cost
   
   def backtrack(self, path, current_cost, visited):
      
      if len(path) == len(self.graph):
         total_cost = current_cost + self.graph[path[-1]][self.start_node]
         if total_cost < self.min_cost:
             self.min_cost = total_cost
             self.best_path = path + [self.start_node]
         return
      
      for next_node in range(len(self.graph)):
         if not visited[next_node] and self.graph[path[-1]][next_node] > 0:
            visited[next_node] = True
            self.backtrack(path + [next_node], current_cost + self.graph[path[-1]][next_node], visited)
            visited[next_node] = False
         
tsp = TSP(graph, start_node)
best_path, min_cost = tsp.solve()

# 输出结果
print("Optimal Path:", [node + 1 for node in best_path])  
print("Minimum Cost:", min_cost)

以上代码的输出如下 −

Optimal Path: [1, 2, 3, 4, 1]
Minimum Cost: 93