Algoritmo para determinar la existencia de soluciones con valores no negativos para la ecuación diofántica lineal

Question

Estoy buscando un método para determinar si existe solución a ecuaciones como:3n1+4n2+5n3=456, dónde n1, n2, n3 son números enteros positivos.

O más general:hay cero o positivo números enteros n1, n2, n3...que resuelve la ecuación k1n1+k2n2+k3n3...=m dónde k1,k2,k3...y metro son números enteros positivos conocidos.

No necesito encontrar una solución, sólo determinar si existe una solución.

Editar:

En cuanto al uso práctico de este algoritmo:

En una biblioteca de comunicaciones, quiero decidir si un mensaje determinado es válido según su tamaño, antes de manipularlo.Por ejemplo:Sé que un mensaje contiene cero o más elementos de 3 bytes, cero o más elementos de 4 bytes y cero o más elementos de 5 bytes.Recibí un mensaje de 456 bytes y quiero determinar su validez antes de inspeccionar más a fondo su contenido.Por supuesto, el encabezado del mensaje contiene la cantidad de elementos de cada tipo, pero quiero hacer una primera inspección en el nivel de la biblioteca de comunicaciones pasando algo como pair<MsgType,vector<3,4,5>>.

Answer 1

Estás preguntando si la expresión regular

(xxx | xxxx | xxxxx)*

coincide xx ... x, donde x ocurre 456 veces.

Aquí hay una solución en O (N+A^2), donde A es el más pequeño de los números en el lado izquierdo (en este caso 3).

Supongamos que sus números son 6,7,15. Llamaré a un número expresible en el formulario 6x+7y+15z "disponible". Debe verificar si hay un número determinado disponible.

Si puede obtener algún número N, seguramente podrá obtener n+6, n+12, n+18 - en general, n+6k para todos k> = 0. en el otro lado, si No puede obtener algún número N, entonces N-6 seguramente tampoco está disponible (si puede obtener (N-6), entonces (N-6)+6 = N estaría disponible), esto significa N-12, N-18, N-6K tampoco están disponibles.

Supongamos que ha determinado que 15 está disponible pero 9 no. En nuestro caso, 15 = 6*0+7*0+15*1 pero no podrá obtener 9 de ninguna manera. Entonces, por nuestro razonamiento anterior, 15+6k está disponible para todos K> = 0 y 9-6K para todos los k> = 0 no lo es. Si tiene algún número que dividido por 6 da 3 como resto (3, 9, 15, 21, ...), puede responder rápidamente: los números <= 9 no están disponibles, los números> = 15 son.

Es suficiente para determinar para todos los restos posibles de división en 6 (es decir, 0,1,2,3,4,5) cuál es el número más pequeño que está disponible. (Solo he demostrado que este número para el resto 3 es 15).

Cómo hacerlo: cree un gráfico con vértices 0,1,2,3,4,5. Para todos los números K que le dan (7,15 - ignoramos 6) Agregamos un borde de x a (x + k) mod 6. Déle peso (x + k) div 6. use Algoritmo de Dijkstra Usando 0 como nodo inicial. Las distancias encontradas por el algoritmo serán exactamente aquellos números que estamos buscando.

En nuestro caso (6,7,15), el número 7 da lugar a 0 -> 1 (peso 1), 1 -> 2 (peso 1), 2 -> 3 (peso 1), ..., 5 -> 0 (peso 1) y el número 15 da 0 -> 3 (peso 2), 1 -> 4 (peso 2), ..., 5 -> 1 (peso 2). La ruta más corta de 0 a 3 tiene un borde: su peso es 2. Entonces 6*2 + 3 = 15 es el número más pequeño que da 3 como resto. 6*1 + 3 = 9 no está disponible (bueno, lo verificamos previamente a mano).

¿Y cuál es la conexión con expresiones regulares? Bueno, cada expresión regular tiene un autómata finito equivalente, y construí uno de ellos.

