Algorithme pour minimiser la surface, en fonction du volume

22

Considérez la tâche algorithmique suivante:

Entrée: un entier positif , avec sa factorisation première Trouver: des entiers positifs qui minimisent , sous réserve de la restriction quex , y , z x y + y z + x z x y z = nn
x,y,zxy+yz+xzxyz=n

Quelle est la complexité de ce problème? Existe-t-il un algorithme à temps polynomial? Est-ce NP-difficile?


Ce problème pose essentiellement: parmi tous les solides rectangulaires dont le volume est et dont les dimensions sont tous des entiers, lequel a la plus petite surface?n

Ce problème a été posé par Dan Meyer, sous le titre Le problème mathématique que 1000 professeurs de mathématiques n'ont pas pu résoudre . Jusqu'à présent, aucun des professeurs de mathématiques avec lesquels il a travaillé n'a trouvé d'algorithme raisonnable pour ce problème. Dans son contexte, la définition de «raisonnable» est un peu imprécise, mais en tant qu'informaticiens, nous pouvons poser une question plus précise sur la complexité de ce problème.

L'approche évidente consiste à énumérer toutes les possibilités pour , mais cela prend un temps exponentiel. Les commentateurs du blog de Dan Meyer ont proposé de nombreux algorithmes candidats efficaces qui se sont malheureusement tous révélés incorrects. Martin Strauss suggère que ce problème semble vaguement faire penser à 3 partitions , mais je ne vois pas de réduction.x,y,z


Permettez-moi également de clarifier certaines idées fausses que j'ai vues dans les commentaires / réponses:

  • Vous ne pouvez pas réduire à partir de 3 partitions en remplaçant simplement chaque nombre par sa puissance , car les fonctions objectives des deux problèmes sont différentes. La réduction évidente ne fonctionne tout simplement pas.2 qq2q

  • Il n'est pas vrai que la solution optimale implique de choisir l'un des pour être le diviseur le plus proche de à . Je vois plusieurs personnes qui supposent que c'est le cas, mais en fait, ce n'est pas correct. Cela a déjà été réfuté sur le blog de Dan Meyer. Par exemple, considérons ; et 4 divise 68, donc vous pourriez penser qu’au moins un des devrait être 4; cependant, ce n'est pas correct. La solution optimale est , , . Un autre contre-exemple est , , mais la solution optimale estn 3 x,y,zn n=683n3n=68x,y,zx=2y=2z=17n=22236834x,y,zx=2y=2z=17n=222x=3722236X=37 , , . (Il pourrait être vrai que pour tout , la solution optimale implique de faire au moins un de égal au plus petit diviseur de supérieur à ou au plus grand diviseur de plus petit que - Je n'ai pas de contre-exemple pour le moment - mais si vous pensez que cette affirmation est vraie, elle aurait besoin d'une preuve. Vous ne pouvez absolument pas supposer qu'elle est vraie.)y=3z=2nx,y,znn3 nn3

  • "Faire en sorte que soient de la même taille" ne semble pas nécessairement donner la réponse optimale dans tous les cas; voir le blog de Dan Meyer pour les contre-exemples. Ou, au moins, pour certaines interprétations raisonnables de l'expression "faites-les à peu près la même taille", il existe des contre-exemples montrant que cette stratégie n'est pas en fait optimale. Si vous souhaitez essayer une stratégie de ce type, assurez-vous de formuler la réclamation avec précision, puis fournissez une preuve mathématique précise.x,y,z

  • Un temps d'exécution de n'est pas polynomial. Pour que ce problème soit en P, le temps d'exécution doit être un polynôme dans la longueur de l'entrée . La longueur de l'entrée est quelque chose comme , pas . L'algorithme de force brute évident peut être fait pour fonctionner en temps ou , mais c'est exponentiel en et compte donc comme un algorithme temps exponentiel. Ce n'est donc pas utile.O(n3)lgnnO(n3)O(n2)lgn

