Weak Schur numbers

lums.fr

Résumé

Cet article, empruntant le style d'un papier scientifique, représente mon journal de bord. Un carnet de voyage que j'étoffe, depuis février 2014, de mes expéditions au pays des weak Schur numbers.
J'ai intégré à cette page une partie des algorithmes que j'ai développé. Ils sont disponibles via l'objet weak_schur dans la console du navigateur.
Cette page est en cours d'écriture, j'essaie de l'enrichir quand j'en ai le temps.

Introduction

Présentation du sujet

Les weak Schur numbers sont un problème d'algorithmie définit ainsi : un ensemble $A$ d'entiers est dit « libre » si il ne contient pas trois éléments distincts $x,y,z$ tel que $x + y = z$. Avec $k \geq 1$, notons $WS(k)$ le plus grand entier $n$ pour lequel $\{1, \ldots, n\}$ admet une partition en $k$ sous-ensembles « libres ».

Le but est de trouver la valeur $WS(k)$ quelque soit $k$ en un temps polynomial.

Une façon plus ludique de se représenter ce problème est de le considérer comme un jeu dans lequel le but est de ranger les nombres (d'abord $1$, puis $2$, puis $3$ etc.) dans un certain nombre de paquets. Pour pouvoir insérer un nombre dans un paquet, on ne doit pas pouvoir trouver deux nombres dans ce paquet dont la somme est égale au nombre que l'on cherche à insérer. Par exemple : si dans un paquet j'ai déjà les nombres $1, 2$, on ne pourra pas insérer le nombre $3$ car $1 + 2 = 3$.

Le but du jeu est de deviner rapidement combien il est possible d'insérer de nombres au maximum en fonction du nombre de paquets disponibles.

Définitions

Nous allons utiliser, dans ce papier, un certain nombre de notion et dans cette partie nous allons en définir une bonne partie.

Un ensemble

Un ensemble contient des nombres entiers naturels. Par convention, on nomme les ensembles par une lettre : « $A$ », puis « $B$ », puis « $C$ » et ainsi de suite. Un ensemble est libre si il ne contient pas trois éléments distincts $x,y,z$ tel que $x + y = z$. Si un ensemble n'est pas libre, on dit qu'il est contraint.
L'ensemble $A$ est contraint car $1 + 2 = 3$ : $$A = \{1, 2, 3\}$$
L'ensemble $A$ est libre : $$A = \{1, 2, 4\}$$

Une collection

Puisque nous allons travailler avec plusieurs ensembles, on note cette collection d'ensembles $\sigma$. Cette collection peut contenir des ensembles vides, libres ou contraints. Au même titre que les ensembles qui la composent, une collection peut être libre ou contrainte : contrainte si au moins un de ses ensembles est contraint, libre sinon.
La collection $\sigma$ est contrainte car l'ensemble $B$ est contraint ($2 + 3 = 5$) : $$\sigma = \begin{cases} A = \{1\} \\ B = \{2, 3, 4, 5\} \end{cases}$$
La collection $\sigma$ est libre : $$\sigma = \begin{cases} A = \{1, 2\} \\ B = \{\} \end{cases}$$
Tout comme la taille d'un ensemble se note $|A|$, la taille d'une collection se note également $|\sigma|$ et est égale à la somme de la taille des ensembles qui la compose : $$|\sigma| = \sum_{S \in \sigma} |S|$$
La racine de la collection $\sigma$ à $k$ ensembles correspond à la collection $\sigma'$ à $k - 1$ ensembles par laquelle débute $\sigma$.
Si $$\sigma = \begin{cases} A = \{1, 2, 5\} \\ B = \{3, 4\} \end{cases}$$ alors $$\sigma' = \begin{cases} A = \{1, 2\} \end{cases}$$
Deux collections sont équivalentes lorsque les ensembles qui la composent sont identiques indépendemment de leur nom. On peut ordonner les ensembles sans modifier les propriétés de la collection et, dans ces recherches, on range toujours les ensembles par ordre croissant de leur plus petit élément. Si un ensemble est vide, on le place toujours à la fin.
Si $$\sigma' = \begin{cases} A = \{3, 5\} \\ B = \{1, 2, 4\} \\ C = \{\} \\ D = \{6, 7, 8\} \end{cases}$$ $$\sigma'' = \begin{cases} A = \{6, 7, 8\} \\ B = \{\} \\ C = \{3, 5\} \\ D = \{1, 2, 4\} \end{cases}$$ alors $$\sigma' = \sigma'' = \sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5\} \\ C = \{6, 7, 8\} \\ D = \{\} \end{cases}$$

Les optima

