我正在尝试制作一款游戏，玩家必须在游戏板上从头到尾找到自己的方式。
如您所见，此游戏板包含一堆红色圆形障碍物。为了赢得比赛，玩家必须消除最少数量的障碍。所以我的问题是，我如何以编程方式找出要移除的最少障碍物，以释放路径？自由路径将被视为圆圈之间的空间，圆圈不重叠且不接触。
所以我真正需要的是要删除的最小圆圈数量，我不需要实际路径。是否有捷径可寻？
并且为了补充对这个棋盘的理解，每个圆都有相同的半径，并且受到黑线的限制。
此外，不必沿直线移动。
问问题
2481 次
5 回答
17
这是一个图论maximum flow问题。
假设每个圆圈都是图中的一个节点。另外引入 2 个特殊节点：TOP和BOTTOM. 如果这些节点与 TOP/BOTTOM 侧相交，则将圆圈与这些节点连接起来。如果圆相交，则将圆对应的节点相互连接。
现在您需要在此图中找到一个最小割，将TOP 作为源，将BOTTOM 作为汇，反之亦然。您可以使用Max-flow_min-cut_theorem来解决它。它所说的Minimum-cut problem是相当于最大流量问题。Max-Flow problem您可以在TopCoder上找到有关如何解决的详细信息。
由于我们只能通过每个节点一次，我们应该将节点转换为容量为 1 的有向边，每个圆都有入节点和出节点。最大流算法将解决结果图上的问题，并考虑到我们正在删除圆圈而不是圆圈之间的连接这一事实。对于这个问题，删除图中的节点而不是边总是一个更好的决定，因为我们总是可以通过删除节点来删除任何边。额外移除一个节点可能会导致移除多个边。
顺便说一句，在Uva Online Judge上也可以找到类似的问题。尝试在法官上解决此任务是个好主意，那么您将确定您的解决方案是正确的。
于 2010-10-28T10:10:41.617 回答
13
在试图形象化列昂尼德写的东西时，我制作了下图。
于 2010-10-28T14:12:38.447 回答
6
对于图形翻译，这样的事情可能会起作用。
如果两个圆圈重叠，则在它们之间制作一堵墙（蓝线）。不要忘记添加顶部和底部边框。这会创建几个区域。这些将是图的所有节点。
接下来我们必须找到边，从一个节点到另一个节点的成本。取两个相邻区域（共享一堵墙）。然后通过蛮力，或者你想出的任何聪明的方法，确定从这个区域移动到另一个区域的成本。如果你移除一个圆圈，这意味着你移除了通往该圆圈的所有墙壁。如果这使两个区域成为一个区域，则边缘的成本为 1。如果您需要移除两个圆（它们拥有的所有墙壁）来组合两个区域，则成本为 2。等等。
绘制了一些边缘（绿色）。我们必须从起始区域到结束区域。你现在得到了一个每日加权图。
我认为这可以改进很多，但我把它留作练习=）
在这种情况下，最小值为 3。
警告，图片是手绘的，我确实忘记了一些墙壁、边缘和区域。仅用于说明目的。
于 2010-10-28T10:38:11.777 回答
3
好吧，所以我决定在 pygame 中对此进行可视化。
结果比我预想的要困难得多。
其他建议中的想法是使用Max Flow。从源到汇的流动瓶颈是流动最密集的地方。如果我们在这个密集的瓶颈处将图形切成两半（即在min-cut处），那么我们有最小的圆数。maxflow = min-cut 就是这样发生的。
这是我采取的步骤：
如果我可以随机生成圆圈，请创建 pygame 世界
制作函数来计算圆之间的所有碰撞：
这涉及按 x 坐标对圆圈进行排序。现在要找到 Circle[0] 的所有碰撞，我继续沿着数组测试碰撞，直到找到一个 x 值大于 2*radius 大于 circle[0]sx 值的圆，然后我可以弹出 circle[0 ]并重复该过程..
- 创建源节点和汇节点，找出它们需要连接的圈子。
步骤 4-5 在“ findflow()函数”中执行
创建表示带有节点的圆的基本无向 networkX 图。只有当它们对应的圆发生碰撞时才连接节点。
这就是它开始变得困难的地方。我从我的无向图创建一个新的有向图。因为我需要通过圆（即节点）而不是边缘来计算流量，所以我需要将每个节点分成两个节点，中间有一条边。
假设我将节点 X 连接到节点 Y (Y<->X) （在原始图中）。
我将 X 更改为 Xa 和 Xb，以便 Xa 连接到 Xb (Xa->Xb) Y 也更改为 (Ya->Yb)。
我还需要添加 (Yb->Xa) 和 (Xb->Ya) 来表示 X 和 Y 之间的原始连接。
无向图中的所有边都被赋予容量=1（例如，您只能穿过一个圆圈一次）
- 我现在申请networkx。我的新有向图上的ford_fulkerson()算法。这为我找到了flowValue 和 flowGraph。
flowValue 是一个整数。它是最小切割（或从源到汇的最大流量）。这是我们一直在寻找的答案。它表示我们需要删除的最小圆圈数。
奖金分配：
我想..为什么停在这里，有要删除的圆圈数量很好，但我想知道我需要删除的确切圆圈。为此，我需要找出最小切割在 flowGraph 上实际发生的位置。我设法弄清楚如何做到这一点，但是我的实现在某处有一个错误，所以它有时会稍微错误地选择剪切，从而得到错误的圆圈。
为了找到最小切割，我们将使用在步骤 6 中生成的 flowGraph。这个想法是这个图的瓶颈将是最小切割。如果我们尝试从源到汇，我们将卡在瓶颈处，因为瓶颈周围的所有边缘都将处于最大容量。所以我们简单地使用 DFS（深度优先搜索）尽可能地向下流动。DFS 只允许沿着流程图中未达到最大容量的边移动。（例如，他们的流量是 0 而不是 1）。使用源中的 DFS，我记下了我可以看到的所有节点，将它们存储在 self.seen 中。现在在 DFS 之后，对于看到的所有节点，我检查该节点是否具有与在 DFS 中未看到的节点相比的最大容量边缘。所有这些节点都在最小切割上。
这是我运行的其中一个模拟的图片：
移除圆圈后，我用颜料填充它（您可能需要放大一点才能看到圆圈之间确实存在间隙）：
学习：
即使在 python 中速度也可以，可以运行 1000 圈。
这比我想象的要难，而且我在尝试使用 DFS 查找原始圆圈时仍然存在错误。（如果有人可以帮助找到很棒的错误）。
代码起初很优雅，尽管我不断添加技巧来更改可视化等。
工作代码（除了 DFS 中偶尔出现的轻微错误）：
__author__ = 'Robert'
import pygame
import networkx
class CirclesThing():
def __init__(self,width,height,number_of_circles):
self.removecircles = False #display removable circles as green.
self.width = width
self.height = height
self.number_of_circles = number_of_circles
self.radius = 40
from random import randint
self.circles = sorted(set((randint(self.radius,width-self.radius),randint(2*self.radius,height-2*self.radius)) for i in range(self.number_of_circles)))
self.sink = (self.width/2, self.height-10)
self.source = (self.width/2, 10)
self.flowValue,self.flowGraph = self.find_flow()
self.seen = set()
self.seen.add(self.source)
self.dfs(self.flowGraph,self.source)
self.removable_circles = set()
for node1 in self.flowGraph:
if node1 not in self.seen or node1==self.source:
continue
for node2 in self.flowGraph[node1]:
if self.flowGraph[node1][node2]==1:
if node2 not in self.seen:
self.removable_circles.add(node1[0])
def find_flow(self):
"finds the max flow from source to sink and returns the amount, along with the flow graph"
G = networkx.Graph()
for node1,node2 in self.get_connections_to_source_sink()+self.intersect_circles():
G.add_edge(node1,node2,capacity=1)
G2 = networkx.DiGraph()
for node in G:
if node not in (self.source,self.sink):
G2.add_edge((node,'a'),(node,'b'),capacity=1) #each node is split into two new nodes. We add the edge between the two new nodes flowing from a to b.
for edge in G.edges_iter():
if self.source in edge or self.sink in edge:
continue #add these edges later
node1,node2 = edge
G2.add_edge((node1,'b'),(node2,'a'),capacity=1) #if we flow through a circle (from node1a to node1b) we need to be able to flow from node1b to all node1's children
G2.add_edge((node2,'b'),(node1,'a'),capactiy=1) #similarly for node2..
for node in G[self.source]:
G2.add_edge(self.source,(node,'a'))
for node in G[self.sink]:
G2.add_edge((node,'b'),self.sink)
flowValue, flowGraph = networkx.ford_fulkerson(G2,self.source,self.sink)
return flowValue, flowGraph
def dfs(self,g,v):
"depth first search from source of flowGraph. Don't explore any nodes that are at maximum capacity. (this means we can't explore past the min cut!)"
for node in g[v]:
if node not in self.seen:
self.seen.add(node)
if g[v][node]!=1 or v==self.source:
self.dfs(g,node)
def display(self):
self.draw_circles()
self.draw_circles(circle_radius=5, circle_colour=(255,0,0))
if not self.removecircles:
lines = self.intersect_circles()
self.draw_lines(lines)
self.draw_source_sink()
def draw_circles(self,circle_radius=None,circle_colour=(0,0,255),circles=None):
if circle_radius is None:
circle_radius = self.radius
if circles is None:
circles = self.circles
circle_thickness = 2
for pos in circles:
cc = circle_colour if pos not in self.removable_circles else (100,200,0) #change colour of removable circles
ct = circle_thickness if pos not in self.removable_circles else 4 #thicken removable circles
if pos not in self.removable_circles or not self.removecircles:
pygame.draw.circle(screen, cc, pos, circle_radius, ct)
def intersect_circles(self):
colliding_circles = []
for i in range(len(self.circles)-1):
for j in range(i+1,len(self.circles)):
x1,y1 = self.circles[i]
x2,y2 = self.circles[j]
if x2-x1>2*self.radius+5: #add 5 to make a more obvious gap visually
break #can't collide anymore.
if (x2-x1)**2 + (y2-y1)**2 <= (2*self.radius)**2+5:
colliding_circles.append(((x1,y1),(x2,y2)))
return colliding_circles
def draw_lines(self,lines,line_colour=(255, 0, 0)):
for point_pair in lines:
point1,point2 = point_pair
try:
tot = self.flowGraph[(point1,'b')][(point2,'a')] + self.flowGraph[(point2,'b')][(point1,'a')] #hack, does anything flow between the two circles?
except KeyError:
tot = 0
thickness = 1 if tot==0 else 3
lc = line_colour if tot==0 else (0,90,90)
pygame.draw.line(screen, lc, point1, point2, thickness)
def draw_source_sink(self):
self.draw_circles(circles=(self.sink,self.source),circle_radius=15,circle_colour=(0,255,0))
bottom_line = ((0,self.height-3*self.radius),(self.width,self.height-3*self.radius))
top_line = ((0,3*self.radius),(self.width,3*self.radius))
self.draw_lines([top_line, bottom_line],line_colour=(60,60,60))
if not self.removecircles:
self.draw_lines(self.get_connections_to_source_sink(),line_colour=(0,255,0))
def get_connections_to_source_sink(self):
connections = []
for x,y in self.circles:
if y<4*self.radius:
connections.append((self.source,(x,y)))
elif y>height-4*self.radius:
connections.append((self.sink,(x,y)))
return connections
def get_caption(self):
return "flow %s, circles removes %s" %(self.flowValue,len(self.removable_circles))
time_per_simulation = 5 #5 seconds
width, height = 1400, 600
background_colour = (255,255,255)
screen = pygame.display.set_mode((width, height))
screen.fill(background_colour)
from pygame.locals import USEREVENT
pygame.time.set_timer(USEREVENT+1,time_per_simulation*1000)
simulations = 0
simulations_max = 20
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if event.type == USEREVENT+1:
if simulations % 2 ==0:
world = CirclesThing(width,height,120) #new world
else:
world.removecircles = True #current world without green circles
screen.fill(background_colour)
world.display()
pygame.display.set_caption(world.get_caption())
pygame.display.flip()
if simulations>=2*simulations_max:
running = False
simulations+=1
if False:
pygame.image.save(screen,'sim%s.bmp'%simulations)
于 2012-03-23T02:44:31.203 回答
1
一种选择是首先删除那些重叠或接触次数最多的圆圈。每次删除后，检查它是否有解决方案，如果没有，请继续删除。
var circle;
circle = findMostOverlapCircle();
while(circle != null) {
circle.remove();
circle = findMostOverlapCircle();
}
于 2010-10-28T10:04:04.160 回答