Dado que desee combinación de colores para un palo, ¿cómo puedo cepillo con el menor número de pasos?

Question

Si me quieres que el color de un palo (considerado como un segmento de línea en un espacio tridimensional) para una combinación de colores deseada usando un pincel, cómo puedo hacerlo con el menor número de pasos?

Observe que, el nuevo color se acaba de cubrir más de la edad, y tanto cambio de pinturas y crowhop durante el cepillado será considerada como causa de nuevos pasos.

Por ejemplo, a 2 pasos que son necesarios en el caso que se muestra a continuación: (Paso 1) cepillo de todo el palo con azul y, a continuación, (Paso 2) con un cepillo, el medio con el rojo.

y hay algunos otros ejemplos:

¿Cómo puedo averiguar el mínimo paso para cualquier determinada combinación de colores, y encontrar una estrategia para colorear?

Gracias de antemano por su ayuda.

Answer 1

Definir una porción a ser un contiguos de la sección del palo con el mismo color. Indicar todos los colores de los símbolos $a,b,c,...$ y deseada de la coloración por una cadena mediante los símbolos. Deje $S$ denotar el inicio en blanco palo y $A,B,C,...$ son símbolos utilizados para indicar el color de una parte de la barra, la correspondiente a los mismos colores que las minúsculas, símbolos. Ahora tenemos las siguientes reglas:

$S \to A|B|C|...$ (No hacer una diferencia para pintar todo el palo en el primer paso, porque al final cualquier parte sin pintar en el primer paso va a ser pintado.)

$A \to AB|AC|...|BA|CA|...|ABA|ACA|...$ (Podemos pintar la derecha/a la izquierda/a la parte media de cualquier parte, y nunca tenemos a la pintura a través de dos diferentes partes, de lo contrario podría haber simplemente agrandamiento de cualquiera de las partes afectadas, de modo que uno de sus extremos coincide con la nueva parte para ser pintadas.)

$A \\\ B \b \\ ...$ (Cuando hemos terminado, nos finalizar los colores de todas las partes.)

Esta es una gramática independiente del contexto y puede ser fácilmente convertido en una forma normal de Chomsky de tal forma que el tamaño de la resultante de la gramática es sólo un factor constante de veces que de esta gramática. A continuación, puede ejecutar el algoritmo CYK, que es esencialmente una relación de recurrencia que se basa en el hecho de que cada uno no termina de paso en una forma normal de Chomsky produce exactamente dos partes cada una de las cuales finalmente terminar en una cadena no vacía, y así para cualquier cadena de podemos de forma recursiva de la prueba de todas las maneras posibles que se pueden formar debido a que debe ser dividida en 2 de las cadenas no vacías, que puede ser escrito como de abajo hacia arriba DP algoritmo. Es fácil mantener el mínimo número de pasos necesarios para llegar a cada subcadena en el algoritmo CYK, y así se obtiene el número mínimo de pasos necesarios para toda la cadena, y como con todos los DP algoritmos podemos ejecutar un aparte de seguimiento para recuperar una óptima (pero no necesariamente la única) opción en cada paso.

Por supuesto, debe quedar claro que podríamos hacer la DP directamente en el problema original sin traducir en una gramática independiente del contexto, pero a veces puede ser conveniente para ser capaz de traducir una gran cantidad de este tipo de problemas en el mismo formulario.

Answer 2

Esta no es una respuesta, sino una formulación alternativa de ir en la dirección inversa:

Tenemos $N$ tarjetas en una fila, algunos podrían ser colocadas boca abajo. En cada turno, debemos elegir un conjunto de las cartas que muestran el mismo número - o que están boca abajo; todas las cartas seleccionadas son entonces volvió la cara hacia abajo. El objetivo es convertir boca abajo todas las cartas en el mínimo número de vueltas.

En los ejemplos de arriba:

1 2 1 2
1 2 1 X
1 X 1 X
X X X X

1 2 1 2
1 2 X 2
1 X X X
X X X X

1 2 1 3 2 3
1 2 1 3 X 3
1 2 1 X X X
1 X 1 X X X
X X X X X X 

De aspecto duro.