algorithm - tiempo - tipos de cubos rubik

Algoritmo para encontrar solución a rompecabezas.

Question

Estoy tratando de hacer un juego en el que un jugador tenga que encontrar su camino desde el principio hasta el final en el tablero de juego. ! [Tablero de juego] [1]

Como ves, este tablero de juego contiene un montón de obstáculos circulares rojos. Para ganar el juego, el jugador debe eliminar una cantidad mínima de obstáculos. Entonces, mi pregunta es, ¿cómo descubro programáticamente la cantidad mínima de obstáculos para eliminar, para liberar un camino? Un camino libre se consideraría el espacio entre, círculos que no se superponen y no se tocan.

Entonces, lo que realmente necesito es la cantidad mínima de círculos para eliminar, no necesito la ruta real. ¿Hay una forma fácil de hacer esto?

Y para complementar la comprensión de este tablero de juego, cada uno de los círculos tiene el mismo radio, y está restringido por las líneas negras.

Tampoco es necesario moverse en línea recta.

Answer 1

Al tratar de visualizar lo que escribió Leonid, hice el siguiente diagrama.

Answer 2

Muy bien, así que decidí hacer una visualización de esto en pygame.

Resultó ser mucho más difícil de lo que esperaba .

La idea como en otras sugerencias es usar Max Flow . El cuello de botella en el flujo de la fuente al sumidero es donde el flujo es más denso. Si cortamos el gráfico a la mitad en este cuello de botella denso (es decir, en el corte mínimo ), tenemos el número mínimo de círculos. Ocurre el maxflow = min-cut.

Aquí están los pasos que tomé:

1. Crear un mundo de pygame donde pueda generar círculos al azar

2. Hacer la función para resolver todas las colisiones entre círculos:

Esto implicó ordenar los círculos por la coordenada x. Ahora, para encontrar todas las colisiones del Círculo [0] Sigo moviéndome a lo largo de la matriz para detectar colisiones hasta que encuentre un círculo cuyo valor de x es más de 2 * radio mayor que el valor del círculo [0] ''sx, luego puedo hacer estallar el círculo [0 ] y repite el proceso ..

3. Cree nodos fuente y receptor , determine a qué círculos deben conectarse.

Los pasos 4 a 5 se llevan a cabo en la función " findflow () "

4. Cree un gráfico de networkX no dirigido básico que represente círculos con nodos. Conectando los nodos solo si sus círculos correspondientes chocan.

5. Y aquí es donde empieza a ponerse difícil ... creo un nuevo gráfico dirigido desde mi gráfico no dirigido . Debido a que tenía que trabajar el flujo a través de círculos (es decir, nodos) no bordes, tengo que dividir cada nodo en dos nodos con un borde entre ellos.

   Digamos que tengo un nodo X conectado al nodo Y (Y <-> X) (en el gráfico original).

   Cambio de X a Xa y Xb para que Xa se conecte a Xb (Xa-> Xb) También Y cambia a (Ya-> Yb).

   También necesito agregar (Yb-> Xa) y (Xb-> Ya) para representar la conexión original entre X e Y.

A todos los bordes del gráfico no dirigido se les asigna una capacidad = 1 (por ejemplo, solo puede cruzar un círculo una vez)

6. Ahora aplico networkx. algoritmo ford_fulkerson () en mi nuevo gráfico dirigido. Esto me encuentra el valor de flujo y el gráfico de flujo.

El valor de flujo es un número entero. Es el mínimo corte (o flujo máximo de la fuente al sumidero). Esta es la respuesta que hemos estado buscando . Representa el número mínimo de círculos que debemos eliminar.

Asignación de bonificación:

Pensé ... por qué parar aquí, tener el número de círculos que eliminar es bueno, pero quiero saber los círculos exactos que necesito eliminar. Para hacer esto, necesito averiguar dónde se produce realmente el corte mínimo en el flowGraph. Me las arreglé para averiguar cómo hacer esto, sin embargo, mi implementación tiene un error en alguna parte, por lo que a veces elimina el corte ligeramente incorrecto y así obtiene los círculos equivocados.