DW
la source
1
Intéressant. Mon approche naïve serait de «faire peu près la même taille», généralisant l'idée que le cube est le solide rectangulaire avec la plus petite surface pour un volume donné. Cela fonctionnerait-il? Et si c'est le cas: je ne vois pas comment le faire efficacement, mais y a-t-il une réduction plus facile à atteindre, peut-être? x,y,z
G. Bach
2
Une réduction va être un cauchemar car vous avez besoin d'un moyen de générer des nombres premiers appropriés. Le mieux que vous puissiez espérer est une réduction aléatoire, en utilisant quelque chose comme le théorème de Dirichlet pour générer des nombres premiers appropriés, mais même cela semble peu probable.
Tom van der Zanden
1
@ G.Bach, je pense que cet article de blog considère un tas d'heuristiques de cette veine (par exemple, commencez par chacun de pour être l'entier le plus proche de , puis ajustez-les un tout petit bit) et affiche des contre-exemples explicites pour chacun. Mais vous avez peut-être un algorithme qu'ils n'ont pas envisagé? x,y,zn3
DW
3
oeis.org/A075777 semble revendiquer un algorithme, mais il semble être incorect (n = 1332 génère 9,4,37 au lieu de 6,6,37 par exemple)
Scott Farrar
1
Voici une observation qui peut être utile. Étant donné , les optimaux satisfont en fait le "rêve naïf": ils doivent être la paire de facteurs de plus proche de y , z n / xxy,zn/x . (C'est facile à prouver.) À une solution optimalex,y,z, cette condition doit être vérifiée pour les trois variables simultanément:x,ysont la paire correspondant àz, etc. Une implication: étant donnéz, il n'y a qu'une seule paire possiblex,yavec laquelle elle peut être optimale. Malheureusement, (1) cette condition n'identifie pasuniquementle triple optimal; (2) Je ne vois pas comment trouver rapidement la paire correspondante. n/xx,y,zx,yzzx,y
usul

Réponses:

1

Voici une version modifiée d'un algorithme "choisir un diviseur près de la racine du cube". Il doit encore forcer brutalement de nombreux cas, donc je ne sais pas à quel point il s'agit d'une réelle amélioration par rapport à l'énumération de tous les cas. Cependant, je l'ai soumis comme correction à l'algorithme sur OEIS (celui qui a généré des résultats incorrects) parce que je pense qu'il devrait être précis au moins.

Voici l'algorithme pour trouver (s1, s2, s3) et la surface d'un prisme rectangulaire étant donné son volume n:

  1. Étant donné n, trouvez la racine du cube.
  2. Définissez un entier de valeur initiale s1 au plafond de cette racine de cube.
  3. Testez pour voir si s1 est un diviseur de n, et sinon, réduisez s1 de 1.
  4. Si un diviseur s1 est trouvé, définissez un s2 initial comme étant le plafond de la racine carrée de (n / s1).
  5. Testez ensuite pour voir si s2 est un diviseur de n / s1, et sinon, réduisez s2 de 1.
  6. Lorsqu'un diviseur s2 est trouvé, s3 est alors réglé sur n / (s1 * s2).
  7. La surface actuelle est calculée par 2 * (s1 * s2 + s1 * s3 + s2 * s3).
  8. La SA actuelle est comparée au minimum actuel. S'il s'agit de la première surface calculée, il est stocké en tant que minSA. Après le premier, nous testons pour voir si la SA actuelle est plus petite que minSA, et si oui, stockons-la dans minSA.

Cet algorithme énumère certains des triplets (s1, s2, s3) mais n'a besoin que de tester les diviseurs sous la racine du cube. (Étant donné que les trois diviseurs ne peuvent pas tous être au-dessus de la racine du cube). De la même manière, s2 n'a qu'à tester les diviseurs de n / s1 sous la racine carrée de n / s1, car les deux diviseurs ne peuvent pas être au-dessus de la racine carrée)

Remarque sur l'étape 3: si la racine du cube est un diviseur, alors n est un cube et nous pouvons nous arrêter là avec une surface minimale 6 * s1 ^ 2 de la boîte (s1, s1, s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA
Scott Farrar
la source
Votre algorithme prend un temps exponentiel. Chaque boucle examine environ candidats possibles, donc le temps d'exécution estO( 3 n3, qui est exponentielle,non polynomiale. Ainsi, cet algorithme ne répond pas à la question. (J'ai déjà mentionné un algorithme à temps exponentiel dans la question.)O(n32)=O(n2/3)
DW
Hmm, y n'est pas confiné sous la racine cubique de n, par exemple, n = 1332, nous testerons finalement s1 = 2, ce qui signifie que s2 sera sous la racine carrée de 1332/2 ~ = 26. En effet (2,18, 37) est testé avec y et z au-dessus de la racine du cube.
Scott Farrar
@ScottFarrar, oui, je sais. Je n'ai pas inclus tous les détails sanglants de l'analyse de complexité; il n'y avait pas d'espace dans un seul commentaire. Si vous incluez les détails sanglants, je pense que vous constaterez que vous obtenez le temps d'exécution que j'ai cité. Vous pouvez me faire confiance :-), ou lire notre question de référence pour en savoir plus sur ces détails sanglants. Dans tous les cas, même si vous avez supprimé la boucle interne, la boucle extérieure ne fonctionne toujours itérations, de sorte que le temps d' exécution de votre algorithme est au moins Ω ( n 1 / 3 ) - à savoir, il est certainement exponentiel. Θ(n1/3)Ω(n1/3)
DW
0

