Алгоритм поиска решения головоломки

Ответ 1

Это проблема теории графов maximum flow.

Предположим, что каждый круг является node в графе. Дополнительно добавьте 2 специальных узла: TOP и BOTTOM. Соедините круги с этими узлами, если они пересекаются со стороной TOP/BOTTOM. Соедините узлы, соответствующие кругам друг с другом, если круги пересекаются.

Теперь вам нужно найти минимальный разрез на этом графике, имеющий TOP как источник и BOTTOM как приемник или наоборот. Вы можете использовать Max-flow_min-cut_theorem, чтобы решить эту проблему. То, что он утверждает, состоит в том, что Minimum-cut problem равносильно задаче Макс. Потока. Вы можете найти информацию о том, как решить Max-Flow problem на TopCoder.

Поскольку мы можем пройти через каждый node только один раз, мы должны преобразовать узлы в направленный фронт емкости с ин node и out-node для каждого круга. Алгоритм максимального потока решает проблему на полученном графике и учитывает тот факт, что мы удаляем круги, а не соединения между кругами. Всегда лучше решить эту проблему, чтобы удалить node в графе, а не в край, поскольку мы всегда можем удалить любое ребро, удалив node. Удаление node дополнительно может привести к удалению более одного края.

Кстати, аналогичную проблему можно найти на Uva Online Judge. Это хорошая идея, чтобы попытаться решить эту задачу у судьи, тогда вы будете уверены, что ваше решение верное.

Ответ 2

Пытаясь визуализировать то, что написал Леонид, я сделал следующую диаграмму.

Ответ 3

Для графического перевода возможно что-то подобное.

Создайте стену (синие линии) между двумя кругами, если они перекрываются. Не забудьте также добавить верхнюю и нижнюю границу. Это создает пару регионов. Это будут все узлы графика.

Далее мы должны найти ребра, стоимость перехода от одного node к другому. Возьмите две соседние области (разделяя стену). Затем, используя грубую силу или какой бы хитрый метод вы придумали, определите стоимость перехода от этого региона к другому. Если вы удалите круг, это означает, что вы удаляете все стены, которые идут в этот круг. Если это делает две области в одной области, стоимость края равна 1. Если вам нужно удалить два круга (все стены, которые у них есть), чтобы объединить две области, стоимость равна 2. Etc.

Некоторые края (зеленые) нарисованы. Мы должны идти от начального региона, до конца региона. Теперь вы получаете ежедневный взвешенный график.

Я думаю, что это можно улучшить, но я оставляю это как упражнение =)

В этом случае минимум равен 3.

Предупреждение, рисунок рисуется вручную, я забыл несколько стен, краев и областей. Только для иллюстрации.

Ответ 4

Хорошо, поэтому я решил сделать визуализацию этого в pygame.

Это оказалось намного сложнее, чем я ожидал.

Идея, как и в других предложениях, заключается в использовании Max Flow. Узкое место в потоке от источника до потолка - это место, где поток наиболее плотный. Если мы вырезаем граф пополам на этой плотной горловине бутылки (т.е. На min-cut), мы получим минимальное количество окружностей. Так происходит maxflow = min-cut.

вот шаги, которые я сделал:

• Создайте мир pygame, я могу произвольно создавать круги

• Сделать функцию для обработки всех столкновений между кругами:

Это включало сортировку окружностей по координате x. Теперь, чтобы найти все столкновения Circle [0], я продолжаю двигаться по массиву, проверяя для столкновений, пока не найду круг, значение x которого больше радиуса 2 * больше, чем значение круга [0] x, тогда я могу поп-кружок [0] и повторите процесс.

3. Создайте узлы источника и приемника, определите, с какими кругами они должны подключиться.

Этапы 4-5 выполняются в функции findflow() "

4. Создайте базовый неориентированный график сети X, представляющий круги с узлами. Соединение узлов только в том случае, если их соответствующие круги сталкиваются.

5. И здесь он начинает усердно. Я создаю новый ориентированный граф из моего неориентированного графика. Поскольку мне нужно было проработать поток через круги (т.е. Узлы), а не ребра, мне нужно разделить каждый node на два узла с краем между ними.

   Допустим, что у меня есть node X, связанный с node Y (Y ↔ X) (в исходном графе).

   Я меняю X на Xa и Xb так, что Xa соединяется с Xb (Xa- > Xb) Также Y изменяется на (Ya- > Yb).

   Мне также нужно добавить (Yb- > Xa) и (Xb- > Ya), чтобы представить исходное соединение между X и Y.

Все ребра в неориентированном графе задаются как емкость = 1 (например, вы можете пересекать только круг один раз)

6. Теперь я применил алгоритм networkx. ford_fulkerson() на моем новом ориентированном графе. Это находит меня flowValue и flowGraph.

значение currentValue является целым числом. Это минимальный разрез (или максимальный поток от источника к потоку). Это ответ, который мы искали. Он представляет минимальное количество окружностей, которые мы должны удалить.

Назначение бонуса:

Я подумал... зачем останавливаться здесь, имея число удаляемых кругов, приятно, но я хочу знать точные круги, которые нужно удалить. Для этого мне нужно выяснить, где минимальный разрез на самом деле происходит на flowGraph. Мне удалось выяснить, как это сделать, однако в моей реализации есть ошибка где-то, поэтому она иногда неправильно выбирает разрез и поэтому получает неправильные круги.

Чтобы найти минимальный разрез, мы будем использовать flowGraph, созданный на шаге 6. Идея состоит в том, что узким местом этого графика будет минимальный разрез. если мы попробуем поток от источника к потоку, мы застрянем на горлышке бутылки, так как все края вокруг узкого места будут иметь максимальную емкость. Таким образом, мы просто используем DFS (Глубина первого поиска), чтобы течь вниз, насколько это возможно. DFS разрешено перемещаться по ребрам, которые не имеют максимальной емкости в потоковом графике. (например, их поток равен 0 не 1). Используя DFS из источника, я продолжал замечать все узлы, которые я мог видеть, сохраняя их в self.seen. Теперь после DFS, для всех рассматриваемых узлов, я проверяю, имеет ли край node край максимальной емкости node, который не был замечен в 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 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)

Ответ 5

Один из вариантов состоит в том, чтобы сначала удалить эти круги с наибольшим количеством перекрытий или касаний. После каждого из них вы удаляете, проверяете, если его решение, если оно не продолжит удаление.

var circle;
circle = findMostOverlapCircle();
while(circle != null) {
    circle.remove();
    circle = findMostOverlapCircle();
}