Un optimum local est une collection $\sigma$ libre pour laquelle il est impossible d'ajouter le prochain nombre $|\sigma| + 1$ sans la contraindre.
La collection $\sigma$ n'est pas un optimum local car il est possible d'ajouter $5$ dans $B$ : $$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3\} \end{cases}$$
La collection $\sigma$ n'est pas un optimum local car $\sigma$ est contraint : $$\sigma = \begin{cases} A = \{1, 2, 3\} \\ B = \{4, 5\} \end{cases}$$
La collection $\sigma$ est un optimum local : $$\sigma = \begin{cases} A = \{1, 4\} \\ B = \{2, 3\} \end{cases}$$
Les optima globaux sont le sous-groupe des optima locaux ayant la plus grande taille, taille que l'on note $WS(k)$. Il n'existe pas encore de méthode pour trouver $WS(k)$ sans, au préalable, avoir recensé tous les optima locaux du problème : et sans ce recensement, $WS(k)$ est incertain.
On utilise la notation $\mu^{local}_{l}(k)$ pour représenter la quantité d'optima locaux de taille $l$ à $k$ ensembles. La taille $l$ est optionnelle : si elle n'est pas précisée on se sert de cette notation pour représenter la quantité d'optima locaux de toutes tailles à $k$ ensembles : $$\mu^{local}(k) = \sum_{i=1}^{WS(k)} \mu^{local}_{i}(k)$$
À $k = 2$ ensembles, il existe neuf optima locaux : $$\mu^{local}(2) = 9$$
On utilise de la même manière la notation $\mu^{global}(k)$ pour représenter la quantité d'optima globaux, qui sont par définition de taille optimale (d'où l'absence du paramètre $l$), à $k$ ensembles.
À $k = 2$ ensembles, il n'existe qu'un seul optimum global : $$\mu^{global}(2) = 1$$

Encodage des collections

Il est possible d'utiliser différentes notations pour décrire une même collection. Selon les cas, certaines notations sont plus adéquates.

La notation classique énumère le contenu de chaque ensemble.
$$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5, 6, 7\} \end{cases}$$
La notation classique factorisée, comme la notation classique, énumère le contenu de chaque ensemble mais où chaque suite de nombres au sein d'un même ensemble est factorisé avec la notation $\frac{a}{}$ où $a$ est la quantité de nombres qui n'apparaissent plus par rapport à la notation classique.
$$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5 \frac{1}{} 7\} \end{cases}$$ représente $$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5, 6, 7\} \end{cases}$$
La notation littérale énumère le contenu de la collection sous la forme d'un mot lu de gauche à droite qui est à comprendre ainsi : le nombre $i$ est ajouté dans l'ensemble « $i$ème lettre du mot ».
$$\sigma = AABABBB$$ représente $$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5, 6, 7\} \end{cases}$$
La notation littérale factorisée part de la notation littérale et fait en sorte de ne jamais écrire deux fois la même lettre successivement. Pour ce faire, on écrit une lettre $L$ puis en dessous le nombre de fois $n$ qu'elle se répète successivement.
$$\sigma = \underset{2}{A}\underset{1}{B}\underset{1}{A}\underset{3}{B}$$ représente $$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5, 6, 7\} \end{cases}$$
La notation littérale binaire énumère le contenu de chaque ensemble de la collection sous la forme d'un mot lu de gauche à droite qui est à comprendre ainsi : le nombre $i$ est présent dans l'ensemble si la « $i$ème lettre du mot » vaut « 1 ».
$$\sigma = \begin{cases} A = \text{1101000} \\ B = \text{0010111} \end{cases}$$ représente $$\sigma = \begin{cases} A = \{1, 2, 4\} \\ B = \{3, 5, 6, 7\} \end{cases}$$

Représentation graphique des collections

La représentation graphique permet de visualiser la taille d'une solution ainsi que les nombres présents dans un ensemble et les contraintes qu'ils engendrent sur ce même ensemble :
  • un carré vert indique un nombre qui est inclu dans l'ensemble
  • un carré rouge clair indique un nombre qui est contraint par une seule paire dans l'ensemble (dans l'exemple qui suit, sur l'ensemble A, le nombre 3 n'est contraint qu'une seule fois par la paire {1,2})
  • un carré rouge foncé indique un nombre qui est contraint par plus d'une paire dans l'ensemble, le nombre de paires est précisé par un chiffre blanc à l'intérieur du carré (dans l'exemple qui suit, sur l'ensemble A, le nombre 12 est contraint deux fois par les paires {4,8} et {1,11})
  • un rond noir indique un nombre qui ne devrait pas être inséré dans l'ensemble (dans l'exemple qui suit, sur l'ensemble A, le nombre 7 est contraint ainsi par la paire {1,8} car 1 + 7 = 8)
