Algorithme pour trouver la solution d'un puzzle

Question

J'essaie de créer un jeu dans lequel un joueur doit trouver son chemin du début à la fin sur le plateau de jeu.

Comme vous le voyez, ce plateau de jeu contient un tas d'obstacles circulaires rouges. Pour gagner la partie, le joueur doit éliminer un nombre minimum d'obstacles. Ma question est donc la suivante : comment puis-je déterminer par programme le nombre minimum d'obstacles à supprimer pour libérer un chemin ? Un chemin libre serait considéré comme l'espace entre des cercles qui ne se chevauchent pas et ne se touchent pas.

Ce dont j'ai vraiment besoin, c'est du nombre minimum de cercles à supprimer, je n'ai pas besoin de la trajectoire réelle. Existe-t-il un moyen simple de faire cela ?

Et pour compléter la compréhension de ce plateau de jeu, les cercles ont tous le même rayon, et il est limité par les lignes noires.

De plus, il n'est pas nécessaire de se déplacer en ligne droite.

Answer 1

Il s'agit d'une théorie des graphes maximum flow problème.

Supposons que chaque cercle soit un nœud du graphe. En outre, introduisez 2 nœuds spéciaux : TOP y BOTTOM . Connectez les cercles avec ces nœuds s'ils se croisent avec le côté TOP/BOTTOM. Connecter les nœuds correspondant aux cercles entre eux si les cercles se croisent.

Maintenant, vous devez trouver une coupe minimale dans ce graphique, ayant TOP comme source y BOTTOM comme évier ou vice versa. Vous pouvez utiliser Théorème de la coupe max-flow_min pour le résoudre. Ce qu'il dit, c'est que Minimum-cut problem est équivalent au problème de Max-flow. Vous pouvez trouver des détails sur la façon de résoudre Max-Flow problem en TopCoder .

Comme nous ne pouvons passer par chaque nœud qu'une seule fois, nous devons convertir les nœuds en une arête dirigée de capacité un avec un nœud d'entrée et un nœud de sortie pour chaque cercle. L'algorithme max-flow résoudra le problème sur le graphe résultant et tiendra compte du fait que nous supprimons des cercles plutôt que des connexions entre cercles. Il est toujours préférable pour ce problème de supprimer un nœud dans un graphe plutôt qu'une arête, car nous pouvons toujours supprimer une arête en supprimant un nœud. La suppression d'un nœud peut également entraîner la suppression de plus d'une arête.

A propos, un problème similaire peut être trouvé sur Juge en ligne Uva . C'est une bonne idée d'essayer de résoudre cette tâche sur le juge, vous serez alors sûr que votre solution est correcte.

Answer 2

En essayant de visualiser ce que Leonid a écrit, j'ai fait le schéma suivant.

Answer 3

Pour la traduction d'un graphique, quelque chose comme ceci pourrait fonctionner.

Faites un mur (les lignes bleues) entre deux cercles s'ils se chevauchent. N'oubliez pas d'ajouter également la bordure supérieure et inférieure. Cela crée deux régions. Celles-ci seront tous les nœuds du graphe.

Ensuite, nous devons trouver les arêtes, c'est-à-dire le coût pour aller d'un nœud à l'autre. Prenez deux régions voisines (partageant un mur). Puis, par force brute, ou toute autre méthode intelligente que vous trouverez, déterminez le coût du déplacement de cette région à l'autre. Si vous supprimez un cercle, cela signifie que vous supprimez tous les murs qui vont vers ce cercle. Si cela transforme les deux régions en une seule, le coût de l'arête est de 1. Si vous devez enlever deux cercles (tous les murs qu'ils ont) pour combiner les deux régions, le coût est de 2. Etc.

Certains des bords (verts) sont dessinés. Nous devons aller de la région de départ à la région d'arrivée. Vous avez maintenant un graphe pondéré quotidien.

Je pense que cela peut être beaucoup amélioré, mais je laisse cela comme un exercice =)

Dans ce cas, le minimum est de 3.

Attention, l'image est dessinée à la main, j'ai oublié quelques murs, bords et régions. A des fins d'illustration uniquement.

Answer 4

Bon, j'ai décidé de faire une visualisation de ceci dans pygame.

Il s'est avéré que c'était beaucoup plus difficile que prévu .

L'idée, comme dans d'autres suggestions, est d'utiliser Débit maximal . Le goulot d'étranglement dans le flux de la source au puits est l'endroit où le flux est le plus dense. Si nous coupons le graphe en deux au niveau de ce goulot d'étranglement dense (c'est-à-dire à l'endroit où le flux est le plus dense), le graphe sera coupé en deux. min-cut ) alors nous avons le nombre minimum de cercles. Il se trouve que le maxflow = min-cut.

