Juego de brocas de conmutación

Question

Me he encontrado un interesante problema: Se nos da $n$ bits en una fila, algunos de ellos son iguales a $1$, y algunos de ellos son iguales a $0$. Esta es nuestra combinación inicial. Y también nos dan el final de la combinación. La única operación que podemos realizar es la negación del bit seleccionado. Pero se niega también a sus vecinos (primera y la última bits sólo se tienen el uno al prójimo). Nuestra tarea es encontrar el mínimo número de operaciones que debemos realizar para obtener la terminación de la combinación de la combinación inicial. O dicen que no es posible. Con esto me refiero a escribir un algoritmo eficaz para resolver este problema.

Por ejemplo:

1) inicio: $1001$; final: $0010$. Número óptimo de operaciones es $2$, debido a $1001\rightarrow 0101\rightarrow 0010$ (en primer lugar niega primer bit, y luego la tercera).

2) Pero a partir de: $10$; a: $00$ es imposible de conseguir.

Creo que es un muy bien conocido problema pero no estoy seguro. Tal vez sea conocido en alguna otra forma. Yo estaría muy agradecido por las sugerencias.

Answer 1

Vamos a considerar la entrada como un vector de $\mathbb{F}_2$, por lo que el $1+1 = 0$. Va de $a$ $b$es lo mismo que ir de$a+b$$0$. Ahora, hay dos casos, usted puede comenzar a partir de $a+b+\mathtt{00000\ldots}$ o usted puede comenzar a partir de $a+b+\mathtt{11000\ldots}$ (el primer movimiento difiere del resto, porque el cambio sólo en dos lugares).

Ahora, la parte importante es que usted debe interpretar su movimiento no como "$i$- ésimo bit de cambiar también $i-1$$i+1$", pero como

Con $i$-ésimo bit de cambiar $(i+1)$-th y $(i+2)$-th bits.

Eso significa que usted puede trabajar con la inducción, porque la anterior bits que ya no va a cambiar. El paso es sencillo, si el $i$-ésimo lugar se establece, es necesario aplicar el bit flip (para que coincida $\mathtt{000\ldots}$). El siguiente de los bits de la secuencia puede cambiar para mejor o peor, pero la parte anterior no. Usted puede trabajar a través de todos los índices y se le dejó con $\mathtt{\ldots0000}$ o $\mathtt{\ldots0011}$ o $\mathtt{\ldots0001}$ o $\mathtt{\ldots0010}$. Los dos primeros - usted gana, el segundo de los dos - le suelto.

Observar, que desde el principio no tenía mucha elección, cada vez que dio la vuelta al poco, había que hacerlo, porque era el único movimiento que haría que el vector de coincidir en el lugar. Este es informal, pero con un poco de trabajo se puede hacer es una prueba de que el algoritmo es óptimo, es decir, es el menor de la solución, y si no encuentras una solución, entonces no hay ninguno.

Espero que esta ayuda ;-)