Хорошо, поэтому я решил сделать визуализацию этого в pygame.
Это оказалось намного сложнее, чем я ожидал.
Идея, как и в других предложениях, заключается в использовании Max Flow. Узкое место в потоке от истока к стоку находится там, где поток наиболее плотный. Если мы разрежем график пополам в этом плотном узком месте (т. е. в точке min-cut), то получим минимальное количество кругов. Так получается, что макспоток = мин-рез.
вот шаги, которые я предпринял:
Создайте мир pygame, в котором я могу случайным образом генерировать круги
Сделать функцию для обработки всех столкновений между кругами:
Это включало сортировку кругов по координате x. Теперь, чтобы найти все столкновения 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.
значение потока является целым числом. Это минимальная отсечка (или максимальный поток от источника к стоку). Это ответ, который мы искали. Он представляет собой минимальное количество кругов, которые нам необходимо удалить.
Бонусное задание:
Я подумал... зачем останавливаться на этом, иметь количество кругов, которые нужно удалить, это хорошо, но я хочу знать, какие именно круги мне нужно удалить. Для этого мне нужно выяснить, где на самом деле происходит минимальное отсечение на потоковом графике. Мне удалось выяснить, как это сделать, однако в моей реализации где-то есть ошибка, поэтому иногда она выбирает разрез немного неправильно и поэтому получает неправильные круги.
Чтобы найти минимальный разрез, мы будем использовать потоковую диаграмму, созданную на шаге 6. Идея состоит в том, что узким местом этого графика будет минимальная отсечка. если мы попытаемся течь от источника к стоку, мы застрянем в горлышке бутылки, так как все края вокруг узкого места будут на максимальной мощности. Поэтому мы просто используем DFS (Поиск в глубину), чтобы спуститься как можно дальше. DFS разрешено перемещаться только по ребрам, которые не имеют максимальной пропускной способности в потоковом графе. (например, их поток равен 0, а не 1). Используя DFS из источника, я записал все узлы, которые я мог видеть, сохраняя их в self.seen. Теперь, после DFS, для всех видимых узлов я проверяю, имеет ли узел максимальную пропускную способность по сравнению с узлом, который не был замечен в DFS. Все такие узлы находятся на мин-разрезе.
Вот изображение одной из симуляций, которые я запускал:
и, удалив круги, я залил его краской (возможно, вам придется немного увеличить масштаб, чтобы увидеть, что между кругами действительно есть зазор):
Обучение:
Скорость нормальная даже на питоне, пробегает 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)
person
robert king
schedule
23.03.2012