Le problème serait bien sûr lié à la complexité de l'affacturage si les décompositions principales n'étaient pas données. Étant donné les facteurs et en prenant des journaux de tous les facteurs premiers, ce problème semble être à peu près le même que celui de minimiser l'écart par rapport à la moyenne des sommes de partition (l'exercice, peut-être analytique ou expérimental, trouve à quel point cette approximation intuitive de la problème tient).k

Voici le cas à 3 voies (les sommes de partition sont ). le cas à 2 voies a été largement étudié et est NP difficile (à partir de la 1ère réf). (Ce cas 2 voies est pas tout à fait le même que le NP-complet 2 voies connu problème de la partition où des sommes de partition sont égales. Remarque sommes égales de partition implique 0 écart des sommes de séparation et vice - versa. ) Les 2 e études ref 3- partitionnement à sens et à n voies , en partie empiriquement, où il n'y a pas autant d'études que le cas à 2 voies.log(x),log(y),log(z)n

vzn
la source
Cette réponse n'est pas utile et ne répond pas à la question. 1. Je recherche des preuves ou des preuves, pas des spéculations. Il n'y a aucune preuve que la minimisation de l'écart donne une solution optimale. Même si c'était vrai, cela ne répondrait pas à la question: cela ne nous dirait pas la complexité de minimiser l'écart. 2. La première référence concerne environ 2 partitions. Me pointer vers une référence sur 2 partitions n'est pas utile. J'ai déjà expliqué dans la question pourquoi mon problème n'est pas seulement à 3 partitions (ou 2 partitions). Un article sur une variante d'un problème que je n'ai pas demandé n'est pas utile.
DW
Contre-exemple de l'affirmation selon laquelle vous devriez minimiser l'écart absolu par rapport à la moyenne: . Ensuite, 1 , 4 , 17 donne un écart absolu de 2,85342 , qui est l'écart absolu le plus faible possible. Cependant 2 , 2 , 17 est la solution correcte (optimale) et a une plus petite surface. [Par déviation absolue de la moyenne, je veux dire spécifiquement | log ( x ) - μ | + | log ( y ) - μ | + |n=681,4,172.853422,2,17(où μ = ( log ( x ) + log ( y ) + log ( z ) ) / 3 ).]|log(x)μ|+|log(y)μ|+|log(z)μ|μ=(log(x)+log(y)+log(z))/3
DW
D'accord! il n'y a jamais eu aucune affirmation que cet algorithme était correct, il était basé sur l'inspection de certains exemples et d'autres suggestions dans les commentaires. il ne s'agit que d'un seul contre-exemple (vous avez indiqué que la méthode de minimisation des écarts est défectueuse dans le post révisé ). la question de savoir «à quelle fréquence» cet algorithme donne une solution correcte est intéressante car elle pourrait donner des indices sur une métrique d'optimisation correcte. conjecture que cet algorithme donne «souvent» la bonne réponse. la référence bidirectionnelle consiste à afficher une version de déviation du problème qui est différente de la version exacte typique sur wikipedia, etc.
vzn
voir aussi Lakatos Preuves et réfutations
vzn
0

modifier

Voici un argument informel pour expliquer pourquoi il est peu probable qu'un algorithme rapide existe. Cette phrase n'a pas changé, mais j'ai supprimé ce qui était ici parce qu'elle était trop structurée comme la preuve formelle dans la section suivante et la discussion se détournait de ses bugs, dont certains que j'ai remarqués moi-même et un dont DW m'a gentiment fait remarquer. Permettez-moi plutôt d'essayer d'exprimer l'intuition qui se cache derrière.

N

Que se passe-t-il lorsque nous traduisons les mêmes étapes dans une algèbre différente, comme l'addition et la soustraction au lieu de la multiplication et de la division? Nous savons (voir le lemme ci-dessous) que notre algorithme trouvera une 3-partition dont les produits sont égaux, s'il en existe une, ou bien déterminera qu'il n'y a pas une telle 3-partition. Donc, si nous pouvions traduire les mêmes techniques dans le groupe additif, nous pourrions trouver une partition à 3 dont les sommes sont égales, ou déterminer qu'aucune telle partition n'existe. En d'autres termes, nous pourrions résoudre 3 partitions en temps polynomial. Ce n'est pas très plausible.

Alors, pourquoi un tel algorithme pourrait-il fonctionner pour la multiplication et échouer pour l'addition? Une raison possible est que chaque entier a une factorisation première unique sous multiplication, mais est cyclique sous addition. Une autre est que la multiplication forme un anneau avec addition, vous avez donc un autre ensemble d'opérations que vous pouvez utiliser. Un autre est que vous devrez généraliser l'algorithme pour qu'il fonctionne pour les non-premiers, et cela pourrait dépendre de leur primalité. Celui que DW a souligné est que la méthode de traduction spécifique peut augmenter de façon exponentielle la taille de vos entrées. Et peut-être P = NP après tout.

