Recherche de graphe avec une fonction de prédicat qui conserve la trace de la limite de saut

Question

Le code suivant recherche un graphe et renvoie true ou false en fonction de la fonction de prédicat passée en paramètre.

Le graphique est représenté sous la forme d'une liste d'adjacence.

Supposons que le graphique ne contient pas de cycles.

code:

(define (search predicate? key) 
    (define value-list (lookup key)) 
    (if (not (empty? value-list)) 
     (if (findf predicate? value-list) 
      #t 
      (ormap (curry search predicate?) value-list)) 
     #f)) 

La fonction loopup est utilisée pour faire une recherche sur une table de hachage et retourne ses chemins correspondants.

La fonction de recherche obtient les chemins et si elle est trouvée non vide essaie de trouver l'élément en utilisant la fonction de prédicat et si elle est trouvée renvoie true sinon appelle search() pour chaque élément de la liste.

Cela semble fonctionner.

maintenant je suis coincé ficelage pour atteindre les objectifs suivants:

Actuellement, la fonction de recherche parcourt le graphe complet et applique prédicat à tous ses nœuds.

Je souhaite créer une fonction de prédicat qui inclut non seulement l'élément à rechercher mais inclut également la limite de saut. Par exemple: si la valeur de saut est 1: la fonction de prédicat retournerait true si et seulement si le nœud de recherche est à 1 saut et false dans le cas contraire.

Je souhaite généraliser la limite de saut pour n sans modifier la recherche().

choses que je pensais de jusqu'à maintenant pour résoudre ce:

1.I pourrait changer la fonction de recherche pour passer le nombre de sauts en tant que paramètre et l'utiliser pour mettre fin à de la récursion, mais je ne veux pas changer la fonction de recherche.

2.Créez le nombre de nœuds pouvant être visités avec la limite de saut donnée et stockez cette information dans la fonction de prédicat et pour chaque appel de la fonction de prédicat, décrémentez le compte et si le nombre atteint 0 renvoie false à chaque fois. (Cependant, je ne suis pas sûr de savoir comment implémenter ce qui précède (peut-être des fermetures?), Et je ne pense pas que cela fonctionnerait parce que le compte pourrait être utilisé pour la liste de nœuds la plus longue)

3.Si je pouvais trouver le l'appelant dans la fonction de prédicat, c'est-à-dire si l'appelant est findf, alors n'incrémente pas le compte, si l'appelant recherche l'incrément du nombre présent dans le prédicat et l'utilise. Qui m'a conduit à: Detecting the caller of a function in Scheme or Racket

Cependant cela n'a pas aidé.

suis coincé et des idées toute aide serait appréciée.

Modifier:

Une petite précision pourquoi je sentais que l'approche 2 ne fonctionnerait pas.

La recherche de fonction effectue une première recherche de rayon.

Je pense que l'approche 2 ne fonctionnerait pas pour les 2 raisons suivantes.

Supposons que le graphique

Say Position de départ est « A » et l'élément de recherche est « je » avec limite hop comme 2.

Maintenant, la valeur du compteur = nombre de nœuds qui peut être visité avec 2 houblonnières compte à partir de 'A' qui est: count = 0 (intially)

Dans nombre de sauts 1: 'C' et 'D', count = 2

Dans nombre de sauts 2: 'F', 'G', 'H', 'I', count = 2 + 4 = 6.

Commençons par 'A' la façon dont le code fonctionnerait est

nœuds visités (en findf) serait 'C' et 'D', comte = 6 - 2 = 4

laisse supposer que la moitié gauche est pris en premier.

Maintenant, 'C' devient la clé et toutes ses sous-enfant sont visités

nœuds visités (en findf) serait 'F', 'G', 'H', count = 03/04 = 1

'F' n'a pas de sous-cliché donc pas de probs.

« G » a un subchild il rend visite à « K » et le nombre devient = 1-1 = 0.

donc désormais toutes les itérations reviendriez faux parce que nous comptions le nombre max-de nœuds si l'approche 2 est suivi Une façon de le résoudre serait d'ajuster le compte correctement, mais je pense que nous pourrions finir par faire une recherche complète du graphique pour que l'élément garde une trace du nombre correct.

Answer 1

Avertissement pour cette réponse: Je vois la question comme un casse-tête de type casse-tête; Je pense que le meilleur façon de résoudre ce problème est via l'approche # 1 décrite dans la question. Mais si nous partons du principe que nous ne sommes pas autorisés à modifier search, pour une raison quelconque ...

... et nous supposons que le predicate? que nous passons est autorisé à maintenir l'état et faire des appels à la lookup que est utilisé dans search (et est notre représentation essentielle pour le graphique), ...

alors je pense que l'on peut atteindre votre objectif, en ayant le predicate? garder seul le nombre de bonds pour tous les nœuds qu'il a rencontré. Puis, il peut simplement interroger cette table de comptage de bonds à chaque fois qu'il veut savoir si le nœud qu'il a rencontré est trop éloigné.

Voici le code que je l'ai fait pour illustrer ceci:

(define (is-parent-of? maybe-parent maybe-child) 
    (member maybe-child (lookup maybe-parent))) 

(define (hist-capturing-pred root pred?) 
    (let ((hop-counts (list (list root (box 0))))) 
    (lambda (n) 
     (let* ((parents (filter (lambda (entry) (is-parent-of? (car entry) n)) 
           hop-counts)) 
      (min-count (apply min (map unbox (map cadr parents))))) 
      ;; the `min-count` above represents a distance given what we 
      ;; know so far. Its possible that we actually encountered `n` 
      ;; *previously* via a *longer* path, in which case not only 
      ;; will there already be an entry for `n` in the `hop-counts` 
      ;; table, but it will have recorded a non-globally-minimum 
      ;; hop-count. 
      ;; 
      ;; So, check if there is an entry for `n`, and if so, make 
      ;; sure it holds the currently known minimum value. 
     (cond ((assoc n hop-counts) 
       => (lambda (entry) 
        (set-box! (cadr entry) 
           (min min-count (unbox (cadr entry)))))) 
       (else 
       ;; otherwise, add a new entry for `n` to the table 
       (set! hop-counts (cons (list n (box (+ 1 min-count))) 
             hop-counts)))) 
     (pred? (map (lambda (entry) (list (car entry) (unbox (cadr entry)))) 
        hop-counts) 
       n))))) 

Et voici quelques appels d'échantillons dans la fenêtre interactions DrRacket:

> (search (hist-capturing-pred 'A (lambda (h n) (display `(,h ,n)) (newline) (eq? n 'I))) 'A) 
(((C 1) (A 0)) C) 
(((D 1) (C 1) (A 0)) D) 
(((F 2) (D 1) (C 1) (A 0)) F) 
(((G 2) (F 2) (D 1) (C 1) (A 0)) G) 
(((H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) H) 
(((K 3) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) K) 
(((K 2) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) K) 
(((I 2) (K 2) (H 2) (G 2) (F 2) (D 1) (C 1) (A 0)) I) 
#t 
> (search (hist-capturing-pred 'A (lambda (h n) (and (eq? n 'I) (< (cadr (assoc 'I h)) 3)))) 'A) 
#t 
> (search (hist-capturing-pred 'A (lambda (h n) (and (eq? n 'I) (< (cadr (assoc 'I h)) 2)))) 'A) 
#f 
>