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.

128 lines
4.4KB

  1. \section{Chapitre 5: Structures traitables}
  2. \label{sec:ch5}
  3. \textbf{Structure traitable}: propriétés d'un problème qui garantissent une résolution en temps polynomial.
  4. \paragraph{Éviter un retour arrière}
  5. \begin{itemize}
  6. \item Heuristique qui ne fait que de bons choix
  7. \item Filtrage assez fort pour éliminer tous les mauvais choix
  8. \end{itemize}
  9. \subsection{Graphe de contraintes}
  10. \begin{itemize}
  11. \item Problème de satisfaction binaire
  12. \item Variable:noeud, Contrainte:arête
  13. \item \textbf{Arbre}: graphe acyclique
  14. \item \textbf{Arbre orienté}: possède une racine, chaque noeud a des enfants et un parent (sauf le noeud racine)
  15. \item Hauteur:
  16. \begin{itemize}
  17. \item feuille: 0
  18. \item autres: maximum des hauteurs des enfants + 1
  19. \end{itemize}
  20. \item Théorème: Arbre + Cohérence de domaine = Aucun retour arrière
  21. \item Sous-ensemble de contraintes forment un arbre = filtrage fort. Dans le cas des horaires de travail, la structure en arbre donne des horaires valides. Il reste à valider les autres contraintes.
  22. \end{itemize}
  23. Modèle avec deux séquences de variables:
  24. \begin{align}
  25. \mathtt{dom}(X_i) &= \lbrace 0,1 \rbrace \forall X_1, \ldots, X_n\\
  26. \mathtt{dom}(Y_i) &= \lbrace 0,1,2 \rbrace \forall Y_1, \ldots, Y_n\\
  27. X_i = 1 &\Leftrightarrow Y_i=1 et Y_i \leq Y_{i+1}
  28. \end{align}
  29. \paragraph{Hypergraphes de contraintes}
  30. Tuple $(V,E)$
  31. \begin{itemize}
  32. \item $V$: ensemble de noeuds: variables du problème
  33. \item $E$: ensemble d'hyperarêtes: portées des contraintes
  34. \item Décomposition de contrainte: arbre arithmétique
  35. \end{itemize}
  36. \begin{figure}[H]
  37. \centering
  38. \includegraphics[width=6cm]{ch5hypergraph}
  39. \caption{Hypergraphe}
  40. \label{fig:ch5hypergraphe}
  41. \end{figure}
  42. \subsection{Automate}
  43. Tuple $(\Sigma,Q,q_0,F,T)$
  44. \begin{itemize}
  45. \item $\Sigma$ : alphabet
  46. \item $Q$: Ensemble d'états
  47. \item $q_0$: État initial
  48. \item $F \subset Q$: États finaux
  49. \item $T \subset Q \times \Sigma \times Q$: Un ensemble de transitions
  50. \end{itemize}
  51. Une séquence de caractères $c_1, \ldots, c_n$ est reconnue par l'automate si $\exists q_1, \ldots, q_n t.q. (q_{i-1},c_i,q_i) \in T \wedge q_n \in F$.
  52. \paragraph{Contrainte \textsc{Regular}}
  53. \begin{itemize}
  54. \item Comprend une séquence de variable et un automate
  55. \item Un algorithme peut appliquer la cohérence de domaine
  56. \item Peut aussi être encodée avec une structure en forme d'arbre \ref{fig:arbreregular}
  57. \end{itemize}
  58. \paragraph{Encoder avec des contraintes}
  59. \begin{figure}[H]
  60. \centering
  61. \includegraphics[width=14cm]{tableau_regular}
  62. \caption{Structure d'arbre pour \textsc{Regular}}
  63. \label{fig:arbreregular}
  64. \end{figure}
  65. \begin{itemize}
  66. \item $dom(x_i) = \Sigma$
  67. \item $n+1$ variables $Q_0,\ldots,Q_n$
  68. \item \begin{itemize}
  69. \item $dom(Q_0)=\lbrace q_o \rbrace$
  70. \item $dom(Q_i)=Q, 0<i<n$
  71. \item $dom(Q_n)=F$
  72. \item $\textsc{Tableau}(Q_{i-1},X_i,Q_i) \in T$
  73. \end{itemize}
  74. \end{itemize}
  75. \paragraph{Ordre lexicographique}
  76. $X_1,\ldots,X_n$ est lexicographiquement plus petite ($\preceq$) que $Y_1,\ldots,Y_n$ si $\exists P t.q. X_P < Y_P \wedge X_i=Y_i \mid i < P$.
  77. La contrainte lexicographique s'écrit
  78. \begin{align}
  79. C(X_i,Y_i,P) \Leftrightarrow (i < P \Rightarrow X_i = Y_i) \wedge (i=O \Rightarrow X_i < Y_i) \\
  80. i \leq P \Rightarrow X_i \leq Y_i
  81. \end{align}
  82. \subsection{Largeur d'arbre}
  83. \textbf{Largeur d'arbre}: permet de dire à quel point une structure est similaire à un arbre. Lorsque la largeur est bornée par une constante, le problème peut être résolu en temps polynomial.
  84. \textbf{Décomposition en arbre}: graphe de contraintes $G \rightarrow $ arbre $T$ de la façon suivante: Si un noeud dans G se trouve à deux endroits dans T, il doit également se trouver sur tout le chemin reliant un endroit à l’autre. Minimiser le nombre de noeuds de $G$ par noeud de $T$.
  85. \textbf{Largeur d'arbre}: Cardinalité du plus grand ensemble - 1
  86. \paragraph{Largeur d'arbre bornée par $k$}
  87. Chaque noeud devient un problème de résolution de contraintes. Une contrainte \textsc{Tableau} par arête de $T$ avec une colonne par noeud contenant les tuples de solution valides. On garde les lignes compatibles.
  88. Cardinalité du plus grand domaine bornée par $d$: La complexité d'un sous-problème est $\mathcal{O}(d^{k+1})$. La contrainte tableau a au plus $d^{k+2}$ entrées. L'arbre aura au plus $n$ noeuds. Le problème est résolu en $\mathcal{O}(n)$
  89. %%% Local Variables:
  90. %%% mode: latex
  91. %%% TeX-master: "notes_de_cours"
  92. %%% End: