python - 一组开关和灯的最大流量

Question

有的开关和灯是装墙的，一个开关只能接一盏灯。灯、开关和墙壁以这种形式给出 x,y 点。

Walls = [(1,2),(1,5),(8,5),(8,3),(11,3),(11,1),(5,1),(5,3),(4,3),(4,1),(1,1),(1,2)]

Lights = [(2,4),(2,2),(5,4)]  # In red can only be turned on by one switch

Switches = [(4,4),(6,3),(6,2)] # In green can only turn on one light

graph = {}

residual = {}

def ccw(A,B,C):
    return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])
# Return true if line segments AB and CD intersect
# Source: http://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def visible(pt1,pt2,Walls):
    x1,y1 = pt1
    x2,y2 = pt2
    for i,wall in enumerate(Walls[:-1]):
        x3,y3 = wall
        x4,y4 = Walls[i+1]
        if intersect((x1,y1),(x2,y2),(x3,y3),(x4,y4)):
            return False
    return True

def edges(L,M):

    # Empty dictionary that will store the edges
    graph['End'] = []
    for i in range(0, len(L)):  # for all the switches stores them as the key
        graph[M[i]] = []
    for switch in range(0, len(M)):   # for all the switches check to see what lights are visible
        for light in range(0, len(M)):
            if visible(M[switch],L[light],Walls) == True:
                graph[M[switch]].append(L[light])    # If the lights are visible store them in a list as the value
    graph['start'] = []
    for switch in range(0, len(M)):   # Connects the start (sink) to the switches
        graph['start'].append(M[switch])
    for light in range(0, len(L)):   # Connects each light to the End (sink)
        graph[L[light]] = ['End']
    return graph

def bfs_shortest_path(graphs, s, t): # from https://pythoninwonderland.wordpress.com/2017/03/18/how-to-implement-breadth-first-search-in-python/ Valerio Velardo
    # keep track of explored nodes

    global graph

    visited = []
    # keep track of all the paths to be checked
    queue = [[s]]

    # return path if start is goal
    if s == t:
        return "That was easy! Start = goal"

    # keeps looping until all possible paths have been checked
    while queue:
        # pop the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        if node not in visited:
            newnode = graph[node]
            # go through all neighbour nodes, construct a new path and
            # push it into the queue
            for othernodes in newnode:
                newedgest = list(path)
                newedgest.append(othernodes)
                queue.append(newedgest)
                # return path if neighbour is goal
                if othernodes == t:
                    return newedgest, True

            # mark node as explored
            visited.append(node)

    # in case there's no path between the 2 nodes
    return "So sorry, but a connecting path doesn't exist :(", False

def maxflow(graphs):
        # Path taken
        graph = edges(Lights, Switches)
        path, tf = bfs_shortest_path(graph,'start','End')

        while tf == True:


            # for all the nodes in the graph delete them so they cannot be travelled to
            for i in graph['start']:
                if i in path:
                    graph['start'].remove(i)  # Removes first node in graph aka Switch
                    print(graph,'switch removed')
            for newnode in graph[path[1]]:
                if newnode in path:
                    graph[path[1]].remove(newnode)  # Removes next node aka Light
                    print(graph, 'light removed')
            for othernode in graph[path[2]]:
                    if othernode in path:
                        graph[path[2]].remove(othernode)
                        print(graph, 'end removed')
                        residual = graph
            return residual, 'residual graph'

print(maxflow(graph))
print(graph)

newgraph = {'End': [], (4, 4): [(2, 2), (5, 4)], (6, 3): [(2, 4), (5, 4)], (6, 2): [(5, 4)], 'start': [(6, 3), (6, 2)], (2, 4): [], (2, 2): ['End'], (5, 4): ['End']}

print(bfs_shortest_path(newgraph, 'start', 'End'))

预期结果应该是最大流量输出值，表示所有 3 个开关都连接到一盏灯并且可见，不会干扰任何墙壁。

Here is the book problem

Answer 1

我认为这个问题的挑战在于如何将布线问题表达为流问题。从那以后，大概你会使用你学到的算法来计算流量。

我们可以这样概念化它:

• 源 s 连接到开关 [sw1, ..., swN]，整数流量为 1(每个都有电源)<
• 每个开关可能与每个灯泡[b1, ..., bN] 相连，整数流量为 1(此灯泡有电切换与否)
• 每个灯泡连接到水槽t，整数容量为1(灯泡是否发光)

每个开关只有一个可用电源，每个灯泡最多只能从开关接受 1 个电源，这实际上意味着它们只能连接到唯一的灯泡。如果我们排除穿过墙壁的连接并且我们所有的灯泡都亮着，则必须有符合人体工程学的布局(尽管我们不知道它是什么)。

因此，该算法的主要步骤是:

• 通过排除与墙壁相交的任何线，找出哪些开关实际上连接到每个灯泡
• 如上所述构建图表(源到开关，开关到灯泡，灯泡到水槽)
• 计算图的最大流
  • 如果流量等于灯泡的数量，则存在符合人体工程学的布局

我的猜测是计算流量的算法可能已经在文本的前面提供了，所以我把那部分留给读者作为练习:)