Mais si ce sont les failles qui permettent à un algorithme rapide de fonctionner, je pense qu'il est toujours utile de le savoir, car il suggère où nous devrions concentrer nos efforts. Nous devrions chercher quelque chose qui se briserait si nous essayions de l'appliquer à un problème NP-complet. Une approche qui généraliserait à d'autres algèbres consiste probablement à aboyer le mauvais arbre. Je soupçonne, cependant, que la multiplication n'est pas vraiment assez différente pour que cela fonctionne, mais ce n'est qu'un pressentiment.

Lemme

m=N3(am,bm,mab)ab(ab+1a+1b)m2a=b=1

xyz=N

(am)(bm)+(am)(mab)+(bm)(mab)=abm2+m2b+m2a=(ab+1a+1b)m2

f(a,b)=ab+1a+1bδfδa=b1a2δfδb=a1b2a=b2,b=a2aba=b=1

Ma motivation immédiate pour prouver cela était de remplir une vague de main dans ma preuve ci-dessus que, si une solution de cube parfait existe, elle est optimale. Cependant, cette formule pourrait être utile pour l'élagage de l'arbre de recherche.

Pensées variées

Je ne vois aucune symétrie évidente, sauf l'interchangeabilité de x, y et z, qui ne nous donne au mieux qu'un facteur constant de 6. Nous avons quelques accélérations pour la partition 2 qui disent essentiellement que nous voudrions que les deux termes soient être aussi proches les uns des autres que possible, mais je ne vois pas immédiatement d'application à ce problème.

Du haut de ma tête, le simple fait de prendre le journal de tous les nombres le réduit immédiatement à un problème classique à 3 partitions en utilisant l'addition, ou de manière équivalente, en prenant un certain nombre à la puissance des nombres dans n'importe quel problème d'addition à 3 partitions le transforme en un problème de multiplication comme celui-ci. Cela implique que ce problème ne devrait pas être plus facile. Nous avons ici la factorisation principale, alors que cette factorisation ne serait pas première, mais cela nous aide-t-il?

Graphiquement, la surface xyz = 0 ressemblerait à l'union des plans xy, yz et xz, et pour tout n positif, l'équation ressemblerait à y = n / xz, donc chaque tranche le long d'un plan de coordonnées serait une hyperbole. Nous pouvons généralement dire que la quantité que nous essayons de minimiser est la plus faible à l'origine et croît le plus rapidement le long de la ligne où x = y = z. Si nous ne pouvons rechercher que le long de cette variété, nous pourrions être en mesure de réduire à un problème à deux dimensions.

Davislor
la source
Si x + y + z = n, 2 ^ n = 2 ^ (x + y + z) = 2 ^ x * 2 ^ y * 2 ^ z, qui est une instance de ce problème moins la restriction que les entrées sont un décomposition primaire du produit. Ils seraient plutôt tous des pouvoirs de deux.
Davislor
Il est vrai que le poids à minimiser sera différent, mais si x = y = z dans le problème d'origine, x'y '+ x'z' + y'z 'ne sera pas minimisé dans le problème correspondant où chaque w est remplacé par w '= 2 ^ w, ce qui signifie que si une solution au problème d'origine existe, la réduction la trouverait-elle? Nous pourrions obtenir une solution erronée du problème transformé, mais nous pouvons le détecter en temps linéaire lors de la reconversion en vérifiant les sommes.
Davislor
xy+yz+xzxyz=nx,y,zn3
@vzn: Nous essayons de minimiser la surface, pas de la maximiser. Si le problème à 3 partitions a une solution, cela se traduit par un problème de dimension de boîte modifié où la solution est un cube parfait. Un algorithme hypothétique poly-temps trouverait les facteurs des côtés de ce cube, et nous pourrions ensuite le traduire dans le domaine d'origine, tout en vérifiant les solutions parasites, en temps linéaire. Cela suggère qu'un algorithme pour un problème légèrement détendu pourrait servir d'oracle à un problème difficile, ce qui rend peu probable l'existence d'un algorithme meilleur que exponentiel.
Davislor
? je ne suis pas en désaccord avec vous. ne dit-on pas la même chose? plz drop par Computer Science Chat pour démêler / trier cela plus loin. ne peut pas non plus suivre @DWs qui prétend que la transformation logarithmique ne fonctionne pas, pouvez-vous? utilise certaines de vos analyses (apparemment sur la cible) comme base pour ma propre réponse.
vzn