Substitution de variable dans la correspondance de modèle?

Je développe un moteur d'inférence, ce qui signifie que j'ai un certain nombre de "faits" qui sont fondamentalement la représentation du monde à un certain moment. Avec les faits (qui sont généralement seulement deux, l'état de départ et l'état d'objectif), j'ai beaucoup de règles (pourrait littéralement être des centaines pour certains problèmes). Le but du moteur d'inférence est, étant donné un état de départ et un ensemble de règles, de trouver le chemin le plus court vers l'un des états de but acceptables. Cela peut être fait avec plusieurs algorithmes comme DFS, BFS ou A *. La structure de base du programme est:Substitution de variable dans la correspondance de modèle?

 
fact factname 
    attribute1 = "value"; 
    attribute2 = [ 1, 2, 3]; 
    attribute3 = 4; 
    attribute4 = 7; 
    ... 
endFact 

rule ruleOne 
    equalsto(attribute, "value") or 
    greaterthan(attribute, 5) 
    > 
    remove(attribute); 
endRule 

rule ruleTwo 
    isprimeinteger(attribute) 
    > 
    add(attribute, 1) 
endRule

Dans la règle, le LHS (la partie avant la>) correspond chaque attribut dans le fait factname qui est égale à la « valeur ». Dans ce cas, c'est seulement un, mais il peut y en avoir beaucoup. Cela signifie que je dois résoudre des variables (souvent plusieurs fois pour le même fait), et que le LHS de la règle peut avoir plusieurs conditions entrées et/ou avec une analyse de priorité appropriée.

Le problème est: existe-t-il un moyen de résoudre ce type de variables efficacement? Ce que je fais maintenant, c'est d'itérer sur chaque attribut dans le fait et, en gros, je génère un assez grand arbre n-aire qui est même déséquilibré, et c'est TRÈS lent, surtout étant donné les conditions ci-dessus.

J'avais des pointeurs d'amour des papiers pour ce genre de motif correspondant à

Source

2009-06-11 user121155

Pouvez-vous expliquer votre problème un peu plus précis? J'ai du mal à le comprendre. Comment obtenez-vous les états qui peuvent être atteints d'un état donné? Que voulez-vous dire par variables? (Je ne vois que 'attribut', qui semble être une variable très spéciale Y en a-t-il d'autres?) Je ne peux pas détecter de correspondance (ou d'unification) et ne pas voir la pertinence du système expert des balises 'et' C++ '. Enfin, DFS ne semble pas être un excellent choix si vous voulez un chemin le plus court. – mweerden

Pas grande surprise ici, vous utilisez un algorithme O (N) où une table de hachage simple serait O (1). La table de hachage stocke pour chaque valeur d'attribut l'attribut correspondant.

Source

2009-06-11 08:48:50 MSalters

Non, une hashtable n'est pas utile dans ce cas. Peut-être que l'exemple ne donne pas l'idée, mais je peux avoir quelque chose comme ça dans le LHS: greaterthan (nom_variable, 2) et cela doit donner à variable_name * all * les attributs du fait dont la valeur est supérieure à deux (et beaucoup). – user121155

Mieux vaut mettre à jour l'exemple avec cette condition, et pendant que vous y êtes, ajoutez "isprimeinteger (attribut)" si cela est possible. Le problème de base est que toute solution efficace tirera parti de la structure pour éliminer la marche de liste O (N). Pas de structure, pas d'efficacité. – MSalters

J'ai remarqué que vous n'avez pas utilisé le mot unification n'importe où dans votre message. C'est ce qu'on appelle généralement l'algorithme que vous essayez de mettre en œuvre. Consultez l'article Wikipedia; Il y a quelques références au bas de la page ... dont une datant des années 70 quand l'espace et les cycles comptaient.

Source

2009-06-11 17:59:55 eduffy

eduffy l'a: c'est ce qu'on appelle l'unification. Prolog est un langage de programmation conçu pour faire exactement ce que vous essayez de faire, dans le cas général, et il utilise l'unification pour faire son sale boulot. Cependant, tous ceux qui ont essayé d'implémenter l'arithmétique en utilisant les axiomes de Peano dans Prolog peuvent vous dire que cela n'arrive pas toujours le plus rapidement possible. Il existe des langages de "programmation par contraintes" qui font à peu près la même chose mais en mettant l'accent sur la fourniture d'heuristiques pour aider le solveur à trouver des solutions optimales le plus rapidement possible. L'un d'eux est Comet.

Source

2009-06-12 15:45:19

Substitution de variable dans la correspondance de modèle?

Répondre

Questions connexes