Je cherche une méthode pour déterminer s'il existe une solution aux équations telles que:
3n1 + 4n2 + 5n3 = 456 , où n1, n2, n3 sont des entiers positifs.
ou plus général: existe-t-il zéro ou positif entiers n1, n2, n3 ... qui résout l'équation k1n1 + k2n2 + k3n3 ... = M où k1, k2, k3 ... et m sont des entiers positifs connus.
Je n'ai pas besoin de trouver une solution - juste pour déterminer si une solution existe.
concernant l'utilisation pratique de cet algorithme:
Dans une bibliothèque de communication, je souhaite décider si un message donné est valide en fonction de sa taille, avant de manipuler le message.
Par exemple: je sais qu'un message contient des éléments à 3 octets zéro ou davantage, des éléments de 4 octets à 4 octets à 4 octets et des éléments de 5 octets zéro ou d 'autres. J'ai reçu un message de 456 octets et je tiens à déterminer sa validité avant d'inspecter davantage son contenu.
Bien sûr, l'en-tête du message contient le nombre d'éléments de chaque type, mais je veux faire une première inspection dans le niveau de communication-bibliothèque en passant quelque chose comme paire
7 Réponses :
On dirait que vous parlez d'un système d'inégalités avec des contraintes entière. La réalité est que vous résolvez pour ce système:
k1n1+k2n2+k3n3...=m n1 >= 0 n2 >= 0 n3 >= 0
Non, c'est différent. Le problème complet de NP cherche s'il existe ou non une solution à certaines inégalités, et non une solution à une égalité.
@Jason: ne remarquant pas les trois inégalités du système de inégalités ci-dessus? Juste que pensez-vous > = 0 signifie?
Je suis désolé de ne pas être clair. Le problème de la programmation linéaire NP-complet tente de décider si une solution entière est une solution entière à un système linéaire d'inégalités. C'est là, existe-t-il des entiers x_1, x_2, ... x_n afin que l'axe> = b. Ici, une matrice entière m x n n est une matrice entier et B est un vecteur m-vecteur entier. Ceci est très différent de résoudre une équation linéaire.
@Jason: Comment est-ce différent? Vous n'avez besoin que d'introduire une variable libre dans la première équation et de la force à être supérieure à 0 pour activer la première équation en inégalité, vous pouvez alors écrire le problème comme AX> = B . Il existe plus d'inégalités que des égalités dans cette situation et les méthodes de programmation linéaire le résoudront définitivement et je ne suis pas convaincu que vous pouvez réduire cela à une solution P. Certes, personne n'a encore identifié une telle solution dans ce fil.
@Welbog: Comment ajustez-vous la matrice A et le vecteur B?
une approche de force brute (pseudocode): Voir aussi http://mail.python.org/pipermaril/python-list/2000-april/031714.html
Cette solution de force brute peut être fortement optimisée d'ici.
Trois inconnues sur le LHS et 456 au fur et à mesure que le RHS est un exemple spécifique, pas le problème général.
Je n'ai jamais dit que c'était efficace, je viens de dire que c'était une solution. Même à 3,5 millions de boucles (152 * 152 * 152), il ne faut toujours que prendre une seconde ou deux à exécuter.
@Jason, vous pouvez substituer vos propres valeurs pour les coefficients.
@ROBERT HARVEY: Il pourrait y avoir plus de trois inconnues aussi. C'est un problème horrible pour se déplacer ( goto S Quelqu'un) et échelle horrifiquement mal.
Ajouté quelques optimisations simples. Cela l'obtient jusqu'à 1,6 million de boucles (152 * 114 * 92)
Optimisations supplémentaires: NOUVEAU CODE ÉTAPES sur chaque facteur, plutôt que par chaque entiers. Le nouveau code a des boucles de 152/3 * 114/4 * 92/5, environ 27550. Toujours probablement plus lentement qu'un hash.
Selon Ce , si le plus grand facteur commun de {N1, N2, N3, ...} n'est pas un diviseur de M puis vous n'avez aucune solution. Cette page montre un exemple de juste {n1, n2} mais il s'étend aux systèmes plus importants. Le nouveau problème consiste à écrire un algorithme pour trouver le plus grand facteur commun, mais c'est trivial à la lumière du problème initial.
Une partie de votre algorithme trouverait la GCF ({N1, N2, ...}) puis voir si c'est un facteur de m. Si ce n'est pas le cas, aucune solution n'existe. Cela ne montre pas complètement qu'une solution existe, mais elle peut rapidement vous montrer qu'aucun existe, ce qui est toujours utile.
Je pense que pour certaines conditions, si vous trouvez une solution, vous pouvez trouver des solutions entières infinies.
Voici quelque chose sur le boîtier de 2 numéros. Je n'ai pas encore compris comment l'échelle de l'échelle:
donné 2 entiers relativement premiers x et y, il existe des entiers positifs A et B tels que Fondamentalement, cela fonctionne car, si vous supposez et pour la force brute: AX + by = C pour tous les c> = (x-1) (Y-1) x
Ceci est lié à la Problème de monnaie Frobenius , qui n'a pas été résolue pour n > 3.
Vous demandez si l'expression régulière
(xxx | xxxx | xxxxx) *
correspond à XX ... x, où x se produit 456 fois.
Voici une solution dans O (n + A ^ 2), où a est le plus petit des chiffres du côté gauche (dans ce cas 3).
Supposons que vos chiffres soient 6,7,15. Je vais appeler un numéro expresssible dans le formulaire 6x + 7y + 15Z "disponible". Vous devez vérifier si un numéro donné est disponible.
Si vous êtes capable d'obtenir un certain nombre N, vous pourrez sûrement obtenir N + 6, N + 12, N + 18 - en général, N + 6k pour tous K> = 0. de l'autre côté, si vous ne parvenez pas à obtenir un nombre Nombre N, N-6 n'est certainement pas disponible également (si vous pouviez obtenir (N-6), alors (N-6) + 6 = N serait disponible), cela signifie que n -12, N-18, N-6K ne sont pas disponibles non plus.
Supposons que vous ayez déterminé que 15 est disponible mais 9 n'est pas. Dans notre cas, 15 = 6 * 0 + 7 * 0 + 15 * 1 Mais ne pourrez pas obtenir 9 de quelque manière que ce soit. Donc, par notre raisonnement précédent, 15 + 6k est disponible pour tous K> = 0 et 9-6k pour tous K> = 0 n'est pas. Si vous avez un nombre divisé par 6, 3, comme le reste (3, 9, 15, 21, ...), vous pouvez répondre rapidement à: les chiffres <= 9 ne sont pas disponibles, des chiffres> = 15 sont.
Il suffit de déterminer pour tous les restes possibles de la division par 6 (soit 0,1,2,3,4,5) Quel est le plus petit nombre disponible. (J'ai juste montré que ce nombre pour le reste 3 est 15).
Comment le faire: Créez un graphique avec des sommets 0,1,2,3,4,5. Pour tous les chiffres K que vous avez donnés (7,15 - nous ne tenons pas 6) Ajoutez un bord de x à (x + k) MOD 6. Donnez-le du poids (x + k) DIV 6. Utilisez Algorithme de Dijkstra en utilisant 0 comme noeud initial. Les distances trouvées par l'algorithme seront exactement ces chiffres que nous recherchons.
Dans notre cas (6,7,15), le numéro 7 donne lieu à 0 -> 1 (poids 1), 1 -> 2 (poids 1), 2 -> 3 (poids 1), ..., 5 -> 0 (poids 1) et le nombre 15 donne 0 -> 3 (poids 2), 1 -> 4 (poids 2), ..., 5 -> 1 (poids 2). Le chemin le plus court de 0 à 3 a un bord - son poids est 2. SO 6 * 2 + 3 = 15 est le plus petit nombre qui donne 3 à la suite. 6 * 1 + 3 = 9 n'est pas disponible (Eh bien, nous avons vérifié qu'auparavant à la main).
Et quelle est la connexion à des expressions régulières? Eh bien, chaque expression régulière a un automate fini équivalent et j'ai construit l'un d'entre eux.
Ce problème, avec plusieurs requêtes autorisées, est apparue sur le Olympiade polonaise et j'ai traduit la solution. Maintenant, si vous entendez maintenant une personne qui disant que l'informatique n'est pas utile pour de vrais programmeurs, frappez-le en face.
Certainement non standard, mais je l'aime! Me rappelle mes journées en théorie du calcul parlant de Chomsky et du Good OL 'Pompting Lemma;) +100 pour le poinçon au visage;)
Très une solution très soignée. Vous pouvez également inclure un peu plus d'informations sur la manière dont le graphique peut être utilisé comme automate. Mon impression est que l'automate est NFA et par exemple pour traiter 6 + 7 + 15 = 28, 28% 6 = 4, l'état d'acceptation serait donc le nœud 4 et vous avez (28 - 4) / 6 = 4 jetons traiter, et chaque bord consomme autant de jetons que son poids. Est-ce correct? En outre, quelle est l'histoire du problème? Est-ce dans un manuel? Ou quelqu'un est venu avec la solution à l'Olympiade?
Votre description est correcte. Le chemin va 0 -> 1 -> 4, où le premier bord signifie l'ajout de 7 (poids 1) et le second plan de bord ajoutant 15 (poids 2); Cela consomme 3 jetons - le quatrième est pris en utilisant le numéro 6 une fois. Dans Stackoverflow.com/Questtions/2912885 donne un lien avec plus d'informations sur le problème. Je ne connais pas l'histoire comment le jury a choisi la tâche. Trois participants (sur 42) ont marqué un maximum de points (tâche "somme"): oi.edu.pl/php/show.php?ac=E180912 .
Peut-être que les informations suivantes sont hors de propos, car elles ne gèrent pas la situation générale, mais ...
Si le problème est de déterminer si un entiers positif donné K peut être formé comme une somme Le manuel bien connu de Rosen mathématiques discrètes et ses applications , p. 287 de la sixième édition, prouve que "chaque quantité d'affranchissement de 12 cents ou plus peut être formée en utilisant seulement des timbres de 4 cents et de 5 cents", utilisant l'induction.
L'étape de base est que les frais de port de 12 cents peuvent être formés avec 3 timbres de quatre cents.
L'étape d'induction estime que si p (k) est véridique en utilisant des timbres de quatre cents, puis remplacez simplement un tampon de quatre cents avec un tampon de cinq cents pour montrer que p (k + 1) est vrai.
Si p (k) est vrai en utilisant des timbres de quatre cents, alors, parce que k> = 12, nous avons besoin d'au moins 3 timbres de cinq cents pour former notre somme et 3 tampons de cinq cents peuvent être remplacés avec 4 quatre cents timbres pour atteindre K + 1.
Pour prolonger la solution ci-dessus à ce problème nécessite juste d'envisager quelques autres cas. 3 * N1 + 4 * N2 + 5 * N3 , pour les entiers non négatifs N1, N2, N3, puis La réponse est "oui", pour k> = 3.
Y a-t-il plus de contraintes au problème? Si m est 1 et k1, k2 .. km sont tous supérieurs à 1, alors vous ne pouvez pas trouver une solution ... donc je suppose m> = k1, k2 ... kn?
Nous avons vraiment besoin de Mathoverflow.
Lior, merci pour l'explication d'utilisation. Votre question vient de devenir beaucoup plus intéressante.
K1, K2, K3 sera-t-il 3,4,5 dans tous les cas? ou était-ce juste un exemple?