You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

113 lines
4.1KB

  1. \section{Chapitre 6: Stratégies de recherche}
  2. \label{sec:ch6}
  3. Robustesse d'un solveur: capacité à résoudre une large variété de problèmes
  4. \subsection{Heuristiques de choix de variables}
  5. \label{sec:heuristiquevariables}
  6. Instancier les variables qui ont le plus d'impact en premier
  7. Types d'heuristiques
  8. \begin{itemize}
  9. \item Ordre statique: on fixe l'ordre d'instantiation manuellement
  10. \item Plus petit domaine: plus grande probabilité d'avoir la bonne valeur
  11. \item Variable la plus contrainte: plus grand degré, a le plus d'impact sur la solution
  12. \item Choix structurels: obtenir un problème plus simple à résoudre
  13. \item Combinaisons des heuristiques précédents
  14. \end{itemize}
  15. Techniques additionnelles
  16. \begin{itemize}
  17. \item Stochastique: Utilise un générateur de nombres pseudo-aléatoires pour sélectionner les branchements sur les variables
  18. \item Apprentissage: Ces heuristiques s'adaptent au problème avec une forme d'apprentissage qui met du poids sur les variables. Plongées dans l'arbre de recherche
  19. \end{itemize}
  20. \subsection{Heuristiques de choix de valeurs}
  21. \label{sec:choixvaleurs}
  22. \begin{itemize}
  23. \item Le choix dépend souvent d'une connaissance du problème. On peut trier les valeurs du premier choix au dernier choix.
  24. \item Déviation: solveur branche sur une valeur qui n'est pas le premier choix
  25. \end{itemize}
  26. \subsection{Fouille LDS}
  27. \label{sec:fouillelds}
  28. \begin{algorithm}[H]
  29. \DontPrintSemicolon
  30. \Deb{
  31. $Candidats \leftarrow \lbrace X_i \mid |dom(X_i)| >1 \rbrace$ \;
  32. \Si{$Candidats = \emptyset$}{
  33. \Si{$dom(X_1),\ldots,dom(X_n)$ sat. contraintes}{
  34. \Retour{$dom(X_1),\ldots,dom(X_n)$}
  35. }
  36. \Sinon{
  37. \Retour{$\emptyset$}
  38. }
  39. }
  40. Choisir une variable $X_i \in Candidats$ \;
  41. \Si{$nbDeviations < |Candidats|$}{
  42. $Solution \leftarrow LDS(dom(X_1),\ldots,dom(X_{i-1}),\lbrace v_1 \rbrace, \ldots, dom(X_n)4,nbDeviations)$ \;
  43. \Si{$Solution \neq \emptyset$}{\Retour{$Solution$}}
  44. }
  45. \Si{$nbDeviations>0$}{
  46. $Solution \leftarrow LDS(dom(X_1),\ldots,dom(X_{i-1}),\lbrace v_2 \rbrace, \ldots, dom(X_n),nbDeviations)$ \;
  47. \Si{$Solution \neq \emptyset$}{\Retour{$Solution$}}
  48. }
  49. \Retour{$\emptyset$} \;
  50. }
  51. \caption{LDS($dom(X_1),\ldots,dom(X_n)$,nbDeviations)}
  52. \end{algorithm}
  53. \subsection{Redémarrage}
  54. \label{sec:redemarrage}
  55. \begin{itemize}
  56. \item Heuristique stochastique: après un certain temps ou un certain nombre de retours arrières, on redémarre la recherche
  57. \item Possibilité de visiter deux fois le même noeud: risque à prendre, inefficace, mais acceptable
  58. \item Si on ne fait pas attention: possibilité de ne jamais visiter une branche de l'arbre, inacceptable
  59. \end{itemize}
  60. Stratégies de redémarrage:
  61. Garantissent que la totalité de l'arbre est visité
  62. \begin{itemize}
  63. \item Géométrique: $1, r, r^2, r^3, ... | r>1$
  64. \item Luby: $1,1,2,1,1,2,4,1,1,2,1,1,2,4,8, \ldots$ nombre de retours arrières est à un facteur logarithmique de la séquence optimale
  65. \end{itemize}
  66. \subsection{Nogoods}
  67. \label{sec:nogoods}
  68. \begin{itemize}
  69. \item Cette stratégie réduit la possibilité de revisiter des noeuds
  70. \item Contrainte ajoutée au modèle, prévient un second retour arrière pour les mêmes raisons
  71. \item Un noeud est identifié par un ensemble de contraintes de branchement $p(n)= \lbrace b1, \ldots, b_j\rbrace$
  72. \item Soit $n$ le noeud où le retour arrière est déclenché sans avoir visité ses descendants. Au moins une contrainte a été violée.
  73. \begin{align}
  74. J(n) = \lbrace b_i \in p(n) \mid portée(bi) \cap portée(C) \neq \emptyset \rbrace
  75. \end{align}
  76. \item Si un retour arrière se produit sur chacun des enfants $c_1, \ldots, c_k$ de $n$
  77. \begin{align}
  78. J(n) = p(n) \bigcup_{i=1}^k J(c_i)
  79. \end{align}
  80. \item Favoriser l'arité du nogood la plus petite
  81. \item Gestion: Effacer ...
  82. \begin{itemize}
  83. \item les plus vieux,
  84. \item les moins appelés,
  85. \item ceux avec arité la plus grande
  86. \end{itemize}
  87. \end{itemize}
  88. Les solveurs SAT utilisent des heuristiques d'apprentissage, le redémarrage et des nogoods
  89. %%% Local Variables:
  90. %%% mode: latex
  91. %%% TeX-master: "notes_de_cours"
  92. %%% End: