Dans les problèmes de recuit simulé, en gros il y a deux étapes
- trouver une configuration initiale convenable
- trouver des modifications simples qui permettent de passer d'une configuration admissible à une autre proche de telle manière que le calcul de la différence d'énergie soit simple.
Ici, ce qui rend les choses difficiles, c'est qu'il y a beaucoup de contraintes, à telle point que de manière générale, il n'est pas possible d'affirmer qu'une solution existe toujours.
Du coup, même la première étape n'est pas évidente.
Dans ces cas là, ce qu'on peut faire, c'est, dans une première phase, libérer une contrainte dure (ici par exemple la fourchette) en fabriquant un hamiltonien qui pénalise très fortement les sorties de la fourchette.
Dans cette première phase, le coût total on s'en fout.
Puis, une fois qu'une solution admissible a été trouvée, on peut passer au point deux, cette fois avec le vrai hamiltonien.
# Découper les difficultés
Posté par mac_is_mac (site web personnel) . En réponse au message URGENT : Recuit Simulé : Affectation des sites à des opérateurs de téléphonie mobile. Évalué à 2.
- trouver une configuration initiale convenable
- trouver des modifications simples qui permettent de passer d'une configuration admissible à une autre proche de telle manière que le calcul de la différence d'énergie soit simple.
Ici, ce qui rend les choses difficiles, c'est qu'il y a beaucoup de contraintes, à telle point que de manière générale, il n'est pas possible d'affirmer qu'une solution existe toujours.
Du coup, même la première étape n'est pas évidente.
Dans ces cas là, ce qu'on peut faire, c'est, dans une première phase, libérer une contrainte dure (ici par exemple la fourchette) en fabriquant un hamiltonien qui pénalise très fortement les sorties de la fourchette.
Dans cette première phase, le coût total on s'en fout.
Puis, une fois qu'une solution admissible a été trouvée, on peut passer au point deux, cette fois avec le vrai hamiltonien.