représente $$\sigma = \begin{cases} A = \{1, 2, 4, 8, 11, 16, 22\} \\ B = \{3, 5, 6, 7, 19, 21, 23\} \\ C = \{9, 10, 12, 13, 14, 15, 17, 18, 20\} \end{cases}$$
La représentation graphique étendue étend la représentation graphique aux nombres entiers négatifs pour nous permettre d'ajouter une nouvelle dimension à l'analyse visuelle, on peut y observer certaines contraintes (je ne sais pas encore si ça me sera utile, à investiguer donc) :

représente également $$\sigma = \begin{cases} A = \{1, 2, 4, 8, 11, 16, 22\} \\ B = \{3, 5, 6, 7, 19, 21, 23\} \\ C = \{9, 10, 12, 13, 14, 15, 17, 18, 20\} \end{cases}$$

Lorsque l'on manipule les collections à l'aide de la représentation graphique, il y a un mécanisme qui se dégage lors de l'insertion d'un nouveau nombre dans un ensemble : si dans un ensemble on ajoute le nombre $n$ alors, visuellement, on copie les nombres $\{1, \ldots, n - 1\}$ directement derrière le nombre $n$ en identifiant comme contraint dans la partie collée les nombres qui sont présents dans la partie copiée. Prenons un exemple avec la collection $AABABBBA$ à l'instant où on ajoute $8$ dans $A$ : dans l'ensemble $A$, j'ai les nombres $1, 2, 4$ et j'ajoute donc $8$ ; alors les nombres $8+1, 8+2, 8+4$ sont contraints ; visuellement, on a l'impression d'avoir copié les nombres $\{1, \ldots, 7\}$ de l'ensemble $A$ pour le coller directement derrière le nombre $8$ en identifiant comme contraint dans la partie collée les nombres qui sont présents dans la partie copiée.

Jouer avec la représentation graphique des collections

Ci-après une version revisitée de la représentation graphique pour permettre d'intéragir avec.

Espace de recherche

Concernant un ensemble

