Probleme de dénombrement

[Patastronch]

Bonjour,

Tout d'abord quelques définitions pour comprendre mon problème :

Notre espace est discrétisé : M lignes, K colones.
toutes les courbes démarrent de (1,M) et finissent en (K,1) et sont toutes décroissante ( à partir d'une case (x,y) on peut tracer soit en (x+1,y) (x+1,y-1) ou (x,y-1) ).

On dit qu'une courbe domine une autre courbe ssi elle est plus grande que la deuxième pour toutes valeurs de 1 a K.

Ma question :

Quel est le nombre de courbes non dominées maximum que l'on peut avoir dans un espace de taille MxK.

Exemple :



Si on a les 4 courbes suivante (rouge, verte bleu et jaune) les non-dominées sont les courbes jaune et bleu, car la jaune domine la rouge et la verte, et la bleu domine la rouge et la verte mais la jaune ne domine pas la bleu de meme que la bleu ne domine pas la jaune.

Si on a les 2 courbes suivante (vert et rouge) les non dominées sont vert et rouge.

Si on a les 2 courbes suivantes (rouge et jaune) la non dominée est la jaune.

Voila je sais pas si j'ai été assez clair, mais n'hésitez pas a me poser des questions si c'est pas le cas.

Merci encore.

P.S: Sur l'image de l'exemple s'il y a plusieurs couleur sur une case c'est que plusieurs courbes passent par cette case.

[Patastronch]

Je précise que je n'ai pas la réponse, je cherche depuis pas mal de temps la dessus déjà.

[Flodelarab]

pitêtre, je n'ai pas compris la question mais je crois qu'une seule courbe est non dominée (celle qui reste horizontale jusqu'à K,M et qui plonge vers K,1).

Car meme tes courbes bleue et jaune sont dominée par celle que g décrite.
Dans le cas général, ya pas d'autre reponse.

non ?

[Patastronch]

Rien que dans mon exemple y en a 2, donc ta réponse est fausse.

En fait j'ai demandé le nombre maximum de non dominées possible dans un espace, pas le nombre de dominées quand y a toutes les courbes possible dans cet espace.

[scelerat]

Je pense que la question est "Combien peut-on choisir au maximum de courbes distinctes telles qu'elles soient toutes non-dominees au sein de cet ensemble retenu ?"
J'aurais tendance a faire une recurrence sur M, peut-etre montrer que le nombre est constant quel que soit M > K, puis voir combien il faut ecarter de courbes quand on reduit M de 1... Pour le moment, je cherche.

[Patastronch]

Oui tu as merveilleusement bien reformulé la question, j'avoue que je suis pas tres clair.

[scelerat]

Intuitivement, je dirais que le nombre est min (M-1, K-1) est que la solution optimale est obtenue en prenant des courbes en marches d'escalier : {2,2,...2,1}, {3,3,...,3,1,1}, {4,4,...4,1,1,1}, etc.
Mais ca reste une intuition non demontree.

[Patastronch]

J'avais reussi a trouver une configuration qui métait en oeuvre un nombre polynomiale (pseudo polynome du second degré en fonction de M et de K) sans prendre en compte le "mouvement diagonale" pour une courbe. Mon polynome du second degré était donc un minimum de ce que l'on peut faire.

En fait j'était partie en dénombrant le nombre de courbe "entrelacées" entre elles en divisant en 2 partie symétrique le probleme (je faisais l'hypothese que dans la configuration saturée on avait une symétrie centrale) et en m'arrangeant pour que chaque courbe soit la plus grande pour au moins une valeur dans la premiere partie de l'espace,et donc par symétrie la plus petite pour une autre valeur dans la seconde partie de l'espace. Il suffisait de trouver le nombre maximum de courbes pouvant etre maximal en un point dans la premiere partie de l'espace.

En fait je ne cherche pas le nombre exact de courbes mais je cherche à :

Soit majorer par un pseudo polynome en M et K le nombre de courbes.
Soit minorer par une fonction combinatoire en M et K le nombre de courbes.

En tous cas je te remerci de te pencher sur la question :)

Je dois avouer que la je bloque totalement au point ou je ne vois meme plus comment prendre le probleme.

[aviateurpilot]

1erment, combien de courbes peut-on avoir dans ce espace?

[Patastronch]

Le calcul n'est pas compliqué pour dénombrer le nombre de courbe possible.

Chaque courbe doit "descendre" M fois et "aller a droite" K fois.

On a donc :

