希望让我的程序BFS算法更加高效

Question

我正在开发一个程序，该程序对一系列连接的链接进行广度优先搜索，并且应该输出一条打印语句，告诉我要剪切哪些链接。要切断的链接将阻止某个代理前往其当前位置，前往散布在图表周围的出口网关之一。

该图像准确地显示了程序做什么，以及它不应该同时做什么。绿色虚线链接是我正在打印的链接，它将切断红色 bobnet 代理到浅蓝色出口网关的路径。

这是我的程序的输入映射：

初始化输入： 第 1 行：3 个整数 N L E

• N，该级别的节点总数，包括网关。
• L，关卡中的链接数。
• E，关卡中出口网关的数量。

接下来的L行：每行2个整数（N1，N2），表示网络中索引为N1和N2的节点之间的链接。

接下来的E行：1个整数EI，表示出口网关节点的索引。

因此，正如您所看到的，我的程序中发生的情况是，程序检查代理的位置，并切断其旁边最可能的链接。然而，似乎有一个更高效的程序，它不像我的例子那样在 39 步内完成，而是以更少的步数结束，我想请求帮助找出我的程序的问题所在，以有效地管理以使其更加高效：

import sys
from collections import deque

class Binder:
    
    def __init__(self, id, pre_binder):
        self.id = id
        self.pre_binder = pre_binder
        
class Game:

    def __init__(self):
        # n: the total number of nodes in the level, including the gateways
        # l: the number of links
        # e: the number of exit gateways
        n, l, e = [int(j) for j in input().split()]
        self.graph = {i: [] for i in range(n)}

        for _ in range(l):
            # n1: N1 and N2 defines a link between these nodes
            n1, n2 =  [int(j) for j in input().split()]
            self.graph[n1].append(n2)
            self.graph[n2].append(n1)

        self.exit_gateways = [int(input()) for _ in range(e)] # the index of a gateway node

    def breadth_first_search(self, root):
        print(f"Graph nodes: {self.graph}", file=sys.stderr)

        visited, queue = set(), deque([Binder(root, None)])
        visited.add(root)

        while queue:
            binder = queue.popleft()
            vertex = binder.id
            print(f"Bobnet Location: {self.graph[vertex]}", file=sys.stderr)

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    new_binder = Binder(neighbor, binder)
                    queue.append(new_binder)

                if neighbor in self.exit_gateways:
                    return Binder(neighbor, binder)
                            
def trace_and_cut_link(result_binder):
    current_binder = result_binder
    while current_binder.pre_binder is not None:
        previous_binder = current_binder.pre_binder
        link_to_cut = (previous_binder.id, current_binder.id)
        print(f'Cutting link: {link_to_cut}', file=sys.stderr)
        current_binder = previous_binder
    print(link_to_cut[0], link_to_cut[1])

game = Game()

while True:
    node_index = int(input())  # The index of the node on which the Bobnet agent is positioned this turn
    result_binder = game.breadth_first_search(node_index)
    trace_and_cut_link(result_binder)

Game information:
Graph nodes: {0: [2, 10, 9, 5, 12, 11, 17, 7, 13, 14, 6, 3, 4, 15, 1, 16, 8], 
1: [2, 17, 0, 37], 
2: [0, 37, 1, 3, 35], 
3: [34, 0, 2, 4], 
4: [5, 33, 0, 3], 
5: [4, 0, 6], 
6: [5, 0, 7], 
7: [8, 0, 6], 
8: [7, 9, 0], 
9: [0, 10, 8], 
10: [0, 11, 9], 
11: [10, 0, 12], 
12: [0, 11, 13], 
13: [14, 0, 12], 
14: [13, 0, 15], 
15: [16, 14, 0], 
16: [17, 15, 0], 
17: [16, 0, 1], 
18: [26, 24, 23, 22, 27, 25, 21, 19, 20], 
19: [27, 20, 18], 
20: [19, 21, 18], 
21: [29, 22, 18, 20], 
22: [18, 23, 21, 36], 
23: [18, 24, 35, 22, 37], 
24: [18, 23, 25, 37], 
25: [26, 24, 18], 
26: [18, 25, 27], 
27: [19, 18, 26], 
28: [36, 32, 34, 31, 35, 29, 33, 30], 
29: [21, 30, 28, 36], 
30: [31, 29, 28], 
31: [30, 28, 32], 
32: [28, 33, 31], 
33: [32, 4, 34, 28], 
34: [3, 35, 28, 33], 
35: [37, 34, 23, 28, 36, 2], 
36: [28, 22, 35, 29], 
37: [35, 2, 23, 1, 24]}

Block the Agent!
Agent is at position 37

Standard Output Stream:
37 35
Game information:
Link [37-35] severed
Agent moved from 37 to 2

Standard Output Stream:
2 0
Game information:
Link [2-0] severed
Agent moved from 2 to 35

Standard Output Stream:
35 28
Game information:
Link [35-28] severed
Agent moved from 35 to 23

提前谢谢您。

Answer 1

为了防止智能体从当前位置移动到任何节点，从当前位置切掉所有出边就足够了。

如果我正确解释你的图像，这意味着切割三个边缘（蓝线）

无论如何，这都是一个微不足道的任务，不需要 BFS。