Produit scalaire minimal

[ekryyn]

Bonjour à tous,
J'essaie de démontrer le fait suivant :

Imaginons 2 vecteurs de dimension N, v1(x1, x2, ..., xN) et v2(y1, y2, ..., yN), où les coordonnées sont des entiers relatifs.
Le produit scalaire de ces deux vecteurs peut être noté comme suit :
p = x1y1 + x2y2 + ... + yNyN

Imaginons maintenant que je puisse ordonner à ma guise les coordonnées de chacun des vecteurs.

Je cherche une combinaison des coordonnées de v1 et v2 telle que p soit le plus petit possible.
La solution que j'ai trouvé consiste à ordonner les coordonnées de v1 par ordre croissant, et les coordonnées de v2 par ordre décroissant (ou vice-versa). Cela tient de l'intuition, et ça semble fonctionner.

Présenté autrement, je multiplie la plus basse coordonnée de v1 par la plus haute coordonnée de v2. Ceci fait, je multiplie la coordonnée la plus basse restante de v1 par la plus haute restante de v2. Et ainsi de suite.

La combinaison de coordonnées vérifiant :
x1 y2 > ... > yN
est celle qui produit le plus petit produit scalaire possible.

Tout cela peut paraître étrange, et vient en fait du challenge google jam suivant :
https://code.google.com/codejam/contest/dashboard?c=32016#s=p0

J'ai écrit un petit programme en python qui fait ce que je viens de décrire, et cela fonctionne pour les 2 jeux de tests fournis sur le challenge.

Seulement je suis en quête d'une démonstration du pourquoi du comment. Et là, je sèche. Il faut avouer que je n'aie pas un niveau en mathématique exceptionnel, enfin cela m'intéresse.

Quelqu'un sait s'il est possible de démontrer ça ? En espérant que ce soit à ma portée :we:

Merci d'avance

[fatal_error]

Hello

je pense avoir une démonstration visuelle.

Si on se prend deux vecteurs:
[a,b], [x,y]

On cherche le plus petit des produits scalaires:
ax+by
ou
ay+bx
ax+by a(x-y) (a-b)(x-y)0 et (x-y) a>b et x0 ==> ay
Donc effectivement, si un vecteur est trié ascendant, l'autre doit l'etre descendant pour minimiser le produit scalaire.

Maintenant si on prend deux vecteurs quelconques:
v1=[a,b,c,d,...]
v2=[A,B,C,D,...]
on peut intervertir les lignes de manière à trier v1 ascendant
ex:

Code: Tout sélectionner

v1 v2     v1  v2
0  5      0   5
[COLOR=Green]4  6[/COLOR]   => [COLOR=Red]2   7[/COLOR]
[COLOR=Red]2  7[/COLOR]      [COLOR=Green]4   6[/COLOR]

Si on regarde les deux premières composantes ca veut dire que les autres lignes sont fixes. Du coup on peut intervertir les deux premières composantes et comme v1 est trié ascendant, v2 doit etre descendant.
Maintenant, on décale la fenetre de comparaison et on regarde les lignes 2 et 3...
on trie..
etc....

Au final, on fait simplement un sort sur v2 qui va se retrouver descendant.

[ekryyn]

Merci pour cette démonstration.
Je comprends parfaitement la première partie.
J'ai par contre du mal à comprendre la généralisation sur les vecteurs à plus de 2 coordonnées.
En gros, il s'agit de s'attacher à obtenir un minimum local, le produit des deux lignes considérées.
Par récurrence, la contrainte d'ordre se répercute sur les ligne suivantes a < b & A > B puis b < c & B > C , etc...
J'ai du mal à voir pourquoi la somme totale est la plus petites possible si le produit chaque ligne, prises 2 par 2, est minimal. Ce ne sont que des minimums locaux, j'arrive pas à élargir le raisonnement

[fatal_error]

ben si tu considères que le vecteur v2.
Mettons tu as 1 5 9 5 2
(je rappele v1 est ascendant)
1 5 9 5 2
5 1 9 5 2 (colonnes 1-2)
5 9 1 5 2 (colonnes 2-3)
5 9 5 1 2 (colonnes 3-4)
5 9 5 2 1 (colonnes 4-1)
9 5 5 2 1 (colonnes 1-2)

c'est juste un sort quoi. pour tout éléments adjacents x,y de v2, il faut que que x>y.
Si jamais tu as deux elements adjacents, tu les intervertis.
Tu es sur de t'arreter sur tous les élements triés dans l'ordre décroissants.

[ekryyn]

D'accord je vois !
Merci beaucoup pour ton aide !