Soit M bas et K droite dans n'importe quel ordre
Soit M-1 bas et K-1 droite et un diagonal dans n'importe quel ordre.
...
Soit M-N bas et K-N droite et N diagonal dans n'importe quel ordre
...
Soit max(K,M)-min(K,M) bas (ou droite selon le min) et min(K,M) diagonal.

Le calcul j'ai la flem dele faire mais c'est clairement pas polynomial, ce qui permet donc pas de majorer polynomialement.

Apres sit 'avais une autre idée en tete hésite pas a m'en faire part :)

[Flodelarab]

1erment, combien de courbes peut-on avoir dans ce espace?

A vue de nez, je dirais:
K+M mouvements maximum et on place K mouvements parmi K+M et M mouvements parmi K+M.
Soit:

[Patastronch]

A vue de nez, je dirais:
K+M mouvements maximum et on place K mouvements parmi K+M et M mouvements parmi K+M.
Soit:

Quand tu as placé tes K mouvements parmis tes K+M innutile de placer les M restant qui sont deja placé, ou alors tu place les M restant parmis M possibilité ce qui ne sert a rien comme calcul.

Mais comme tu le dis si bien, pour le premier cas on est deja dans un calcul non polynomial, donc si j'y ajoutes les autres cas ca ne fait qu'empirer.

[aviateurpilot]

les courbes qu'on peut avoir dans ce espace est:

[Patastronch]

les courbes qu'on peut avoir dans ce espace est:

C'est pas plutot :



?

[aviateurpilot]

je voulais dire

[Flodelarab]

innutile de placer les M restant qui sont deja placé

FAUX!
Tu n'est pas obligé d'avoir M+K mouvement!

Ceci dit, mon calcul est incomplet. Interdit de choisir un M après un trou (sans K ni M)

[Patastronch]

FAUX!
Tu n'est pas obligé d'avoir M+K mouvement!

Dans ce cas t as pas forcément K mouvements en bas non plus. Et dans ce que tu as écrit tu place bien au total K+M mouvement parmis K+M.

De toute facon le nombre de courbes a été trouvé par AviateurPilot, mais ca règle pas mon problème puisque ce nombre n'est pas une fonction polynomiale de M et de K (ou une fonction majorée par un polynome de M et de K)

[aviateurpilot]

FAUX!
Tu n'est pas obligé d'avoir M+K mouvement!

mais moi j'ai fait
mouvement (à droite)
mouvement (en bas)
en diagonal

donc
et ma formule final est:

De toute facon le nombre de courbes a été trouvé par AviateurPilot, mais ca règle pas mon problème puisque ce nombre n'est pas une fonction polynomiale de M et de K (ou une fonction majorée par un polynome de M et de K)

pour quoi tu cherche une fonction polynominal

[Patastronch]

pour quoi tu cherche une fonction polynominal

Pour prouver que mon algo est Polynomial (ou NP-COMPLET le cas échéant). Pour ca il faut que je sache si je peux majorer le pire cas (ici majorer le cardinal de l'ensemble des nons-dominés) par un polynome ou pas.

[scelerat]

Pour prouver que mon algo est Polynomial (ou NP-COMPLET le cas échéant). Pour ca il faut que je sache si je peux majorer le pire cas (ici majorer le cardinal de l'ensemble des nons-dominés) par un polynome ou pas.

Je suis quasiment sur que le nombre est min(M-1, K-1) comme indique precedemment. Plutot que de recenser les suites decroissantes de K entiers de [1, M], faites comme moi, M=2, M=3, et vous serez convaincus qu'on ne pas rajouter plus d'une fonction a chaque fois qu'on incremente M (meme si on peut avoir plusieurs choix pour celle-ci). D'autre part, pour croiser une autre fonction, il faut descendre d'au moins une marche pendant qu'on etend l'autre de 1 horizontalement. On sent qu'augmenter seulement le plus grand des deux K ou M ne donne pas de possibilites de croisement supplementaires. Par consequent, on aurait N(M,K) = N(min(M,K),min(M,K)).

J'ai essaye de formaliser tout ca en cherchant une relation entre des elements des c courbes d'une solution optimale sous la forme yi0 > yi1 > yi2 > yi3 >...>yic, ce qui montrerait qu'il nous faut au moins c+1 niveaux distincts, donc que c < M. J'y suis presque, mais il me manque un chouia (en gros, j'ai bien c relations 2 a 2, il me manque la maniere formelle d'ordonner mes courbes pour pouvoir les combiner).