Calcul d'approximations intérieures pour la résolution de Max-NCSP

摘要: Abstract Cet article pr´esente un algorithme de calcul desolutions garanties pour des probl`emes num´eriquesMaxCSP. Les auteurs proposent une approchequi offre exploration compl`ete et garantie del’espace recherche identifie l’ensemble dessous-espaces ´eventuellement disjoints qui satisfontle plus grand nombre contraintes num´eriques duCSP. L’impl´ementation cet fournit uneapproximation int´erieure ces sous-ensembles pourune taille minimale pav´e donn´ee . L’approche reposesur m´ethodes propagation classiques sur lesintervalles (AC-3) processus d’extension parl’int´erieur en n dimensions. Une hybridation avec desm´ethodes locales recherche, ´etendues aux intervalles,est propos´ee test´ee r´esultats, portant desprobl`emes jouets montrent l’apport par rapport `aun na¨if mais ne mettent pas lumi`erel’´evidence la contribution recherchelocale. 1 Introduction approches compl`etes r´esolution CSPnum´eriques permettent s’attaquer `a probl`emesr´eput´es difficiles dans nombreux domaines(conception pr´eliminaire, conformation mol´ec ulaire,probl`emes d’automatique, robotique, ou desynth`ese d’images, etc.). Ces d´eterminentun ensemble pav´es approximant l’ext´erieurl’ensemble r´ee l solutions assurant qu’aucunesolution lle n’est perdue lors du processusde (propri´et´e compl´etude). Or denombreuses applications n´ecessitent le suˆres, c’est-`a-dire telles que tout point despav´es r´esultats soit solution syst`emede contraintes. De tels ont ´et´e r´esoluspar diff´erentes [24, 15, 5] dites calculd’approximation i-consistency [10].Cependant, aucune deux approximations(int´erieure ext´erieure) directement adapt´eeau cadre Max-NCSP cherche `amaximiser satisfaites unCSP les domaines continus (ici, on n’´etablit dehi´erarchie entre pr´ef´erences surles domaines). Ce travail est motiv´e fait qu’ilest g´en´eralement difficile d´eterminer l’avance lanature d’un mod`ele num´erique (i.e. sous-contraint ousur-contraint) avant sa r´esolution, donc pr´evoirla nature techniques employer r´esoudre.Nous proposons premiersr´esultats issus calculd’approximations int´erieures probl`emessur sous-contraints. d´etermineun satisfont maximumde CSP. La technique r´esolutionconsiste entrelacer ´etapes decontraintes d’extensions int´erieuresbas´ees choix repr´esentatif pav´e.Cette s´election sera effectu´ee techniquesdiff´erentes, premi`ere ´etant simple tirage dumilieu (midPoint), deuxi`eme faisant appel`a m´ethode Recherche Locale (LS) ´etendueau domaine continu aider lemeilleur possible pav´e. A` ce sujet,nous d´efinissons formel l’extension aucontinu locale. Nous decomparer l’algorithme dit midPointavec bissection/´evaluation,puis comparer obtenues parl’approche locale continue. A la99