Nous avons reçu un graphique avec les faits suivants: et nous sommes invités à définir une règle, Je suis vraiment perdu sur la façon de faire cela, j'ai essayé de tenter de traverser les nœuds et de vérifier si le prochain serait le premier, mais je ne peux pas sembler le faire fonctionner < / p> cycle (x) , qui détermine s'il y a Un cycle à partir du nœud x .
6 Réponses :
Cela fait longtemps que j'ai utilisé Prolog, mais peut-être que cette approche fonctionnera: a chemin est une séquence d'arêtes où chaque bord démarre sur le nœud du bord précédent terminé (par exemple, a -> B, B -> C, C -> D). Le chemin trivial est un seul bord, et des chemins plus complexes peuvent être formés en prenant un chemin existant et en ajoutant un bord à celui-ci. Un cycle est un chemin qui commence et se termine sur le même noeud. Pouvez-vous utiliser ces définitions pour créer vos règles PRolog?
Je n'ai pas utilisé PRolog depuis un certain temps, mais voici mon approche de ce problème.
Vous pouvez faire de la règle chemin (x, y) qui vérifie s'il existe le chemin de nœud x à y . Un chemin est un seul bord ou un bord menant à un chemin. Ayant ceci, il est facile de trouver le cycle à partir du noeud x - ce sera simplement le chemin (x, x) . Voici ma mise en œuvre (prise du sommet de ma tête et pas nécessairement correcte, mais donne l'idée):
Prendre bord (A, B). bord (b, c). bord (c, b). et la requête? - cycle (x). Profondeur Premier Prolog passera dans une boucle infinie et ne trouve pas le cycle.
L'idée d'Archie est un bon point de départ, mais elle créera une boucle infinie s'il trouve un autre cycle lors de la recherche du chemin.
Je n'ai pas non plus utilisé Prolog depuis des années, mais vous aurez besoin de quelque chose comme chemin (x, y, visité) , où vous gardez une trace des nœuds visités, empêchant les boucles sans fin. < / p>
J'ai utilisé de la profondeur d'une première recherche avec une liste de nœuds visitée si nous rencontrons tout nœud visité pendant la traversée, il renvoie true. J'ai testé avec de petites entrées, il semble fonctionner correctement.
cycle(X):- cycleh(X,[X]). cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).
Cela devrait faire le truc: Bien qu'il semble être une solution similaire à @ Gökhan URAS - Great Minds, pensez-vous. Ou quelque chose B ^) La logique de base est que vous avez un cycle si le nœud actuel a déjà été visité (la première clause dans le prédicat si le courant Le nœud n'a pas été visité, nous attrapons un bord ancré au nœud actuel et visitez cela. Retour dans la 2e clause de Cycle / 2 . À cela point, nous coupons (!) et déclarons le succès La raison de la coupe (!) Est-ce que sans cela, la récupération en arrière entraînerait une révision d'un nœud déjà visitée et donc un ensemble infini de cycles. Cycle / 2 Visite le bord suivant, donc une fois qu'un chemin particulier est épuisé, Cycle / 2 Backtracks et essaie un autre chemin.
Si votre système Prolog a une chaîne avant, vous pouvez l'utiliser pour déterminer les cycles. Mais faites attention, cela pourrait manger un peu de mémoire, car il générera et conservera le chemin Voici comment vous auriez besoin de formuler les règles dans une chaîne avant qui n'élimine pas automatiquement les doublons automatiquement. Le pour rendre l'exemple un peu plus intéressant ce qui concerne le résultat, j'ai chuté le bord the P.s.: Il y a encore des recherches sur: chemin / 2 faits. \ + est là pour éliminer explicitement les duplicats: (d, d) . Voici un échantillon d'échantillon: postulaire / 1 Prédicate ici publie un événement et conserve le propagateur de la chaîne avant exécutée. Comment rédiger vos règles en avant dépend de la bibliothèque respective des systèmes Prolog que vous utilisez.
http://x10.sourceforge.net/documentation/papers/x10workshop2011/elton_slides.pdf