Хорошо, поэтому я решил сделать визуализацию этого в Pygame.
Оказалось намного сложнее, чем я ожидал .
Идея какв других предложениях стоит использовать Max Flow .Узкое место в потоке от источника к раковине - там, где поток наиболее плотный.Если мы разрежем график пополам на этой плотной горлышке бутылки (т. Е. На min-cut ), то получим минимальное количество кругов.Так случилось, что maxflow = min-cut.
Вот шаги, которые я предпринял:
Создать мир пигмеев, в котором я могу случайным образом генерировать круги
Создать функцию для обработки всех столкновений между кругами:
Это включало сортировку окружностей по координате х.Теперь, чтобы найти все столкновения Circle [0], я продолжаю двигаться по массиву, проверяя наличие столкновений, пока не найду круг, значение x которого больше чем на 2 * радиуса больше значения x круга [0], тогда я могу всплыть круг [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 действительно происходит мини-срез.Мне удалось выяснить, как это сделать, однако моя реализация где-то содержит ошибку, поэтому иногда она выбирает немного неправильный срез и, следовательно, получает неправильные круги.
Чтобы найти минимальный срез, мы будем использовать flowGraphпроизводится в шаге 6.Идея состоит в том, что узким местом этого графика будет минимальное сокращение.если мы попробуем перетекать из источника в раковину, мы застрянем в горлышке бутылки, так как все края вокруг узкого горла будут на максимальной мощности.Таким образом, мы просто используем 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)