Logo Lainformacion.com
< El «ADSL de la Luna» va bastante bien
Diferentes pero iguales >

Cómo resolver un puzzle entre varias personas, de forma óptima

No recuerdo dónde vi mencionada esta cuestión, pero sí que no había una solución clara sobre cuál podía ser el método, si es que acaso existe uno. Ahí va:

Puzzling (CC) JHRitz

¿Cuál es la forma óptima de resolver un puzzle tradicional en equipo, con varias personas?

La pregunta se refiere al tradicional puzzle rompecabezas de piezas recortadas y no se especifica el tamaño del grupo de personas que pueden colaborar en resolverlo: pueden ser unas pocas o muchísimas.

El problema parece complicado y radica principalmente en que hay dos tipos de tareas: las primeras pueden hacerse entre varias personas en paralelo, como separar las piezas de los bordes de los interiores, agruparlas por colores, orientarlas tal vez. En cambio en otras tareas, como ver si una pieza encaja en cierta posición, no parece que esa aproximación sirva. O tal vez ni siquiera ese sea un acercamiento adecuado al problema. Lo que parece es que «el equipo» puede verse limitado y que muchos pares de ojos no siempre son mejores que uno: está la necesidad de transmitir lo que cada individuo va aprendiendo y por otro lado las limitaciones físicas del problema, como intentar encajar físicamente piezas en su sitio.

7 comentarios

#1 ping José R. Romacho

Un enfoque divide y vencerás creo que sería lo mejor: Algoritmo divide y vencerás.

La etapa de descomposición en colores y bordes se puede hacer en paralelo, para que cada uno resuelva su propio subpuzzle. Como la descomposición no será óptima, se irán intercambiando piezas a otras personas si no encajan en tu trozo.

No está de más que alguien se encargue de proveer refrescos o algo que picar en el proceso para colaborar en la solución del puzzle.

#2 ping Hectronic0

Se reparten las piezas a partes iguales entre todos, y cada cual intenta unir las que pueda. Al cabo de un rato, se intercambian los cachos de piezas unidas en sentido de las agujas del reloj,
(por ejemplo), asi cada uno recibe un grupo de piezas juntas y puede añadirle alguna de las suyas.

Para mejoralo, se podrían dividir las piezas, en lugar de en partes iguales, en grupos en función del color, si son bordes, etc..., así los grupos de piezas unidas al inicio sería previsiblemente mas grande.

Cuando ya no queden piezas sueltas, solo grupos de piezas ya unidas, de nuevo se reparten esos grupos, y se hace el procedimiento de nuevo, hasta que el numero de grupos de piezas unidas sea

#3 ping Hectronic0

M@#~da, debí de borrar parte del comentarío anterior :S.

...se hace el procedimiento de nuevo, hasta que el numero de grupos de piezas unidas sea

#4 ping Javier

Realmente, cuando uno trabaja sobre un puzzle y, una vez que ya se ha colocado el "marco", formado por las piezas con algún lado liso, lo que que se suele hacer es atacar los bordes de la(s) zona(s) que todavía no se han completado.

Es decir, en un momento dado de la reosolución del puzzle nos encontraremos por un lado con el "armazón" del puzzle, que está formado por las piezas ya colocadas, y con un montón de piezas pendientes sin colocar (Excepcionalmente, algunas de estas piezas pendientes pueden unirse entre sí, formando piezas pendientes "compuestas", pero eso no afecta al modo de resolución el puzzle).

En el armazón existirán unas piezas particulares que formarán la "frontera" del armazón, y que son aquellas piezas que tienen algunos "enganches" libres, es decir, que delimitan la zona del puzzle sin resolver.

El algoritmo básico de resolución de cualquier puzzle consiste en ir probando las piezas pendientes sobre la frontera del armazón, hasta que vayamos encajando piezas nuevas y, por tanto, modificando la propia frontera y disminuyendo el área sin resolver.

Lo buena que sea nuestra habilidad haciendo puzzles dependerá, principalmente, de nuestra heurística al ir probando las piezas pendientes sobre la frontera (si lo hacemos por color, forma, etc...) y de la facilidad para construir piezas pendientes compuestas.

Bien, si queremos distribuir el algoritmo en paralelo, la manera más fácil una vez construido el armazón, es asignar a cada recurso un segmento de la frontera que deberá rellenar con las piezas pendientes apropiadas.

Dado que la frontera es dinámica y a la larga decreciente, habrá que establecer una política de asignación de nuevas fronteras cuando dos segmentos de frontera colapsen en uno solo.

Por otra parte, y de manera auxiliar, se puede dedicar a más recursos a ordenar las piezas pendientes, en función de la heurística elegida, para facilitar la tarea de los recursos que están intentado rellenar sus segmentos de frontera (incluso, si se quieren ordenar los "montoncitos" de piezas pendientes con varios criterios simultáneos se puede usar una cuadrícula bidimensional).

#5 ping Munk

Eso está muy bien, pero el planteamiento pedía resolverlo con personas, no con recursos.
XD

#6 ping Juancho

Con un conocimiento del "negocio" se mejora enormemente el algoritmo: generalmente, el patrón de corte de las piezas se repite a lo largo del puzzle, como si fuera una imagen en mosaico. Por ejemplo, cada uno de los elementos del mosaico puede contar de 10x10 piezas. Una vez se consigan pedazos grandes, es muy sencillo montar otras partes del puzzle colocando encima las piezas de igual forma, disminuyendo enormemente las combinaciones de piezas.

#7 ping JuanMa

Como han dicho anteriormente lo mejor es realizar las tareas en paralelo. Primero el marco, segundo separar la piezas por colores y por formas (si tienen más de dos salidas y dos entradas). Después se empieza a buscar la pieza de la que se tenga una mayor información o en su defecto un menor número de posibilidades (colores poco frecuentes o piezas que tengan la distribución de entradas y salidas de forma poco habitual) de esta forma maximizamos las probabilidades de encajar una pieza. Cuando hemos acabado-barrido una zona de alta probabilidad, seguimos a la siguiente. El separar por forma+color acelera el proceso muchísimo