Comment trouver la liste de la longueur la plus courte d'un ensemble infini (Prolog)

Question

J'ai une fonction Prolog path(A,B,Path) qui donne tous les chemins valides sur une planche de A à B.

La sortie de cette fonction ressemble à ceci:

?- path(0,2,Path). 
Path = [0, 1, 2] ; 
Path = [0, 3, 2] ; 
Path = [0, 1, 4, 2] ; 
Path = [0, 3, 4, 2] ; 
Path = [0, 1, 4, 5, 3, 2] ; 

etc, etc.

Il génère un ensemble de listes infinies contenant des chemins valides. Je voudrais simplement obtenir le plus court de ces chemins (aussi nombreux soient-ils). C'est, je veux une fonction shortest(A,B,Path) qui wil donnent les chemins les plus courts valides sur une planche de A à B.

La sortie I veux est:

?- shortest(0,2,Path). 
Path = [0, 1, 2] ; 
Path = [0, 3, 2] ; 
false. 

Je joue autour de la setof fonctionne en Prolog pour lier tous les chemins à un ensemble où j'impose une certaine restriction de longueur, mais je n'ai pas encore réussi à le faire fonctionner.

Mon pauvre travail à ce jour ressemble à ceci. C'est certainement faux, et j'apprécierais toute aide pour comprendre comment fonctionne setof et comment je peux trouver les listes les plus courtes de cet ensemble. Merci!

shortest(A,B,MinPath) :- 
    setof(Path,path(A,B,Path),MinPath), 
    min(length(Path), length(MinPath)). 

Answer 1

Ceci est un cas classique pour l'approfondissement itératif. Il suffit d'entrer au niveau supérieur:

?- length(Path, N), path(0, 2, Path). 

La première réponse sera la plus courte. Et c'est ce que vous pouvez faire avec élégance dans Prolog: Vous êtes commençant pour énumérer un ensemble infini, en espérant que vous trouverez ce que vous recherchez après un certain laps de temps.

Puisque probablement tous les chemins de cette longueur vous intéressent, vous voulez tous. Sinon, vous êtes heureux avec ci-dessus. En outre, vous pouvez énumérer les chemins les plus courts pour différents nœuds. Par conséquent, node/1 doit être le nœud se trouvant dans votre graphique. Dites, vous avez des nœuds 0 à 10, puis node/1 pourrait être définie comme:

node(N) :- 
    between(0,10,N). 

shortest(A,B, Minpath) :- 
    setof(Min, Path^(node(A), node(B), 
         once((length(Path, Min), path(A, B, Path)))), [Min]), 
    length(Minpath, Min), 
    path(A, B, Minpath). 

Cependant, cette solution a une prise; une prise très laide, en effet. Vous avez dit:

(mais il y a beaucoup)

Dans le cas où il n'y a pas de chemin tout, cette solution en boucle pour toujours. Tu étais prévenu.

Éditer: Pour être complet: J'ai supposé que path/3 se termine si la longueur de la liste est fixe. Et pour conclure: Pour un graphe simple et concret, une méthode plus explicite d'éviter les cycles est préférable. Cependant, il y a beaucoup de situations où il n'est pas clair du tout ce qu'est un cycle (pensez à simuler une machine simple), et dans de telles situations, l'approfondissement itératif est incroyablement efficace: Pas de pensée intelligente dans la tête. Prolog.

Il y a une note finale sur la boucle dans le cas où il n'y a aucun chemin du tout.Pour surmonter ce problème, vous avez besoin d'une sorte de calcul limité par les ressources. SICStus Prolog offre library(timeout), d'autres systèmes ont des fonctionnalités plus ou moins comparables. SWI (récemment) a introduit call_with_inference_limit/3 (avec une interface assez arcane) à cette fin.