standard number books algorithm math numbers theory equation

algorithm - number - La ruta más corta entre dos enteros sumando o restando



standard algorithm multiplication (6)

Aquí está la descripción de este problema:

Te dan dos enteros ay b. Desea encontrar la secuencia más corta de operaciones necesarias para transformar a en b, donde en cada paso se le permite sumar o restar 5, 7 o 12.

Por ejemplo, si le dan a = -5 y b = 19, la ruta más corta es

-5 + 12 + 12 = 19

Si te dieran 1 y 3, el camino más corto sería

1 + 7 - 5 = 2

La única forma en que puedo pensar en resolver esto es mediante BFS y tal vez un poco más de poda. ¿Hay un algoritmo mejor que podría utilizar en su lugar?

¡Gracias!

El problema es equivalente a obtener el número ab . O abs(ab) , ya que es simétrico alrededor de cero. Creo que esto se puede hacer fácilmente con una adopción de programación dinámica . Por ejemplo, la forma más rápida de obtener 23 es la forma más rápida de obtener 23+5,23-5,23+7,23-7,23+12 o 23-12 más una operación. Si lo aplica un par de veces en la condición de inicio (el costo de + 5, -5, .. es 1, los demás son infinitos), tendrá su respuesta en O(ab) .

Pre calcule las operaciones necesarias para el primer rango mínimo, después de eso solo siga sumando múltiplos de +12.

Pre-calcule todas sus combinaciones de operaciones en un mapa hash y luego haga una búsqueda de la respuesta.

El paso de precálculo tomará tiempo, pero una vez hecho, encontrará las respuestas dentro del rango precalculado que son 1 operación de búsqueda.

Aquí hay una pequeña demostración de JavaScript:

// maximum depth of combos to try var MAX = 6; // possible operations var ops = ["+-5", "+5", "+-7", "+7", "+-12", "+12"]; // initial hash map of operations->value var all = {"+5":5, "+-5":-5, "+7":7, "+-7":-7, "+12":12, "+-12":-12}; var allcnt = 6; // count combos *not needed* // initial hash map of values->operations, plus "0" so we can avoid it var unique = {"0": "0", "5":"+5", "-5":"+-5", "7":"+7", "-7":"+-7", "12":"+12", "-12":"+-12" }; var ready = false; // get all useful combinations of ops function precalc() { var items = []; for(var p in all) { items.push(p); } for(var p=0; p<items.length; p++) { for(var i=0; i<ops.length; i++) { var k = items[p] + ops[i]; var v = eval(k); if(unique[v] == null) { unique[v] = k; all[k] = v; allcnt++; } } } } // find an answer within the pre-calc''d depth function find(a, b) { if(ready === false) { for(var i=0; i<MAX; i++) precalc(); ready = true; } return unique[""+Math.abs(a-b)]; } // test find(-5,19);

Vamos a empezar con un conjunto de observaciones interesantes. Como muchos otros han señalado, el objetivo es encontrar una combinación lineal de 5x + 7y + 12z = b - a con coeficientes enteros tales que | x | + | y ​​| + | z | se minimiza Pero hay algunas conexiones muy interesantes entre estos tres números que podemos explotar:

  1. Si alguna vez tenemos una combinación de 5x + 7y + 12z donde xey son positivos o negativos, podemos cancelar algunos números de x e y para agregar un número equivalente de 12s. En otras palabras, ninguna solución óptima tiene el mismo signo tanto en x como en y, porque siempre podríamos mejorar esta solución.
  2. Si alguna vez tenemos una combinación de 5x + 7y + 12z donde y, z tienen signos opuestos, siempre podemos eliminar un 7 y un 12 y agregar un 5 del signo apropiado para obtener una mejor solución. De manera similar, si x y z tienen signos opuestos, siempre podemos eliminar un 5 y un 12 y agregar un 7 del signo apropiado. Esto significa que nunca debemos considerar una solución donde z tenga el mismo signo que x o y, porque significa que tendría que haber una solución mejor.

Pensemos en lo que (1) y (2) nos dicen colectivamente. (1) dice que los signos en xey no pueden ser iguales, ya que siempre podemos hacerlo mejor. (2) dice que si x y z tienen signos opuestos o si y y z tienen signos opuestos, siempre podemos hacerlo mejor. Colectivamente esto significa que

Lema : al menos uno de x, y o z debe ser cero en la solución óptima.

Para ver esto, si los tres son distintos de cero, si x e y tienen el mismo signo, entonces podemos mejorar claramente la solución reemplazándolos con 12s. De lo contrario, xey tienen signos opuestos. Por lo tanto, si x y z tienen signos diferentes, por (2) podemos reemplazarlos con menos 7, de lo contrario, yz tendrían signos diferentes y por (2) podremos reemplazarlos por menos 5.

Bien, esto se ve realmente genial! Esto significa que solo necesitamos resolver estas tres ecuaciones de enteros y encontrar cuál tiene la menor suma de coeficientes:

  • 5x + 7y = b - a
  • 5x + 12z = b - a
  • 7y + 12z = b - a

Afortunadamente, por la identidad de Bezout , porque gcd (5, 7) = gcd (5, 12) = gcd (7, 12) = 1, todos estos sistemas de ecuaciones tienen una solución para cualquier valor de b - a.

Ahora, veamos cómo resolver cada una de estas ecuaciones. Afortunadamente, podemos usar algunos trucos lindos para reducir enormemente nuestro espacio de búsqueda. Por ejemplo, para 5x + 7y = b - a, el valor de x no puede estar fuera de [-6, +6], ya que de ser así, podríamos reemplazar siete de los 5 con cinco 7. Esto significa que podemos resolver la ecuación anterior haciendo lo siguiente:

Para x = -6 a +6, vea si 5x + 7y = b - a tiene una solución entera al computar (b - a) - 5x y ver si es divisible entre siete. Si es así, el número de pasos necesarios para resolver el problema viene dado por | x | + | ((b - a) - 5x) / 7 |.

Podemos usar trucos similares para resolver las dos últimas ecuaciones: para la segunda ecuación, x varía de -11 a +11, y para la tercera y también varía de -11 a +11. Entonces podemos tomar la mejor respuesta de las tres ecuaciones para ver cuál es la respuesta.

Aquí hay algunos pseudocódigos para registrar la menor cantidad de pasos posibles. Esto puede modificarse fácilmente para devolver lo que esos pasos son simplemente registrando cuál de las soluciones se usó y luego expandiéndola a una ruta completa:

Let best = infinity # Solve 5x + 7y = b - a for x = -6 to +6: if ((b - a) - 5 * x) mod 7 = 0: best = min(best, |x| + |((b - a) - 5 * x) / 7|) # Solve 5x + 12y = b - a for x = -11 to +11: if ((b - a) - 5 * x) mod 12 = 0: best = min(best, |x| + |((b - a) - 5 * x) / 12|) # Solve 7x + 12y = b - a for x = -11 to +11: if ((b - a) - 7 * x) mod 12 = 0: best = min(best, |x| + |((b - a) - 7 * x) / 12|) return best;

Este algoritmo es sorprendentemente rápido: se ejecuta en tiempo O (1) porque el número de iteraciones necesarias para resolver cada uno de los tres sistemas lineales es una constante (como máximo 23). Solo requiere memoria O (1) para mantener los valores posibles, y creo que en la práctica es probablemente el algoritmo más rápido que podrá escribir.

¡Espero que esto ayude!