Para encontrar el corte mínimo, utilizaremos el flowGraph producido en el paso 6. La idea es que el cuello de botella de este gráfico sea el corte mínimo. Si intentamos fluir desde la fuente hasta el sumidero, nos quedaremos atascados en el cuello de la botella, ya que todos los bordes alrededor del cuello de botella estarán a su máxima capacidad. Así que simplemente usamos DFS ( búsqueda en profundidad ) para fluir hacia abajo tanto como podamos. Solo se permite que el DFS se mueva a lo largo de los bordes que no están a la capacidad máxima en el gráfico de flujo. (Por ejemplo, su flujo es 0 no 1). Utilizando DFS desde la fuente, tomé nota de todos los nodos que pude ver almacenándolos en self.seen. Ahora, después de DFS, para todos los nodos vistos, verifico si el nodo tiene un límite de capacidad máxima para un nodo que no se vio en DFS. Todos esos nodos están en min-cut.

Aquí hay una imagen de una de las simulaciones que ejecuté:

y con los círculos eliminados, la llené con pintura (es posible que tenga que acercarse un poco para ver que hay un espacio entre los círculos):

Aprendizaje:

La velocidad está bien, incluso en python, corre para 1000 círculos ok.

Fue más difícil de lo que pensaba, y todavía tengo un error al intentar usar el DFS para encontrar los círculos originales. (Si alguien puede ayudar a encontrar el error que sería genial).

El código era elegante al principio, aunque seguí agregando hacks para cambiar la visualización, etc.

código de trabajo (aparte de una pequeña falla ocasional en 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 3

Para una traducción de gráficos, algo como esto podría funcionar.

Haz una pared (las líneas azules) entre dos círculos si se superponen. No se olvide de agregar en el borde superior e inferior también. Esto crea un par de regiones. Estos serán todos los nodos del gráfico.

Luego tenemos que encontrar los bordes, el costo de ir de un nodo a otro. Tome dos regiones vecinas (compartiendo una pared). Luego, mediante la fuerza bruta, o el método inteligente que se le ocurra, determine el costo de trasladarse de esta región a la otra. Si quitas un círculo, eso significa que quitas todas las paredes que van a ese círculo. Si esto convierte a las dos regiones en una región, el costo del borde es 1. Si necesita eliminar dos círculos (todos los muros que tienen) para combinar las dos regiones, el costo es 2. Etc.

Algunos de los bordes (verde) están dibujados. Tenemos que ir desde la región de inicio hasta la región final. Ahora tienes un gráfico ponderado todos los días.

Creo que esto se puede mejorar mucho, pero lo dejo como un ejercicio =)

En este caso el mínimo es 3.

Advertencia, la imagen está dibujada a mano, olvidé algunas paredes, bordes y regiones. Sólo con fines ilustrativos.

Answer 4

Una opción es primero eliminar aquellos círculos con la mayor cantidad de coincidencias o toques. Después de cada uno que elimine, verifique si es una solución, si no continúa, elimine.

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

Answer 5

Es un problema de maximum flow teoría de grafos.

Supongamos que cada círculo es un nodo en el gráfico. Adicionalmente introducimos 2 nodos especiales: TOP y BOTTOM . Conecta círculos con estos nodos si se intersecan con el lado TOP / BOTTOM. Conecte los nodos correspondientes a los círculos entre sí si los círculos se cruzan.

Ahora necesita encontrar un corte mínimo en este gráfico, teniendo TOP como fuente y BOTTOM como sumidero o viceversa. Puedes usar Max-flow_min-cut_theorem para resolverlo. Lo que dice es que el Minimum-cut problem es equivalente al problema de flujo máximo. Puede encontrar detalles sobre cómo resolver el problema de Max-Flow problem en TopCoder .

Como podemos pasar por cada nodo solo una vez, debemos convertir los nodos en un borde dirigido de capacidad uno con nodo interno y externo para cada círculo. El algoritmo de flujo máximo resolverá el problema en el gráfico resultante y tendrá en cuenta el hecho de que estamos eliminando círculos en lugar de conexiones entre círculos. Siempre es una mejor decisión para este problema eliminar un nodo en un gráfico en lugar de borde, ya que siempre podemos eliminar cualquier borde eliminando un nodo. La eliminación de un nodo adicionalmente puede resultar en la eliminación de más de un borde.

Por cierto, un problema similar se puede encontrar en Uva Online Judge . Es una buena idea intentar resolver esta tarea en el juez, entonces estará seguro de que su solución es correcta.