Voici les étapes que j'ai suivies :

1. Créer un monde pygame où je peux générer des cercles de façon aléatoire.

2. Créez une fonction pour calculer toutes les collisions entre les cercles :

Il s'agissait de trier les cercles par coordonnée x. Maintenant, pour trouver toutes les collisions du cercle [0], je continue à me déplacer le long du tableau en testant les collisions jusqu'à ce que je trouve un cercle dont la valeur x est supérieure de plus de 2*radius à la valeur x du cercle [0], alors je peux sortir le cercle [0] et répéter le processus

3. Créer des nœuds source et puits pour savoir à quels cercles ils doivent se connecter.

Les étapes 4 à 5 sont réalisées dans la " findflow() fonction"

4. Créez un graphique de base en réseau non dirigéX représentant des cercles avec des nœuds. Connecter les nœuds uniquement si leurs cercles correspondants entrent en collision.

5. Et c'est là que ça commence à être dur I créer un nouveau graphe orienté à partir de mon graphe non orienté . Comme je devais calculer le flux à travers des cercles (c'est-à-dire des nœuds) et non des arêtes, je dois diviser chaque nœud en deux nœuds séparés par une arête.

   Disons que le nœud X est connecté au nœud Y (Y<->X) (dans le graphique original).

   Je change X en Xa et Xb de sorte que Xa se connecte à Xb (Xa->Xb) De même, Y se transforme en (Ya->Yb).

   Je dois également ajouter (Yb->Xa) et (Xb->Ya) pour représenter la connexion originale entre X et Y.

Toutes les arêtes du graphe non orienté ont une capacité = 1. (par exemple, vous ne pouvez traverser un cercle qu'une seule fois)

6. J'applique maintenant Networkx. ford_fulkerson() sur mon nouveau graphe dirigé. Cela me permet de trouver flowValue et le flowGraph.

la valeur du flux est un nombre entier. Il s'agit de la coupe minimale (ou du débit maximal de la source au puits). C'est la réponse que nous cherchions . Il représente le nombre minimum de cercles que nous devons supprimer.

Attribution de bonus :

J'ai pensé pourquoi s'arrêter là, avoir le nombre de cercles à supprimer est bien, mais je veux connaître les cercles exacts que je dois supprimer. Pour ce faire, je dois trouver l'endroit où la coupe minimale se produit réellement sur le flowGraph. J'ai réussi à comprendre comment faire cela, mais mon implémentation a un bug quelque part, de sorte qu'elle choisit parfois la coupe légèrement mal et obtient donc les mauvais cercles.

Pour trouver la coupe minimale, nous utiliserons le flowGraph produit à l'étape 6. L'idée est que le goulot d'étranglement de ce graphe sera la coupe minimale. Si nous essayons de faire circuler le flux de la source vers le puits, nous serons bloqués au niveau du goulot d'étranglement car toutes les arêtes autour du goulot d'étranglement seront à leur capacité maximale. Nous utilisons donc simplement DFS ( Recherche en profondeur ) pour descendre aussi loin que possible. Le site Le DFS n'est autorisé à se déplacer que sur les bords qui ne sont pas à leur capacité maximale. dans le graphe des flux. (par exemple, leur flux est 0 et non 1). En utilisant DFS depuis la source, j'ai noté tous les nœuds que je pouvais voir en les stockant dans self.seen. Maintenant, après DFS, pour tous les nœuds dans seen, je vérifie si le nœud a un bord de capacité maximale vers un nœud qui n'a pas été vu dans DFS. Tous ces noeuds sont sur la coupe minimale.

Voici une photo de l'une des simulations que j'ai effectuées :

et après avoir enlevé les cercles, je l'ai rempli de peinture (vous devrez peut-être zoomer un peu pour voir qu'il y a bien un espace entre les cercles) :

Apprentissages :

La vitesse est correcte même en python, elle fonctionne pour 1000 cercles.

C'était plus difficile que je ne le pensais, et j'ai encore un bug en essayant d'utiliser le DFS pour trouver les cercles originaux. (Si quelqu'un peut m'aider à trouver ce bug, ce serait génial).

Le code était élégant au début, bien que j'aie continué à ajouter des bidouillages pour modifier la visualisation, etc.

code fonctionnel (à part un léger bug occasionnel dans 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)

Answer 5

L'une des options consiste à supprimer d'abord les cercles présentant le plus grand nombre de chevauchements ou de contacts. Après chaque suppression, vérifiez s'il s'agit d'une solution, sinon continuez à supprimer.

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