计算机算法课分支定界题解

用分支定界算法求以下问题：

某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵 M1 给出。每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵 M2 给出。

请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。

具体数据参见文件：

• M1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市 Num.1，乙城市为城市 Num.50。
• M2.txt: 每段公路收取的费用矩阵（非对称）。

解答：

上下界：

本题所述问题中存在两个界：

• 养路费总额不超过 1500，此为一个上界，在搜索过程中，如果累计养路费超过此值，可立即剪枝。
• 若设当前已经得出的一条最短路径的长度为 shortest_distance，那么此值也成为一个上界，在搜索过程中，如果路径长度大于此值就可进行剪枝操作。

上面的第二个解，显得有些不够紧。当搜索到某个城市时，将此时距离目的地 Num.50 的最短距离 shortest_distance_to_dest 与从出发点到当前城市已经走过的距离 total_distance 之和记为 d，那么这个 d 如果当前大于已经得出的 shortest_distance，就可以立即剪枝。这样可以得到更加紧的上界。

搜索策略：

这里采用深度优先搜索策略，每深入一层，通过参数传入新生成的路径。在搜索过程中根据前文确定的界来进行剪枝。当到达目的地 Mum.50 的时候，把得到的路径长度和全局最短路径比较，保存下最优解。

最终得到结果为：

shortest path: [0, 2, 7, 10, 14, 20, 22, 25, 31, 36, 38, 44, 46, 49]
shortest distance: 464

下面是解答本题的 python 代码：

import numpy as np

class Solution:
    def __init__(self):
        self.distance_mat = np.genfromtxt('./m1.txt',dtype=int,delimiter='\t')
        self.cost_mat = np.genfromtxt('./m2.txt',dtype=int,delimiter='\t')

        self.dest_city = 49

        self.shortest_path = []
        self.shortest_distance = float('inf')
    
        # 将原矩阵拷贝一份，因为在求最短路径的时候会改变原矩阵
        self.min_distance_mat = self.floyd(self.distance_mat.copy())
        self.min_cost_mat = self.floyd(self.cost_mat.copy())

    def floyd(self, graph):
        np.fill_diagonal(graph, 0)
        
        n = graph.shape[0]
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
                    
        return graph


    def find_shortest_path(self):
        self.__find_shortest_path([0], {0}, 0, 0)

        return (self.shortest_path, self.shortest_distance)

    def __find_shortest_path(self, path, visited_city_set, total_distance, total_cost):
        current_city = path[-1]

        if total_distance + self.min_distance_mat[current_city][self.dest_city] > self.shortest_distance:
            return
        
        if total_cost + self.min_cost_mat[current_city][self.dest_city] > 1500:
            return

        if current_city == self.dest_city:
            self.shortest_distance = total_distance
            self.shortest_path = path

        for city in range(50):
            # 跳过访问过的 city 和 不可达的 city
            if self.distance_mat[current_city, city] == 9999 or city in visited_city_set:
                continue
                
            new_distance = total_distance + self.distance_mat[current_city, city]
            new_cost = total_cost + self.cost_mat[current_city, city]

            self.__find_shortest_path(path + [city], visited_city_set | {city}, new_distance, new_cost)
    

if __name__ == '__main__':
    solution = Solution()
    
    shortest_path, shortest_distance = solution.find_shortest_path()

    print('shortest path: '.format(shortest_path))
    print('shortest distance: '.format(shortest_distance))