Un nombre est soit dans un ensemble soit il n'y est pas. Il est donc possible de lister toutes les configurations possibles pour un ensemble d'une taille donnée. Par exemple, en reprenant la notation littérale binaire, voici la liste exhaustive des configurations possibles pour un ensemble de taille 5 :

  • 00000 (soit l'ensemble $\{\}$) est libre
  • 00001 (soit l'ensemble $\{5\}$) est libre
  • 00010 (soit l'ensemble $\{4\}$) est libre
  • 00011 (soit l'ensemble $\{4, 5\}$) est libre
  • 00100 (soit l'ensemble $\{3\}$) est libre
  • 00101 (soit l'ensemble $\{3, 5\}$) est libre
  • 00110 (soit l'ensemble $\{3, 4\}$) est libre
  • 00111 (soit l'ensemble $\{3, 4, 5\}$) est libre
  • 01000 (soit l'ensemble $\{2\}$) est libre
  • 01001 (soit l'ensemble $\{2, 5\}$) est libre
  • 01010 (soit l'ensemble $\{2, 4\}$) est libre
  • 01011 (soit l'ensemble $\{2, 4, 5\}$) est libre
  • 01100 (soit l'ensemble $\{2, 3\}$) est libre
  • 01101 (soit l'ensemble $\{2, 3, 5\}$) est contraint
  • 01110 (soit l'ensemble $\{2, 3, 4\}$) est libre
  • 01111 (soit l'ensemble $\{2, 3, 4, 5\}$) est contraint
  • 10000 (soit l'ensemble $\{1\}$) est libre
  • 10001 (soit l'ensemble $\{1, 5\}$) est libre
  • 10010 (soit l'ensemble $\{1, 4\}$) est libre
  • 10011 (soit l'ensemble $\{1, 4, 5\}$) est contraint
  • 10100 (soit l'ensemble $\{1, 3\}$) est libre
  • 10101 (soit l'ensemble $\{1, 3, 5\}$) est libre
  • 10110 (soit l'ensemble $\{1, 3, 4\}$) est contraint
  • 10111 (soit l'ensemble $\{1, 3, 4, 5\}$) est contraint
  • 11000 (soit l'ensemble $\{1, 2\}$) est libre
  • 11001 (soit l'ensemble $\{1, 2, 5\}$) est libre
  • 11010 (soit l'ensemble $\{1, 2, 4\}$) est libre
  • 11011 (soit l'ensemble $\{1, 2, 4, 5\}$) est contraint
  • 11100 (soit l'ensemble $\{1, 2, 3\}$) est contraint
  • 11101 (soit l'ensemble $\{1, 2, 3, 5\}$) est contraint
  • 11110 (soit l'ensemble $\{1, 2, 3, 4\}$) est contraint
  • 11111 (soit l'ensemble $\{1, 2, 3, 4, 5\}$) est contraint

Une représentation visuelle est donnée ici avec un ensemble de taille 8.

Pour une taille $t$ donnée, le nombre total de configurations possibles est égal à $2^{t}$. Pour obtenir le nombre de configurations donnant des ensembles libres

Concernant les collections

L'espace de recherche $\Omega(k, n)$ répresente l'ensemble des collections qu'il est possible d'obtenir (contraintes ou non) à $k$ ensembles et de taille comprise entre $1$ et $n$ que l'on peut calculer ainsi : $$\Omega(k, n) = \Sigma_{i = 1}^{n} \Bigl( \lambda(k, i) + \Sigma_{j = 1}^{\min(k, i)} j \cdot \gamma(j, i) \Bigr)$$ avec $$\lambda(k, i) = \begin{cases} k \cdot \gamma(k + 1, i), & \text{si } k < i \\ 0, & \text{sinon} \end{cases} $$ et $$\gamma(b, n) = \begin{cases} 1, & \text{si } b = n \\ 0, & \text{si } b = 1 \text{ ou } n = 1 \\ (b - 1) \cdot \gamma(b, n-1) + \gamma(b-1, n-1), & \text{sinon} \end{cases} $$
On peut représenter cet espace comme un arbre de recherche à $k$ branches et $n$ niveaux de profondeur où $k$ représente donc le nombre d'ensembles que peut contenir une collection et $n$ la taille maximale d'une collection (idéalement $WS(k)$). Au sommet de cet arbre se trouve le noeud racine représentant le nombre $1$ et les $k$ branches qui partent de ce noeud représentent les $k$ ensembles dans lesquels peut être inséré le nombre $1$ ; à l'extrêmité de ces $k$ branches se trouvent autant de noeuds représentant chacun le nombre $2$ desquels partent $k$ branches représentants les $k$ ensembles dans lesquels peut être inséré le nombre $2$ ; et ainsi de suite. Mais toutes les branches de l'arbre ne sont pas à considérer du fait du mécanisme des équivalences entre les collections.
Au niveau $n = 1$ (le noeud racine au sommet de l'arbre de recherche), on aura toujours qu'une seule collection à prendre en compte (et donc qu'une seule branche) car placer le nombre $1$ dans l'ensemble $A$, ou $B$, ou $C$ etc. revient à placer le nombre $1$ dans l'ensemble $A$ : on a donc qu'une collection possible qu'on peut noter $A$ en notation littérale.
Au niveau $n = 2$, de la même manière, on aura deux collections possibles : $AA$ et $AB$ (avec $k \ge 2$) ; en effet, les collections $AC$ ou encore $AD$ sont équivalentes à la collection $AB$.
Au niveau $n = 3$ on aura cinq collections possibles : $AAA$, $AAB$, $ABA$, $ABB$ et $ABC$ (avec $k \ge 3$) ; en effet, les collections $AAC$ ou encore $AAD$ sont équivalentes à la collection $AAB$.

On remarque que l'on peut déduire le nombre de branches qui partent d'un noeud en observant le nombre de branches qui partent de son noeud parent. Prenons un exemple avec $k \gt 2$ pour mieux comprendre : si un noeud $M$ a deux branches, alors $M$ peut être inséré dans l'ensemble $A$ ou dans l'ensemble $B$. Conséquence : tous les noeuds parents de $M$ ($M - 1$, $M - 2$ et ce jusqu'à 1) ont forcément été tous insérés dans $A$ car si au moins l'un d'entre eux avait été inséré dans $B$, l'ensemble $C$ serait disponible et on aurait, du coup, $3$ branches pour le noeud $M$ et non $2$.

Dans l'arbre de recherche à $k$ ensembles : nombre de branches qui partent d'un noeud en fonction du nombre de branches $b$ qui partent de son noeud parent. Jusqu'à $b = 5$.
un noeud à $b$ branches crée $b$ noeuds à, respectivement $\ldots$ (avec $k \gt b$)
$b = 1$ 2 branches
$b = 2$ 2 et 3 branches
$b = 3$ 3, 3 et 4 branches
$b = 4$ 4, 4, 4 et 5 branches
$b = 5$ 5, 5, 5, 5 et 6 branches
Nombre de branches dans l'arbre de recherche, niveau par niveau, avec $k = 4$ et jusqu'au niveau 6.
Niveau Nombre de noeuds Nombre de branches factorisé Nombre de branches "par noeud"
Niveau 1 1 $1 \cdot 1 = 1$ 1
Niveau 2 1 $0 \cdot 1 + 1 \cdot 2 = 2$ 2
Niveau 3 2 $0 \cdot 1 + 1 \cdot 2 + 1 \cdot 3 = 5$ (2 + 3)
Niveau 4 5 $0 \cdot 1 + 1 \cdot 2 + 3 \cdot 3 + 1 \cdot 4 = 15$ (2 + 3) + (3 + 3 + 4)
Niveau 5 15 $0 \cdot 1 + 1 \cdot 2 + 7 \cdot 3 + 6 \cdot 4 + 1 \cdot 4 = 51$ (2 + 3) + (3 + 3 + 4) + (3 + 3 + 4) + (3 + 3 + 4) + (4 + 4 + 4 + 4)
Niveau 6 51 $0 \cdot 1 + 1 \cdot 2 + 15 \cdot 3 + 25 \cdot 4 + 10 \cdot 4 = 187$ (2 + 3) + (3 + 3 + 4) + (3 + 3 + 4) + (3 + 3 + 4) + (4 + 4 + 4 + 4) + (3 + 3 + 4) + (3 + 3 + 4) + (4 + 4 + 4 + 4) + (3 + 3 + 4) + (3 + 3 + 4) + (4 + 4 + 4 + 4) + (4 + 4 + 4 + 4) + (4 + 4 + 4 + 4) + (4 + 4 + 4 + 4) + (4 + 4 + 4 + 4)

On ne peut jamais obtenir plus de $k$ branches sur un noeud. Par exemple avec $k = 3$, un noeud à $3$ branches donne trois noeuds à, respectivement, $3$, $3$ et $3$ branches (et non $3$, $3$ et $4$ branches avec un $k$ plus grand). On peut donc en déduire qu'un noeud à $b$ branches donne $b$ noeuds à, respectivement, $b, b, \ldots, b$ ($b - 1$ fois) et $\min(k, b + 1)$ branches. Étape après étape, on peut créer ce tableau.

En faisant la somme du nombre de branches à chaque niveau, on obtient alors la taille de l'espace de recherche et sa formule.

L'état de l'Art nous donne un certain nombre de valeur pour $WS(k)$. Je présente dans ce tableau les différentes tailles de chaque espace de rechercheOn peut calculer le nombre de collections au total via weak_schur.Ω(k, n) disponible depuis la console du navigateur. Fonction développée à l'aide de la primitive BigInt pour pouvoir calculer des nombres aussi grands : ces nombres sont très rapidement inconcevablement démesurés. en fonction de $WS(k)$. J'en profite pour y ajouter le nombre d'optima locaux et globaux que j'ai pu dénombrer en parcourant exhaustivement cet espace.

Taille de l'espace de recherche et nombre d'optima en fonction du nombre d'ensembles $k$ et de $WS(k)$.
$k$ $WS(k)$ $\Omega(k, WS(k))$ $\mu^{local}(k)$ $\mu^{global}(k)$
1 2 2 1 1
2 8 255 9 1
3 23 2.353 $10^{10}$ 8067 3
4 66 3.024 $10^{38}$ 5.370 $10^{11}$ 29931
5 ≥ 196 ≥ 1.037 $10^{135}$
6 ≥ 646 ≥ 8.082 $10^{499}$
7 ≥ 2146 ≥ 8.808 $10^{1809}$
8 ≥ 6976 ≥ 2.559 $10^{6295}$
9 ≥ 22536 ≥ 1.997 $10^{21499}$
10 ≥ 71256 ≥ 3.061 $10^{71249}$

Déterminer $WS(k)$ est trivial jusqu'à $k = 3$ ensembles car il est possible de lister toutes les collections possibles via un parcours exhaustif de l'espace de recherche et donc de lister tous les optima locaux et ainsi en déduire tous les optima globaux. À partir de $4$ ensembles, l'espace de recherche est trop grand pour être exploré exhaustivement et, ainsi, rend la recherche des tous optima locaux impossibles et par conséquent : comment reconnaître un optimum global ?

Observations

Dans cette partie, nous allons étudier les résultats de la recherche exhaustive de l'espace de recherche à $k = 1, 2, 3 \text{ et } 4$. Nous allons observer les liens qu'il peut exister entre les optima des différents espaces de recherche.

À k = 1 ensemble

Avec un ensemble, on comptabilise 2On peut retrouver la liste des collections libres et des optima locaux à $k = 1$ ensemble en utilisant la fonction weak_schur.enumerates_sum_free_collections(1) et calculer le nombre de collections au total via weak_schur.Ω(1, 2) disponibles depuis la console du navigateur. collections libres listées ci-après par ordre alphabétique, on dénombre également 1 optimum locaux et donc 1 optimum global :

  • A
  • AA optimum local et optimum global

Ci-après la représentation graphique de l'optimum global :

  • AA

À k = 2 ensembles

Avec deux ensembles, on comptabilise 24On peut retrouver la liste des collections libres et des optima locaux à $k = 2$ ensembles en utilisant la fonction weak_schur.enumerates_sum_free_collections(2) et calculer le nombre de collections au total via weak_schur.Ω(2, 8) disponibles depuis la console du navigateur. collections libres listées ci-après par ordre alphabétique (auxquelles on peut ajouter les 2 collections libres à $k = 1$ ensemble), on dénombre également 9 optima locaux et 1 optimum global :

  • AAB
  • AABA
  • AABAB
  • AABABB
  • AABABBA optimum local
  • AABABBB
  • AABABBBA optimum local et optimum global
  • AABB
  • AABBA
  • AABBAB optimum local
  • AABBB
  • AABBBA optimum local
  • AABBBB
  • AABBBBA optimum local
  • AB
  • ABA
  • ABAB
  • ABABA optimum local
  • ABABB
  • ABABBA optimum local
  • ABB
  • ABBA optimum local
  • ABBB
  • ABBBA optimum local

Ci-après la représentation graphique de l'optimum global :

  • AABABBBA

On peut représenter l'espace de recherche sous la forme d'un arbre binaire pour nous permettre de visualiser où se situent les collections libres. À ce stade, je n'ai qu'une remarque à faire. Parmi les neuf optima locaux, on distingue quatre paires d'optima possédant le même le suffixe en notation littérale : $\ldots$$BA$ et $\ldots$$BBA$. Sur la figure ils dessinent un même pattern : une sorte de crochet vers la gauche. Seule la collection $AABBAB$ semble être isolée et est la seule à terminer par un $B$.

Représentation sous la forme d'un arbre binaire de profondeur 9 de toutes les collections possibles à 2 ensembles. Cet arbre se lit en associant un noeud (représentant un nombre) à une branche enfant (représentant un ensemble dans lequel insérer ce nombre) : lorsque la branche part à gauche on insère le nombre dans l'ensemble A et lorsque la branche part à droite on insère le nombre dans l'ensemble B. Exception faite du premier noeud représentant le nombre 1 qui est toujours placé dans l'ensemble A (via le mécanisme d'équivalence entre les collections). Le surlignage d'une paire noeud/branche est plein et noir quand la collection est libre et en pointillé et gris quand la collection est contrainte.

À k = 3 ensembles

Dans cette partie, on va étudier la topographie de l'espace de recherche à $k = 3$ ensembles et où se situent les optima locaux et globaux.

Il existeOn peut retrouver la liste des collections libres et des optima locaux à $k = 3$ ensembles en utilisant la fonction weak_schur.lists_sum_free_collections(3) et calculer le nombre de collections au total via weak_schur.Ω(3, 23) disponibles depuis la console du navigateur. ainsi :

  • $23\ 535\ 794\ 718$ collections au total ($= \Omega(3, 23)$)
  • $20\ 705$ collections libres
    • soit $0.000\ 087\%$ de l'espace de recherche
  • $8\ 067$ optima locaux
    • soit $38.962\%$ des collections libres
    • soit $0.000\ 034\%$ de l'espace de recherche
  • $3$ optima globaux
    • soit $0.037\%$ des optima
    • soit $0.014\%$ des collections libres
    • soit $0.000\ 000\ 013\%$ de l'espace de recherche

On peut catégoriser les optima en plusieurs familles selon leur racine (ici vingt-quatre familles).

À k = 4 ensembles

Dans cette partie, on va étudier la topographie de l'espace de recherche à $k = 4$ ensembles et où se situent les optima locaux et globaux.

En général

TODO: plus la racine est grande, plus la collection le sera

Réduction de l'espace de recherche

Parcours en profondeur (DFS)

L'algorithme de parcours en profondeur (ou DFS pour Depth-First Search) est un algorithme de parcours d'arbre. L'exploration d'un parcours en profondeur depuis un sommet S fonctionne comme suit. Il poursuit alors un chemin dans le graphe jusqu'à un cul-de-sac ou alors jusqu'à atteindre un sommet déjà visité. Il revient alors sur le dernier sommet où on pouvait suivre un autre chemin puis explore un autre chemin. L'exploration s'arrête quand tous les sommets depuis S ont été visités.

DFS via les impasses

Créer un DFS en se basant sur les impasses, à savoir quand on arrive à déterminer quel nombre on est certain de ne jamais pouvoir inclure dans aucun des ensembles :

  • 1 dans A : ✔️
  • 2 dans A : ✔️
  • 3 dans B : ✔️
  • 4 dans A : ✔️
  • 5 dans B : ✔️
  • 6 dans B : ✔️
  • 7 dans A : ❌ à 8
  • 7 dans B : ✔️
  • 8 dans A : ❌ à 9
  • 4 dans B : ✔️
  • 5 dans A : ❌ à 7
  • 5 dans B : ✔️
  • 6 dans A : ❌ à 7
  • 6 dans B : ✔️
  • 7 dans A : ❌ à 8
  • 2 dans B : ✔️
  • 3 dans A : ✔️
  • 4 dans B : ✔️
  • 5 dans A : ❌ à 6
  • 5 dans B : ✔️
  • 6 dans A : ❌ à 7
  • 3 dans B : ✔️
  • 4 dans A : ❌ à 5
  • 4 dans B : ✔️
  • 5 dans A : ❌ à 6

Algorithme déterministe

Cette algorithme essaie de faire le bon choix à chaque itération en créant des règles. Ces règles sont imaginées à partir des optima globaux que l'on connait déjà par recherche exhaustive. L'idée est de trouver un certain nombre de règles afin d'obtenir la liste exhaustive des optima globaux quel que soit $k$.

Définitions

  • Le « nombre courant » (noté $n$) représente le nombre que l'on essaie d'insérer dans la collection.
  • Le « mur » (noté $\tau$) représente le plus petit nombre pour lequel on sait qu'il nous sera impossible de l'insérer dans la collection. Ce nombre est contraint dans chacun des ensembles qui composent le collection. Par exemple : avec une collection vide le mur vaut 1, avec la collection $AA$ le mur vaut 3.
  • Quand il n'est possible de placer le nombre courant que dans un seul des ensembles libres de la collection sans la contraindre alors ce choix est appelé une « décision triviale ».
  • Une « solution complète » est une collection libre de taille $t$ pour laquelle tous les nombres entre $1$ et $t$ sont insérés.
  • Une « solution incomplète » est une collection libre de taille $t$ pour laquelle certains nombres (pas tous) entre $1$ et $t$ sont insérés.

Règles

  • L'« insertion triviale » : si pour le nombre courant on a une « décision triviale » alors on l'insère dans le seul ensemble possible.
  • Les « insertions triviales en série » : il s'agit de la règle de l'« insertion triviale » appliquée en série d'abord avec le nombre courant $n$, puis avec le nombre suivant $n + 1$ etc. jusqu'à ce que le nombre suivant ne soit plus trivial à insérer.
  • L'« ajout d'un nouvel ensemble à la collection » : si $n = \tau$ alors le nombre courant est contraint dans tous les ensembles de la collection, on ajoute alors un nouvel ensemble à la collection.
  • Le « processus de déduction » est l'un des mécanismes principaux de cet algorithme. L'objectif étant de déduire où doivent être insérés les nombres suivants dans la collection. Pour ce faire, on recense d'abord les différents nombres présents dans chaque ensemble puis on en déduit les contraintes qu'ils engendrent (par exemple, si un ensemble contient les nombres $1, 2$ alors le nombre $3$ est contraint). Une fois cet inventaire fait, on va insérer le plus petit nombre suivant (notons-le $m$ avec $m \gt n$) pour lequel il soit trivial de décider (c'est-à-dire pour lequel un seul ensemble est possible), si un tel nombre existe on l'insère dans le seul ensemble possible (notons-le $E$) puis on déduit les nombres contraints qu'il engendre et, surtout, on identifie les nombres $p$ tel que $p \lt m$ qui sont contraints par la présence de $m$ dans $E$ (si dans un ensemble on a les nombres $1, 2$, et on insère le nombre $m = 10$ alors les nombres $8$ et $9$ seront contraints car $1+ 9 = 10$ et $2 + 8 = 10$).

Création de l'ensemble A

La collection sur laquelle on travaille est initialement vide, elle ne contient aucun ensemble, on ne peut donc pas insérer de nombre. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble A. Se faisant, on obtient $WS(0) = 0$.

Insertions triviales des nombres 1 et 2

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 1 et 3.

Création de l'ensemble B

La collection possède un mur qui vaut précisément le nombre courant $\tau = n = 3$. On ne peut donc pas insérer plus de nombres en l'état. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble B. Se faisant, on obtient $WS(1) = 2$.

Insertion triviale du nombre 3

Le processus de déduction nous permet d'obtenir une solution complète en insérant le nombre 3.

Alternative pour le nombre 4

Pour 4, il est possible de l'insérer dans l'ensemble A et dans l'ensemble B. Pour savoir lequel il faut choisir, on va observer les conséquences qu'engendrent ces deux options via le processus de déduction.

  • 4 dans A
  • 4 dans B

Observations :

  • Choisir A : on obtient une solution complète de taille $8$ suivi d'un mur $\tau = 9$.
  • Choisir B : on obtient une solution complète de taille $7$ suivi d'un mur $\tau = 8$.

Insertions triviales des nombres 5 à 8

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 5 à 8.

Création de l'ensemble C

La collection possède un mur qui vaut précisément le nombre courant $\tau = n = 9$. On ne peut donc pas insérer plus de nombres en l'état. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble C. Se faisant, on obtient $WS(2) = 8$.

Insertions triviales des nombres 9 et 10

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres 9 et 10.

Alternative pour le nombre 11

Pour 11, il est possible de l'insérer dans l'ensemble A et dans l'ensemble C. Pour savoir lequel il faut choisir, on va observer les conséquences qu'engendrent ces deux options via le processus de déduction.

  • 11 dans A
  • 11 dans C

Observations :

  • Choisir A : on obtient une solution complète de taille $15$, une solution incomplète de taille $23$ (2 nombres manquants) suivi d'un mur $\tau = 24$.
  • Choisir C : on obtient une solution complète de taille $12$.

Insertions triviales des nombres 12 à 15

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 12 à 15. Comme on peut le voir dans le détail, il est possible d'insérer également les nombres de 18 à 23. Cependant, à ce stade, on ne peut pas être certain de pouvoir les insérer puisque les nombres 17 et 18 restent à insérer. On ne peut donc pas encore prédire les conséquences qu'engendreront leurs insertions en terme de contraintes.

Alternative pour le nombre 16

Pour 16, il est possible de l'insérer dans l'ensemble A et dans l'ensemble C. Pour savoir lequel il faut choisir, on va observer les conséquences qu'engendrent ces deux options via le processus de déduction.

  • 16 dans A (cet optimum global est la racine de 8 238 optima globaux (soit ~27.52% des optima globaux) à $k = 4$ ensembles)
  • 16 dans C

Observations :

  • Choisir A : on obtient une solution complète de taille $23$ suivi d'un mur $\tau = 24$.
  • Choisir C : on obtient une solution complète de taille $16$, une solution incomplète de taille $23$ (1 nombre manquant) suivi d'un mur $\tau = 24$.

La branche « 16A »

Insertions triviales des nombres 17 à 23

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 17 à 23.

Création de l'ensemble D

La collection possède un mur qui vaut précisément le nombre courant $\tau = n = 24$. On ne peut donc pas insérer plus de nombres en l'état. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble D. Se faisant, on obtient $WS(3) = 23$.

La branche « 16C »

Alternative pour le nombre 17

Pour 17, il est possible de l'insérer dans l'ensemble A et dans l'ensemble C. Pour savoir lequel il faut choisir, on va observer les conséquences qu'engendrent ces deux options via le processus de déduction.

  • 17 dans A (cet optimum global est la racine de 0 optimum global à $k = 4$ ensembles)
  • 17 dans C (cet optimum global est la racine de 21 693 optima globaux (soit ~72.48% des optima globaux) à $k = 4$ ensembles)

Observations :

  • Choisir A : on obtient une solution complète de taille $23$ suivi d'un mur $\tau = 24$.
  • Choisir C : on obtient une solution complète de taille $23$ suivi d'un mur $\tau = 24$.

La branche « 16C-17A »

Insertions triviales des nombres 18 à 23

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 18 à 23.

Création de l'ensemble D

La collection possède un mur qui vaut précisément le nombre courant $\tau = n = 24$. On ne peut donc pas insérer plus de nombres en l'état. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble D. Se faisant, on obtient $WS(3) = 23$.

La branche « 16C-17C »

Insertions triviales des nombres 18 à 23

Le processus de déduction nous permet d'obtenir une solution complète en insérant les nombres de 18 à 23.

Création de l'ensemble D

La collection possède un mur qui vaut précisément le nombre courant $\tau = n = 24$. On ne peut donc pas insérer plus de nombres en l'état. On peut alors appliquer la règle de l'« ajout d'un nouvel ensemble à la collection » : on crée l'ensemble D. Se faisant, on obtient $WS(3) = 23$.

Comparaison des solutions k=3

  • (8 238)
    Za 21=17+4 / Zb 20=12+8 / Zc 11=11+0
    Na 38=7+19+3+9 / Nb 44=7+17+9+11 / Nc 38=9+18+9+2
    Na+ 15=6+9 / Nb+ 21=10+11 / Nc+ 15=14+1
    Na+ 1:1:2:2:1:2:1:4:1 / Nb+ 7:9:1:1:1:1:1 / Nc+ 12:1:2
    (0)
    Za 21=17+4 / Zb 20=12+8 / Zc 11=11+0
    Na 39=7+19+4+9 / Nb 44=7+17+9+11 / Nc 38=9+18+9+2
    Na+ 16=7+9 / Nb+ 21=10+11 / Nc+ 15=14+1
    Na+ 3:1:1:1:1:2:1:5:1 / Nb+ 7:9:1:1:1:1:1 / Nc+ 13:1:1
    (21 693)
    Za 21=13+8 / Zb 20=12+8 / Zc 11=11+0
    Na 33=6+14+5+8 / Nb 44=7+17+9+11 / Nc 38=10+19+9+0
    Na+ 10=4+6 / Nb+ 21=10+11 / Nc+ 15=15+0
    Na+ 1:1:1:3:1:2:1 / Nb+ 7:9:1:1:1:1:1 / Nc+ 15

Tentative k=5