Voici mon problème:
Je voudrais organiser N entiers positifs dans une matrice AxB, de sorte que la différence entre les cellules voisines soit minimisée. N est supérieur à AxB donc j'ai beaucoup de choix possibles.
Par exemple, si j'ai les nombres 1,3,4,9,21 à positionner dans une matrice 2x2,
Je peux construire cette matrice:
1 4 5 9
nous pouvons calculer la somme de la différence entre les cellules voisines: (5-4) + (5-1) + (9-4) + (9-1) = 1 + 4 + 5 + 8 = 18
mais si je réorganise les nombres de cette façon:
5 4 1 9
la somme est maintenant (5-1) + (4-1) + (9-5) + (9-4) = 4 + 3 + 4 + 5 = 16 ce qui est mieux.
Je pensais utiliser la force brute, en changeant chaque nombre et en calculant la somme à chaque fois, mais mon problème actuel a une matrice 4 * 5 et 41 nombres au choix donc le nombre de possible matrices est 41! / 20! (654 764 331 820 982 885 260 361 465 856).
Quelqu'un a-t-il une idée de comment aborder le problème différemment?
4 Réponses :
Le simple fait de remplir la matrice de manière intelligente ne serait-il pas un bon début?
disons que vous avez les nombres suivants: 1 2 4 6 7 8 9 13 17 Ne pouvez-vous pas remplir la matrice de la manière suivante: En commençant par le plus petit nombre dans un coin, remplissez la matrice comme suit:
1 2 6 4 7 9 8 13 17
Ce qui aurait pour résultat:
i1 i2 i4 i3 i5 i7 i6 i8 i9
À partir de ce résultat de départ, vous pouvez simplement essayer d'échanger des positions aléatoires et voir si la somme de chaque nombre voisin diminue. Si le résultat diminue, répétez cette opération, sinon essayez un échange différent.
Je ne sais pas si cela se heurte au minimum local rapidement, vous pouvez également choisir de faire plusieurs échanges avant d'évaluer si le résultat diminue.
EDIT: Je vois maintenant que vous avez plus de nombres que ceux qui correspondent réellement à la matrice. Je suppose que ce sont tous uniques. Donc, choisir un sous-ensemble qui a la différence moyenne la plus faible entraînera probablement aussi une matrice qui a la somme de voisins la plus basse.
Bonne chance
Je pense que vous pourriez faire mieux en utilisant une courbe de remplissage d'espace avec une meilleure propriété de localité, par exemple une courbe de Hilbert
nvm, en essayant avec les nombres 1-16 J'ai obtenu 68 en utilisant votre approche, 67 en utilisant une courbe de hilbert et 60 en remplissant les nombres de gauche à droite ligne par ligne.
@SaiBot qu'est-ce que la matrice donne un résultat de 60?
@ user10472446 4x4 si je n'ai commis aucune erreur, alors [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]. Chaque ligne a la somme des différences de 3 et chaque colonne a la somme des différences de 12, ce qui fait 4 * 3 + 4 * 12 = 60.
@SaiBot: Vous avez cloué un cas dégénéré de la réponse que j'ai à l'esprit. Je suis sûr que le PO apprécierait toute information supplémentaire que vous pourriez avoir; équilibre en laissant quelque chose à OP à résoudre.
@SaiBot Et quelle est la matrice donnant le résultat 68?
@ user10472446 vous pêchez à la traîne? J'ai utilisé la méthode de cette réponse [[1, 2, 4, 7], [3, 5, 8, 11], [6, 9, 12, 14], [10, 13, 15, 16]]
C'est en fait un problème plus simple. Frappez-le avec votre algèbre de l'école primaire. Tout d'abord, un petit aperçu montrera que vous voulez toujours que les nombres soient triés de haut à gauche en bas à droite. Soit ascendant soit descendant fera l'affaire; ils sont isomorphes. Supposons ascendant, pour correspondre à vos exemples. Pour un ensemble de 9 nombres:
// ROWS i2-i1 + i3-i2 + i5-i4 + i6-i5 + i8-i7 + i9-i8 + // COLUMNS i4-i1 + i7-i4 + i5-i2 + i8-i5 + i6-i3 + i9-i6
Nous devons additionner les termes
i1 i2 i3 i4 i5 i6 i7 i8 i9
Cela se réduit à i3-i1 + i6-i4 + i9-i7 + i7-i1 + i8-i2 + i9-i3
Et cela devient 2 * i9 - 2 * i1 + i6 + i8 - (i2 + i4)
Commencez par trier vos numéros N et recherchez la sous-séquence contiguë de A code > * B nombres avec la plus petite différence entre le plus bas et le plus élevé. Ensuite, arrangez les numéros de bordure sans coin de sorte que la différence (supérieure + gauche) - (inférieure + droite) soit minimisée, en notant combien de nombres peuvent entrer entre chaque paire. Enfin, remplissez le milieu de toute manière légale.
Très simplement, cela se réduit à la somme des bords supérieur et gauche, moins les bords inférieur et droit. Les coins principaux comptent double; les coins supérieur droit et inférieur gauche, ainsi que tous les termes internes, abandonnent.
Oui, j'ai laissé de côté quelques étapes logiques ... J'espère que c'est un indice suffisant pour tu. Il réduit l'espace de recherche des nombres A * B pris de N à deux séquences contiguës de nombres A + B-2 dans cette séquence de A * B .
Les différences sont en fait | i2 - i1 | . Le module empêche la réduction (sinon agréable).
@ user58697 Comme je l'ai mentionné dans le premier paragraphe, un petit aperçu montre que la réponse optimale aura les valeurs triées, de sorte que toutes les différences seront dans le même sens.
Merci, c'est en effet plus simple que je ne le croyais au début! J'essaierai votre solution.
@Prune: la solution ne peut-elle pas être simplement réduite à la liste des éléments croissants successifs qui ont la plus petite différence entre le premier et le dernier élément puisque par les équations il faut qu'il existe: i9> i8> i2 et i9> i6> i4 ? Ensuite, les éléments doivent simplement être ordonnés comme l'exemple de SaiBot, n'est-ce pas?
@ user10472446 Non. Ce fut ma première impression, mais je me suis vite rendu compte que ce n'était pas le cas. D'autres commentaires ont déjà montré l'arithmétique sur un 4x4 (résultats 68, 67 et 60). Surtout, voyez le résultat algébrique dans ma réponse ci-dessus: les termes de bord ne tombent pas hors de l'équation. Vous devez minimiser la différence entre les bords supérieur et gauche, par rapport aux bords inférieur et droit.
Très simplement, cela se réduit aux sommes des bords supérieur et gauche, moins les bords inférieur et droit. Les coins principaux comptent double; Les coins NE et SW, et tous les termes internes, abandonnent.
@Prune Il y a une erreur dans les commentaires. Le terme à minimiser est en fait plus petit pour la matrice de valeurs en constante augmentation (60) par rapport à l'autre matrice calculée ci-dessous. Donc, si la méthode de minimisation utilisée avait été correcte, elle aurait trouvé ce 60 et la matrice correspondante. Dans mon calcul ci-dessous, vous devez ajouter 30 pour compter les deux coins qui sont identiques pour les deux matrices. Quoi qu'il en soit, cela semble une bonne heurictique ...
"un peu de perspicacité" est une onde manuelle. Pouvez-vous prouver que la solution optimale a trié les nombres comme vous le décrivez?
Aussi, concernant "Commencez par trier vos numéros N et trouvez la sous-séquence contiguë des nombres A * B avec la plus petite différence entre le plus petit et le plus élevé. ", il n'y a aucune garantie que la réduction de cette différence produise une solution optimale. Par exemple, [[-100, 0, 0], [0, 0, 0], [0, 0, 100]] bat [[901, 901, 901], [ 901, 901, 1099], [1099, 1099, 1099]] .
@ user2357112: "un peu de perspicacité" est assez simple, mais pas bref. Supposons qu'une sous-matrice triée non existe. Caractérisez les possibilités. Exprimez la somme de là à une contradiction.
@ user2357112: bon contre-exemple; oui, cela ressort clairement de l'expression eval au bas de mon algèbre.
Pour revenir sur la solution @Prune et les différents commentaires, il est important de comprendre l'équation résultante.
Parce que les nombres sont ordonnés sur chaque ligne et chaque colonne l'équation globale avec abs () code > est simplifié en pour toutes les lignes et colonnes sum(last-first).
L'équation résultante contient six groupes qui sont additionnés 2 * RB - 2 * TL + RE + BE - LE - TE où:
L'idée est de minimiser l'élément de bord RE + BE - LE - TE pour les éléments RB et TL choisis .
Si nous appliquons cette formule à la matrice ci-dessous, le résultat pour l’élément de bord est 8 + 12 + 14 + 15-2-3-5-9 = 49-19 = 30 code>
Elements = [3, 6, 59, 75, 76, 120, 132, 140, 226, 233, 237, 296, 349, 351, 351, 381, 422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845, 897, 902, 927, 982, 999] Distances for the 22 possible matrices = [2447, 2459, 2420, 2464, 2510, 2386, 2336, 2357, 2318, 2319, 2310, 2192, 2096, 2093, 2038, 1961, 1893, 1952, 2000, 2025, 2127, 2128] List of indexes where min values are = [16] Minimum value found = 1893 Matrix found = [422, 468, 478, 499, 523, 540, 570, 588, 597, 629, 687, 707, 714, 740, 742, 746, 755, 781, 812, 845] Elements = [37, 45, 55, 78, 87, 110, 142, 157, 287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575, 578, 610, 689, 717, 748, 757, 773, 935, 944, 954, 956, 994, 998] Distances for the 22 possible matrices = [2106, 2126, 2105, 1921, 1866, 1745, 1679, 1574, 1402, 1411, 1492, 1687, 1766, 1876, 1882, 1906, 2322, 2433, 2603, 2658, 2655, 2871] List of indexes where min values are = [8] Minimum value found = 1402 Matrix found = [287, 294, 302, 309, 313, 333, 356, 379, 380, 406, 422, 456, 461, 466, 467, 475, 506, 551, 556, 575] Elements = [25, 26, 28, 78, 80, 92, 93, 100, 115, 149, 170, 209, 222, 252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642, 730, 756, 771, 771, 793, 798, 856, 937] Distances for the 22 possible matrices = [1797, 1839, 1875, 1841, 1885, 1878, 1962, 2041, 2042, 1990, 1883, 1832, 1827, 1793, 1907, 1913, 2010, 2124, 2167, 2211, 2235, 2340] List of indexes where min values are = [13] Minimum value found = 1793 Matrix found = [252, 269, 333, 344, 366, 371, 371, 384, 412, 437, 446, 469, 498, 547, 553, 557, 563, 597, 626, 642] Elements = [19, 82, 97, 108, 123, 162, 178, 207, 224, 243, 264, 290, 307, 333, 350, 364, 393, 419, 428, 459, 514, 582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962] Distances for the 22 possible matrices = [2000, 2002, 2147, 2337, 2475, 2547, 2582, 2693, 2733, 2740, 2754, 2695, 2754, 2778, 2745, 2722, 2547, 2446, 2307, 2138, 1952, 1706] List of indexes where min values are = [21] Minimum value found = 1706 Matrix found = [582, 646, 679, 696, 698, 758, 761, 786, 815, 833, 853, 875, 875, 894, 902, 905, 923, 959, 961, 962] Elements = [190, 220, 240, 249, 259, 264, 349, 353, 365, 380, 392, 399, 410, 427, 437, 491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840, 881, 909, 910, 911, 944, 990] Distances for the 22 possible matrices = [1815, 1853, 1902, 1874, 1863, 1760, 1679, 1651, 1624, 1669, 1593, 1620, 1564, 1557, 1569, 1517, 1603, 1614, 1607, 1625, 1644, 1746] List of indexes where min values are = [15] Minimum value found = 1517 Matrix found = [491, 501, 522, 564, 578, 621, 627, 639, 643, 657, 662, 668, 684, 712, 713, 714, 733, 782, 804, 840] Elements = [50, 64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453, 532, 547, 587, 606, 619, 650, 671, 687, 707, 718, 739, 765, 803, 832, 837, 853, 861, 917, 923, 954] Distances for the 22 possible matrices = [1878, 1844, 1993, 1953, 2070, 2068, 2060, 2179, 2086, 2107, 2029, 1906, 2036, 2050, 2157, 2214, 2162, 2214, 2144, 2176, 2107, 1971] List of indexes where min values are = [1] Minimum value found = 1844 Matrix found = [64, 82, 114, 142, 173, 181, 183, 228, 237, 279, 340, 340, 356, 359, 379, 400, 415, 425, 427, 453] Elements = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425, 464, 469, 484, 505, 539, 540, 602, 620, 641, 677, 719, 748, 751, 777, 817, 830, 893, 904, 932, 952, 997] Distances for the 22 possible matrices = [1536, 1680, 1817, 1871, 1994, 2119, 2138, 2258, 2241, 2312, 2469, 2538, 2693, 2678, 2690, 2726, 2619, 2655, 2467, 2426, 2482, 2515] List of indexes where min values are = [0] Minimum value found = 1536 Matrix found = [48, 49, 75, 107, 108, 126, 132, 142, 142, 167, 170, 216, 220, 222, 246, 250, 253, 269, 374, 425] Elements = [7, 39, 46, 62, 66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408, 498, 559, 624, 624, 640, 654, 655, 740, 742, 757, 825, 862, 879, 908, 950, 956, 977] Distances for the 22 possible matrices = [1674, 1670, 1647, 1628, 1586, 1608, 1753, 1928, 2066, 2162, 2256, 2317, 2449, 2484, 2413, 2521, 2605, 2822, 2942, 2952, 3004, 2875] List of indexes where min values are = [4] Minimum value found = 1586 Matrix found = [66, 85, 127, 151, 191, 205, 220, 221, 228, 234, 240, 303, 324, 329, 338, 352, 364, 366, 408, 408] Elements = [17, 161, 185, 192, 211, 231, 291, 307, 319, 346, 348, 369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680, 770, 795, 798, 802, 812, 836, 889, 892, 931, 931] Distances for the 22 possible matrices = [2079, 1729, 1697, 1616, 1524, 1546, 1484, 1526, 1523, 1477, 1475, 1453, 1578, 1628, 1651, 1729, 1755, 1857, 1949, 1952, 1996, 1951] List of indexes where min values are = [11] Minimum value found = 1453 Matrix found = [369, 391, 415, 447, 449, 473, 477, 491, 498, 518, 525, 529, 545, 589, 625, 632, 639, 645, 655, 680] Elements = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415, 489, 500, 582, 659, 662, 667, 683, 705, 716, 731, 734, 776, 785, 803, 819, 841, 877, 883, 949, 951, 995] Distances for the 22 possible matrices = [1919, 2197, 2292, 2465, 2756, 2761, 2948, 2870, 2774, 2725, 2492, 2541, 2496, 2491, 2541, 2478, 2465, 2384, 2276, 2224, 2041, 1986] List of indexes where min values are = [0] Minimum value found = 1919 Matrix found = [10, 23, 29, 50, 61, 71, 72, 82, 137, 147, 249, 262, 267, 295, 303, 340, 346, 366, 369, 415]
Si nous appliquons cette formule à la matrice ci-dessous, le résultat pour l'élément de bord est 11 + 14 + 13 + 15-2-4-3- 6 = 53-15 = 38 ce qui n'est pas minimal.
1 2 4 7 3 5 8 11 6 9 12 14 10 13 15 16
Donc, à cet égard, la minimisation de la composante de bord semble être une bonne approche. Le problème est de savoir comment minimiser cet élément tout en respectant les règles de > le long des lignes et des colonnes . Cependant il est probable que remplir la matrice de gauche à droite et de haut en bas avec les nombres dans l'ordre donnera des résultats assez bons.
Concernant votre problème de matrice 4 * 5 avec 41 valeurs disponibles, il serait intéressant de comparer les 22 matrices que vous pouvez obtenir après avoir trié ces 41 nombres, en les remplissant linéairement et voir si la matrice s avec le plus petit écart entre les éléments extrêmes (je viens de réaliser que vous pourriez avoir plusieurs matrices ayant la même distance entre le premier et le dernier élément mais avec des distances totales différentes) est vraiment celle s avec une "distance" minimale telle que définie par le abs () code> formule.
Faites-nous savoir.
Voici quelques exemples, pour un 4x5 (lignes x cols ) matrice. Je serais intéressé de voir les résultats avec d'autres méthodes pour voir dans quelle mesure la méthode est idéale!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Je ne sais pas si le simple tri est optimal. Mais c'est certainement un bon point de départ. Avec un ensemble de données aléatoires, je vois:
La deuxième solution a été trouvée avec un modèle de programmation en nombres entiers mixtes . Cela s'est avéré optimal (mais j'ai ajouté la contrainte selon laquelle les valeurs augmentent par ligne et par colonne).
Si la contrainte selon laquelle les valeurs augmentent par ligne et par colonne est supprimée, quelle matrice obtenez-vous alors?
@ user10472446 Cela s'avère être un problème difficile. Je l'ai laissé tourner pendant quelques heures mais je n'ai pas pu améliorer cette solution (mais l'écart était toujours important: plus de 10%). Avec les contraintes supplémentaires, c'est un problème facile à résoudre. Je soupçonne qu'ils ne coupent pas la solution optimale.
Quel logiciel avez-vous utilisé? Où pouvons-nous le trouver?
J'ai utilisé GAMS + Cplex.
Quelques réflexions: L'intuition suggère que vous devriez jeter les valeurs aberrantes jusqu'à ce que vous en ayez autant que vous avez d'emplacements. Donc (comme vous le faites) éliminez d'abord 21 car il est plus éloigné de 9 que 1 est de 3. Ensuite, puisque les différences entre les voisins diagonaux ne sont pas comptées dans le résultat, vous devriez probablement organiser les nombres par la plus grande différence le long des lignes diagonales (comme en fait vous faites dans l'exemple).
@ user7285170 pouvons-nous avoir la liste de 41 numéros à choisir de votre problème?