Algoritmo de coincidencia de Dominios

Question

Dadas algunas entradas, que consisten en un símbolo izquierdo y derecho, cadenas de salida que vinculan las entradas.

Imagine que las entradas son dominós que no pueden voltearse horizontalmente y deben encadenarse entre sí. Se prefiere crear cadenas circulares grandes (ignorar si no se puede hacer físicamente con dominós reales) sobre cadenas circulares pequeñas que se prefieren sobre cadenas donde el inicio y el final no coinciden.

Las salidas con más cadenas circulares (independientemente de la longitud o la longitud de la cadena) son lo que estamos buscando. Por ejemplo, una salida de 3 cadenas circulares es mejor que 1 cadena grande y un dominó individual sobrante.

¿Puede alguien señalarme en la dirección correcta? ¿A qué grupo de problemas pertenece esto y existen algoritmos existentes para resolver esto?

Ejemplos (salidas pueden ser incorrectos!):

in[0]=(A,B) 
in[1]=(B,C) 
in[2]=(C,A) 
out[0]=(0,1,2) 

in[0]=(A,B) 
in[1]=(B,A) 
in[2]=(C,D) 
in[3]=(D,C) 
out[0]=(0,1) 
out[1]=(2,3) 

in[0]=(A,B) 
in[1]=(B,A) 
in[2]=(C,D) 
in[3]=(E,F) 
out[0]=(0,1) 
out[1]=(2) 
out[2]=(3) 

in[0]=(A,B) 
in[1]=(B,A) 
in[2]=(C,D) 
in[3]=(D,E) 
out[0]=(0,1) 
out[1]=(2,3) 

in[0]=(A,B) 
in[1]=(B,C) 
in[2]=(C,D) 
out[0]=(0,1,2) 

Answer 1

El problema ya que ahora no es tan claramente definido como podría ser - ¿cómo es exactamente son calificados de soluciones? ¿Cuál es el criterio más importante? ¿Es la longitud de la cadena más larga? ¿Hay una penalización por crear cadenas de longitud uno?

A menudo es útil en tales problemas visualizar la estructura como un gráfico, por ejemplo, asignar un vértice (V [i]) a cada mosaico. Entonces para cada i, j crea un borde entre los vértices V [i], V [j] si puedes colocar V [i] a la izquierda de V [j] en una cadena (entonces si V [i] corresponde a (X) , A) entonces V [j] corresponde a (A, Y) para algunos X, Y, A).

En dicho gráfico, las cadenas son trayectorias, los ciclos son cadenas cerradas ("circulares") y el problema se ha reducido a la búsqueda de algún ciclo y/o trazado de camino para un gráfico. Este tipo de problemas a menudo pueden reducirse a problemas de coincidencia o * flujo (flujo máximo, flujo máximo-máximo-máximo, flujo mínimo-máximo-máximo o lo que sea).

Pero antes de que pueda reducir aún más, debe establecer las reglas precisas según las cuales se determina que una solución es "mejor" que otra.

Answer 2

Es fácil comprobar si existe una cadena circular que consta de todos los dominós. Lo primero que necesita hacer el siguiente gráfico dirigido G:

• nodos de G son símbolos en las fichas de dominó (A, B, C ..) en su ejemplo,
• Para cada dominó (A, B) se poner un borde dirigido de a a B.

existe una cadena circular que consiste en todas las fichas de dominó si y sólo si existe un Eulerian cycle en G. para comprobar si existe ciclo euleriano en G es suficiente para comprobar el tiempo cada nodo tiene incluso grado

Answer 3

No estoy seguro de si este es realmente el caso, pero a juzgar por sus ejemplos, su problema es similar al problema de descomponer una permutación en un producto de ciclos disjuntos. Cada mosaico (X, Y) puede verse como P (X) = Y para una permutación P. Si esto está de acuerdo con sus suposiciones, la buena (o mala) noticia es que dicha descomposición es única (hasta la orden del ciclo) y es muy fácil de encontrar Básicamente, empiezas con cualquier ficha, encuentras una ficha correspondiente y, por otro lado, sigues esto hasta que no se pueda encontrar ninguna coincidencia. Luego pasas al siguiente punto sin tocar. Si eso no es lo que está buscando, la solución más general basada en gráficos por t.dubrownik parece ser el camino a seguir.

Answer 4

Dominios que no se pueden voltear horizontalmente == gráficos dirigidos.

Poner los dominós uno después del otro se llama un "camino", si se trata de un camino cerrado, es un circuito.

Un circuito que incluye todos los vértices de un gráfico es un circuito de Hamilton.

Su problema en términos de teoría de grafos es: cómo dividir (descomponer) su gráfica en un número mínimo de subgrafos que tienen circuitos hamiltonianos. (a.k., gráficos de Hamilton)