Result: LSVF: a New Search Heuristic to Reduce the Backtracking Calls for Solving Constraint Satisfaction Problem

De nombreux chercheurs en intelligence artificielle recherchent de nouveaux algorithmes pour réduire la quantité de mémoire/ temps consommée pour les recherches générales dans les problèmes de satisfaction des contraintes. Ces améliorations sont accomplies par l'utilisation d'heuristiques qui élaguent les branches de recherche d'arbres inutiles ou indiquent même le chemin pour atteindre la solution (optimale) plus rapidement que la version aveugle de la recherche. De nombreuses heuristiques ont été proposées dans la littérature, comme la valeur la moins contraignante (LCV). Dans cet article, nous proposons une nouvelle heuristique de recherche de prétraitement pour réduire la quantité d'appels de retour en arrière, à savoir la valeur la moins suggérée d'abord : une solution chaque fois que la LCV ne peut pas mesurer uniquement combien une valeur est contrainte. Dans cet article, nous présentons un exemple pédagogique, ainsi que les résultats préliminaires.
Muchos investigadores en Inteligencia Artificial buscan nuevos algoritmos para reducir la cantidad de memoria/ tiempo consumido para búsquedas generales en Problemas de Satisfacción de Restricciones. Estas mejoras se logran mediante el uso de heurísticas que recortan ramas de búsqueda de árboles inútiles o incluso indican el camino para llegar a la solución (óptima) más rápido que la versión ciega de la búsqueda. En la literatura se propusieron muchas heurísticas, como el Valor Mínimo de Restricción (LCV). En este documento proponemos una nueva heurística de búsqueda de preprocesamiento para reducir la cantidad de llamadas de retroceso, a saber, el Valor Mínimo Sugerido Primero: una solución siempre que el LCV no pueda medir cuánto se restringe un valor. En este documento, presentamos un ejemplo pedagógico, así como los resultados preliminares.
Many researchers in Artificial Intelligence seek for new algorithms to reduce the amount of memory/ time consumed for general searches in Constraint Satisfaction Problems.These improvements are accomplished by the use of heuristics which either prune useless tree search branches or even indicate the path to reach the (optimal) solution faster than the blind version of the search.Many heuristics were proposed in the literature, like the Least Constraining Value (LCV).In this paper we propose a new pre-processing search heuristic to reduce the amount of backtracking calls, namely the Least Suggested Value First: a solution whenever the LCV solely cannot measure how much a value is constrained.In this paper, we present a pedagogical example, as well as the preliminary results.
يبحث العديد من الباحثين في الذكاء الاصطناعي عن خوارزميات جديدة لتقليل مقدار الذاكرة/ الوقت المستهلك لعمليات البحث العامة في مشاكل الرضا عن القيود. يتم تحقيق هذه التحسينات من خلال استخدام الاستدلالات التي إما تقليم فروع البحث عن الأشجار عديمة الفائدة أو حتى الإشارة إلى المسار للوصول إلى الحل (الأمثل) بشكل أسرع من النسخة العمياء من البحث. تم اقتراح العديد من الاستدلالات في الأدبيات، مثل قيمة الحد الأدنى من القيود (LCV). في هذه الورقة، نقترح استدلالًا جديدًا للبحث قبل المعالجة لتقليل كمية مكالمات التتبع العكسي، وهي القيمة الأقل المقترحة أولاً: حل عندما لا تستطيع قيمة الحد الأدنى من القيمة فقط. في هذه الورقة، نقدم مثالًا تربويًا، بالإضافة إلى النتائج الأولية.