Discussion :

[mllm_so]

Bonjour,

Aprés avoir intérrogé 7 "IA" populaires avec la question du même titre, la réponse commune est "qu'on sait pas vraiment".

Par exemple DeepSeek dit:

État actuel (2023) :

N (taille de l'ensemble de nombres) : Les algorithmes exacts peuvent gérer des ensembles de taille modérée (par exemple, N ≈ 50 à 100) en temps raisonnable, mais deviennent rapidement impraticables pour des N plus grands.

K (nombre de sous-ensembles) : Le nombre de sous-ensembles K influence également la complexité. Pour K = 2, le problème est plus simple, mais pour K > 2, la complexité augmente considérablement.

Suite à cela je finis de la part de DeepSeek avec le défi suivant:

Défi proposé:

N (taille de l'ensemble de nombres) : 500 nombres.
Plage des nombres : Chaque nombre est un entier aléatoire compris entre 1 et 10 000 000.
K (nombre de sous-ensembles) : 10 sous-ensembles.

Objectif : Partitionner ces 500 nombres en 10 sous-ensembles de taille égale (50 nombres par sous-ensemble) tout en minimisant la différence entre les sommes des éléments de chaque sous-ensemble.

DeepSeek dit que "Si un tel problème est résolu de manière efficace, cela constituerait un record notable dans le domaine de l'optimisation combinatoire." (Moi: d'autres IA ou personnes diront peut être autre chose, je ne sais pas à voir...)

La pertinence du défi a été validé par toutes les autres "IA", j'ai donc relevé mais surtout réussi le défi !

Pour ceux que ça intéresse, les résultats se trouvent: https://drive.google.com/drive/folde...8_?usp=sharing

Note 1: En plus d'être datée du 2025-02-08, la liste de nombres utilisée provient d'une source externe (voir fichier multiset.txt).
Note 2: Au regard des (autres) datas que je possède, l'interêt tiens plus de l'exercice que du défi.

[mllm_so]

Au lieu de me mettre des moins 1, feriez mieux de mettre un commentaire et de faire part de votre expertise ! Ttop facile d'arriver des cookies plein la bouche, de pouffer de rire, de mettre son petit moins 1 et de se barrer sans rien justifier ! Exprimez-vous !

[mllm_so]

Optimal_Balanced_Multi_Way_Number_Partitioning - 10 000 numbers - Range [1 - 1 000 000] - K_1_000 - (2 solutions): - date.2025-02-10
https://drive.google.com/drive/folde...U-?usp=sharing

Ce qu'en pense nos chères "IA" (en gros elles disent que le partitionnement ci-dessus n'est pas possible et que si ça l'était...):
Grok: https://x.com/i/grok/share/08oCP7RbSI8AoKc9HbF8ri9O2
ChatGPT: https://chatgpt.com/share/67ab54af-e...2-adfd524d974d
Gemini: https://g.co/gemini/share/0bac0c59663f
Qwen: https://chat.qwenlm.ai/s/662a877d-ef...5-3266774c1292

Et ici ça dit quoi ? Y'a un expert ?

[laurent_ott]

Bonjour,
Je ne suis pas un expert du sujet, je vais rarement sur ce forum et je viens de découvrir votre discussion.
Je vous invite, puisque c'est une discussion, à présenter plus précisément votre démarche (au lieu de liens sur un site où l'on ne s'y retrouve pas forcément), c'est à dire votre logique de raisonnement, un algorithme, un pseudo code, un exemple de données, pour que l'on puisse rejouer tout ça voir ce que ça donne.
Cordialement.

[mllm_so]

@laurent_ott
(Vous dîtes ne pas être expert et venir rarement sur ce site alors que vous avez un paquet de publications pointues sur ce dît site. Je vais répondre à votre question même si celle ci semble vouloir me tester)

Ok en termes simples: Officiellement jusqu'à aujourd'hui, on sait pas partitionner efficacement toutes listes de nombres. On sait partitionner les petites mais pas les grandes.

Plus la liste est grande ou que les nombres sont grands, plus il est difficile, voire impossible, d'obtenir un partitionnement respectant les contraintes de somme et de taille pour chaque sous ensembles. Dés lors on utlise des algorithmes d'approximation.

A quoi ça sert ?
A gerer l'espace (disponible), le temps (imparti) et les forces (équilibre).

Dans la communauté scientifique ce genre de problème de partitionnement est majoritairement considéré pour les cas les plus difficiles, comme impossible à résoudre, sauf que si je m'en tiens à ce que disent les "IA", je viens de démontrer le contraire ou du moins en partie !

Les "IA" construisent leurs réponses en amalgamant toutes sortes de publications scientifiques. Elle sont théoriques mais je ne connais pas le gap entre la théorie et la pratique. D'oû la question de ce post "Quelles sont les limites..."

Un expert "honnête" pourra en dire plus. Un expert "honnête", oui, parce que certains préfèrent vous dénigrer (les petits -1 font partie de ce stratagème de dénigrement) ou pire vous insulter !

Pour toutes informations complémentaires je vous suggère d'intéroger une "IA"

- Les exemples de données sont déjà disponibles via les liens précédents https://drive.google..... Je vérrai plus tard pour des petites datas.
- Désolé je n'ai pas de code, ni de méthode à partager.

[dourouc05]

On sait partitionner les petites mais pas les grandes.

Traduction : on ne peut pas. Si ça ne marche que pour de petits exemples, c'est que c'est inutilisable. Apparemment, tu n'as pas testé si ça marchait pour de petits exemples.

Dés lors on utlise des algorithmes d'approximation.

Ou pas : vive les heuristiques, les approches très généralistes de type MIP ou CP ? Pour beaucoup de problèmes similaires, ça fait des miracles. Tout dépend de ce que tu cherches à faire (ce que tu ne dis pas).