欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

采用宽度优先搜索算法求解TSP问题

程序员文章站 2022-03-03 11:14:23
...

【问题描述】采用宽度优先搜索算法求解TSP问题,并在搜索过程中,使用界限条件(当前结点已经走过的路径长度要小于已求得的最短路径)进行“剪枝”操作(不再对后续结点进行遍历),从而提高搜索效率。采用queue模块中的队列(Queue)来实现宽度优先搜索。

【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接矩阵。

【输出形式】最优值和其中一条最优路径。

【样例输入】

4

0 30 6 4

30 0 5 10

6 5 0 20

4 10 20 0

【样例输出】

[1]

[1, 2]

[1, 3]

[1, 4]

[1, 2, 3]

[1, 2, 4]

[1, 3, 2]

[1, 3, 4]

[1, 4, 2]

[1, 4, 3]

[1, 2, 3, 4]

[1, 2, 4, 3]

[1, 3, 2, 4]

[1, 3, 4, 2]

[1, 4, 2, 3]

[1, 4, 3, 2]

25: [1, 3, 2, 4]

【样例说明】

输入:顶点个数为4。连接顶点间边的邻接矩阵大小为4行4列,位置[i,j]上元素值表示第i个顶点到第j个顶点的距离,0表示两个顶点间没有边连接。

输出:最优值为25,最优路径为[1, 3, 2, 4]。

【评分标准】根据输入得到准确的输出。

import numpy as np
import math
import queue


class VertexNode(object):  # 顶点类
    def __init__(self, path=None, cost=None):  # 构造函数
        self.path = path  # 到当前结点为止已经走过的路径
        self.cost = cost  # 到当前结点为止的费用


def bfs(graph, s_index, n):  # 邻接矩阵,起始结点
    best_cost = np.inf
    best_path = None

    start_node = VertexNode(path=[s_index], cost=0)
    q = queue.Queue(maxsize=0)
    q.put(start_node)
    while not q.empty():
        q_node = q.get()  # 弹出第一个结点
        print(q_node.path)
        cur_path = list(q_node.path)
        k = cur_path[-1]
        if len(q_node.path) == n:  # 此时已经有n个结点
            if graph[q_node.path[-1] - 1, s_index - 1] != 0:  # 判断能否形成回路
                new_cost = q_node.cost + graph[q_node.path[-1] - 1, s_index - 1]  # 加上之前的首尾路径长
                if new_cost < best_cost:
                    best_cost = new_cost
                    best_path = list(q_node.path)
            continue
        for i in range(n):
            if graph[k - 1][i] != 0 and i + 1 not in cur_path:
                new_cost = graph[k - 1][i] + q_node.cost
                new_path = list(cur_path)
                new_path.append(i + 1)
                new_node = VertexNode(new_path, new_cost)
                q.put(new_node)
    return best_cost, best_path


def main():
    vex_num = int(input())  # 顶点个数
    w_array = np.zeros((vex_num, vex_num), dtype=np.double)  # 邻接矩阵
    for i in range(vex_num):
        w_array[i, :] = np.array(input().split(), dtype=np.double)
    w_array[w_array == 0] = np.inf
    s_index = 1  # 起始点序号
    best_cost, best_path = bfs(w_array, s_index, vex_num)
    print('{}: {}'.format(int(best_cost), best_path))


if __name__ == '__main__':
    main()

上面的是常规也是正确的做法,下面我贴一下自己用的双队列写的一种错误做法,也可以完成这道题目…

import math  # 宽度优先算法
import queue
from queue import Queue
bestcost = math.inf  # 最短路径
nowcost = 0  # 当前的路径长度
x = [1, 2, 3, 4, 5, 6]  # 顶点序号
path = [1]  
q = Queue(maxsize=0)
arc = []  # 存放


def main():
    n = int(input())  # 顶点个数
    graph = []  # 图的邻接矩阵
    for i in range(n):
        graph.append(list(map(int, input().split())))
    bsp(graph, 1, n)
    print(bestcost, end=": ")
    print(arc[:n])


def getD(graph, q1, path1, n, s):
    for i in range(n):
        if graph[path1[len(path1) - 1] - 1][i] != 0 and (i + 1 not in path1):  # 要使得结点加入,需要有边相连并且不在路径上了
            if len(path1) == n - 1:  # 如果已经有n-1个结点了
                if graph[i][s - 1] == 0:  # 第n个结点和开始结点不相连,说明无法形成一条回路,不将这个加入
                    return
            for k in range(len(path1)):
                q1.put(path1[k])  # 先将路径中的点加入队列
            q1.put(i + 1)  # 加入新结点


def getlength(path1, n, graph, s):  # 获取路径长度
    l = 0
    for i in range(1, n):
        l += graph[path1[i - 1] - 1][path1[i] - 1]
    l += graph[path1[i] - 1][s-1]
    return l


def bsp(graph, s, n):
    global nowcost, bestcost, arc, q
    path1 = []
    q.put(s)  #
    q1 = Queue(maxsize=0)
    for k in range(n + 1):
        while not q.empty():
            for i in range(k + 1):
                path1.append(q.get())
            if k == n - 1:
                nowcost = getlength(path1, n, graph,s)
                if nowcost < bestcost:
                    bestcost = nowcost
                    arc = path1[:]
            print(path1)
            getD(graph, q1, path1, n, s)
            path1 = []
        while not q1.empty():
            q.put(q1.get())


if __name__ == '__main__':
    main()

这种写法也有改进空间,我想了一下一个队列也应该能完成