MATLAB Résolution d'équations linéaires avec contraintes

[invite983ae819]

Bonjour,

J'essaie de résoudre avec MATLAB l'équation A*X=B (A et B connus, X inconnu) en imposant des contraintes à X:
1) X ne contient que des 0 et des 1
2) sum(X)=p

Merci de votre aide.
-----

[invite6c250b59]

C'est un problème k-SAT, donc NP-complet, donc t'es dans la schnoute...

Sauf si tu peux te contenter d'une solution approchée. Une méthode approchée en pseudo-code en supposant que A et B sont de taille a*b et a*c:

initialiser une matrice X de taille b*c avec, au hasard, k cases à 1 et le reste des cases à 0
calculer E=(A*X-B).^2
while tenveuxencore
    permuter n cases de X au hasard, avec n initialement tel que n=b*c
    recalculer E, et si E a augmenté annuler la permutation
    si les permutations ont été annulé 42 fois diminuer n
    si n=0 alors tenveuxplus
faireunjoligraphique(desresultats)

[invite983ae819]

Merci de ces renseignements.
Ce que vous proposez est de rechercher par tirage au sort les meilleures solutions. Ce ne peut pas être une solution globale.
D’où vient le 42 de la boucle?

[invite6c250b59]

Ce que vous proposez est de rechercher par tirage au sort les meilleures solutions.

Non, c'est un algorithme de recuit. Si tu affiches l'erreur en fonction du temps, tu verras une convergence.

D’où vient le 42 de la boucle?

C'est un facteur qui règle la vitesse de convergence (température). Plus ce facteur est grand, plus le programme passera du temps à essayer des permutations pour chaque n et donc plus il sera lent. A l'inverse plus le facteur est petit, plus le programme a de chances de rester pris dans un minimum local.

PS: j'ai écris k plutôt que p dans le pseudocode ci-dessus.

[A voir en vidéo sur Futura]

[invite983ae819]

Merci de toutes ces infos