Este problema, con múltiples consultas permitidas, apareció en el Olimpiada Polaca Y traducí la solución. Ahora, si escuchas ahora una persona que dice que la informática no es útil para los programadores reales, hazlo en la cara.

Answer 2

De acuerdo a este, si el mayor factor común de {n1, n2, n3, ...} no es un divisor de M, entonces no tienes solución. Esta página muestra un ejemplo de solo {n1, n2} pero se extiende a sistemas más grandes. El nuevo problema es escribir un algoritmo para encontrar el mayor factor común, pero eso es trivial a la luz del problema original.

Entonces, parte de su algoritmo encontraría el GCF ({n1, n2, ...}) luego vea si es un factor de m. Si no es así, entonces no existe ninguna solución. Esto no muestra completamente que existe una solución, pero puede mostrarle rápidamente que ninguno existe, lo cual aún es útil.

Answer 3

Parece que estás hablando de un sistema de desigualdades con restricciones enteras. La realidad es que estás resolviendo para este sistema:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

Y la restricción adicional de que N1, N2, N3 son enteros. Eso es un programación lineal problema. Desafortunadamente para usted, el caso general de resolver dicho sistema con Las restricciones enteras son NP-COMPLETO. Sin embargo, hay muchos algoritmos que lo resolverán para usted.

Answer 4

Esto está relacionado con el Problema de monedas de Frobenius, que no se ha resuelto para N> 3.

Answer 5

Un enfoque de fuerza bruta (pseudocódigo):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

Ver también http://mail.python.org/pipermail/python-list/2000-april/031714.html

EDITAR: En una biblioteca de comunicaciones, esto no tendría sentido, ya que necesita funcionar de inmediato. En la aplicación del OP probablemente usaría algún tipo de hash, pero su enfoque suena interesante.

Answer 6

Aquí hay algo en el caso de 2 números. Todavía no he descubierto cómo escalarlo:

Dado 2 enteros relativamente prime x e y, existen enteros positivos a y b de tal manera que ax+by=c para todos c>=(x-1)(y-1)

Básicamente, esto funciona porque, si asumes x<y, puede expresar todos los enteros mod x con (0, y, 2y, 3y, ..., (x-1) y). Ahora, al agregar un múltiplo positivo de X, puede llegar a todos los enteros entre [(X-1) (Y-1), (X-1) Y], como todos los enteros entre (X-1) (Y- 1) y (x-1) y-1 se habían expresado previamente.

1. GCD (X, Y). Si C no es un múltiplo, devuelve falso.
2. Si GCD (x, y)> 1, divide x, y, c por GCD
3. If c> (x-1) (y-1), devuelve verdadero
4. Más fuerza bruta

Y para la fuerza bruta:

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 7

Quizás la siguiente información sea irrelevante, porque no aborda la situación general, pero...

Si el problema es determinar si un entero positivo dado K puede formarse como una suma 3*n1 + 4*n2 + 5*n3, para enteros no negativos n1, n2, n3, entonces la respuesta es "sí", para K >= 3.

El conocido libro de texto de Rosen Matemáticas Discretas y sus Aplicaciones, pag.287 de la sexta edición, demuestra que "cada importe de franqueo de 12 céntimos o más puede formarse utilizando sólo sellos de 4 y 5 céntimos", por inducción.

El paso básico es que se puede formar un franqueo de 12 centavos con 3 sellos de cuatro centavos.

El paso de inducción considera que si P(k) es verdadero usando sellos de cuatro centavos, entonces simplemente sustituya un sello de cuatro centavos por uno de cinco centavos para demostrar que P(k+1) es verdadero.Si P(k) es verdadera sin usar sellos de cuatro centavos, entonces, como k>=12, necesitamos al menos 3 sellos de cinco centavos para formar nuestra suma, y ​​3 sellos de cinco centavos se pueden reemplazar con 4 sellos de cuatro centavos. sellos para lograr k+1.

Para ampliar la solución anterior a este problema es necesario considerar sólo unos pocos casos más.