Comment l'algorithme abstrait DPLL fonctionne en résolution SAT

Question

J'ai rencontré de nombreuses définitions de l'algorithme DPLL mais je n'ai pas pu les suivre. Ceux qui sont les plus proches de me mettre du sens pour moi sont ceux basés sur des systèmes de transition d'État avec des règles de transition telles que définies ici:

$ F $ est une formule CNF, $ c $ est une clause, et $ m $ est un modèle. Une description de celui-ci est la suivante:

Ici, une procédure DPLL sera modélisée par un système de transition: un ensemble d'états ainsi qu'une relation, appelée relation de transition, sur ces états. Les États seront désignés par (éventuellement en indice) $ s $ .... Un état est défaillant ou une paire $ m parallel f $, où $ f $ est un ensemble fini de clauses et $ m $ est une séquence de littéraux annotés.... nous n'entrerons pas dans une formalisation complète des littéraux annotés; Il suffit de savoir que certains littéraux $ l $ seront annotés comme étant des littéraux de décision; Ce fait sera indiqué ici en écrivant $ l ^ d $ (à peu près, les littéraux de décision sont ceux qui ont été ajoutés à $ M $ par la règle de décidé ci-dessous). La plupart du temps, la séquence $ m $ sera simplement considérée comme un ensemble de littéraux, dénotant une affectation, c'est-à-dire en ignorant à la fois les annotations et le fait que $ m $ est une séquence et non un ensemble.

je comprendre que un littéral est un atome ou sa négation, mais je ne comprends pas ce littéral annoté est, qui est une partie essentielle de la compréhension de ce qu'est un modèle $ m $ dans $ m parallèle f $. Je ne comprends pas non plus quelle est la décision des littéraux.

Deux exemples sont les suivants.

C'est autant que je peux me rassembler. Cette:

dollars

Est essentiellement une implémentation de ceci:

$$ m parallèle f $$

De plus, les virgules sont vraiment $ land $, comme dans:

dollars {2}) $$

Ainsi, chacun des blocs entre les virgules ou $ land $ est des clauses. À gauche se trouve une liste croissante de littéraux (atomes ou leur négation). Sur la droite sont les règles appliquées (comme Decide). Mais je ne comprends pas (a) comment les règles sont appliquées / pourquoi elles sont choisies au moment où elles sont choisies, (b) comment cela se traduit par un littéral annoté pour $ m $ à gauche, et (c) pourquoi Certains d'entre eux sont marqués en gras comme les littéraux de la «décision».

Le résultat final, de ma compréhension, est le modèle $ m $ (à gauche) qui satisfait la formule $ f $ à droite. Essentiellement, c'est une évaluation.

Je me demande si l'on pouvait clarifier comment fonctionne le premier exemple, comment les littéraux annotés sont ajoutés au modèle $ m $ à gauche.