code algorithme d'arrangements

[Roger788]

" Une compréhension naturelle serait "nombre dispersé: tout nombre qui est présent dans plus qu'une colonne". oui

voici un exemple avec des nombres "bidon"

vous me direz.
-----

[ansset]

donc tu peux pondre une formule qui compte et pénalise les dispersés.
puis à nb égal , donner un + aux arrangements qui donnent le plus de "grands" groupes de chiffres.
est ce l'idée ?

[Roger788]

oui tout à fait.

par contre je ne sais pas utiliser le Pascal...(je connais le prénom....)

merci

[ansset]

la question reste alors alors quel est le poids que tu donnes à un dispersé par rapport à un bel arrangement.
par exemple : si je rassemble six N° 11 dans un colonne et qu'il en manque un , est ce aussi pénalisant que de séparer trois chiffres 7 en deux morceaux.
il faut donc ( à mon avis ) deux coeffs :
-l'un qui donne des - en fct des "isolés"
-l'autre qui donne des + en fct de la "force" d'un arrangement sur une colonne ( à définir )

je peux essayer de proposer qcq chose si tu veux !
Cdt

[invite73192618]

par contre je ne sais pas utiliser le Pascal...

Peu importe tant que la réponse est claire et complète. Regardes ton exemple en 31: crois-tu clair que la solution 2 est préférable à la solution 4? (ou l'inverse si c'est l'inverse que tu voulais dire) Est-ce que tes lecteurs savent quoi faire si, par exemple, ils doivent choisir entre (3 dispersés et 2 colonnes parfaites) versus (250 dispersés et 3 colonnes parfaites)? [edit: croisement...]

" Une compréhension naturelle serait "nombre dispersé: tout nombre qui est présent dans plus qu'une colonne". oui

Je crois que le problème que tu es en train de définir sera NP-complet. Dans ce cas, il n'existe aucun moyen connu de le résoudre en temps raisonnable et en toute généralité. Les trois choses qu'on peut faire sont:

1) réduire la taille du problème en éliminant les cas triviaux. Par exemple: on regarde si des nombres se retrouvent à deux places dans certaines lignes, ou une seule fois dans tout le tableau. Dans les deux cas on sait tout de suite que, quoi qu'on fasse, ces nombres seront soit des dispersés soit des non dispersés (respectivement). On les note pour plus tard, puis on remplace ces chiffres par des n/a. On enlève les lignes avec uniquement des n/a, ce qui éventuellement diminue la taille du tableau sur lequel on travaille, et on passe à la suite (on les rétablira plus tard, ainsi que les n/a, mais à ce stade c'est simplement une façon de dire "pas besoin d'explorer des permutations de ces éléments").

(en fait je devrais dire: éliminer les cas "impossibles" plutôt que "triviaux". Si tu trouves une démonstration non triviale que certains cas sont impossibles à résoudre, alors détecter ces cas est à ajouter à cette étape. Mais souvent il n'y a que des cas triviaux qui nous viennent en tête... sinon ils ne seraient pas triviaux )

2) choisir entre un algorithme parfait ou approché. Un algorithme parfait sera une recherche par force brute, qui donnera toujours le meilleur résultat mais éventuellement dans un temps trop long pour être réaliste. Un algorithme approché sera une méthode de Monte-Carlo (LeMulet en a donné un) dans lequel on essai des permutations au hasard, puis on conserve le résultat si et seulement si le résultat est meilleur qu'avant la permutation. Le résultat ne sera pas parfait mais il peut éventuellement être très très bon, sans nécessairement qu'on le sache à l'avance si le résultat sera bon ou pas.

3) ordonner la recherche en fonction des cas les plus probables. Pour cela il faut ajouter une information sur la densité de probabilité (si on en n'a pas, ou si seul le comportement "dans le pire des cas" nous intéresse, alors on ne peut rien faire), et en tirer des astuces qui vont améliorer le comportement probable du Monte-Carlo. Par exemple: si on stipule qu'il y a 70 chiffres et que ces chiffres sont équiprobables, alors on sait également la probabilité d'avoir des éléments répétés dans 2, 3, ...70 lignes différentes. Cela pourrait mener à des heuristiques telles que "permuter plus souvent parmi les nombres qui ont peu de répétition" ou "chercher plus souvent parmi les lignes qui ont peu de n/a". Certaines sont plus difficiles à voir. Par exemple LeMulet met du "recuit" dans son algorithme (un truc algorithmique pour éviter d'être bloqué dans un minima local), mais la raison profonde pourquoi cela marche est à chercher dans la distribution des nombres. Comme pour les autres heuristiques, le gain de temps "en moyenne" dépendra de la distribution de probabilité des nombres, et il pourra y avoir des cas bizarres où le résultat final sera pire que sans l'heuristique.

[bdom001]

Bonjour à tous,

Merci pour vos réponses (je ne connais pas ce langage de programmation..) je vous envoie l'image d'un exemple que j'ai fait (en rouge les 2 nombres "en erreur" dispersés) mais je n'arrive pas à faire mieux (avec seulement 15 lignes et des nombres allant uniquement à 50).

Bonne soirée.

Bonjour Roger788,
vous dites (message #5):

il y a 5 colonnes avec nombres (sans doublon en ligne) avec 30 lignes environ.

Alors qu'on voit bien que sur l'image (message #18), le nombre 28 est un doublon sur la troisième ligne ! ???

Cordialement