Definición de camino/sendero/paseo

Resuelto false asked hace 9 años • 0 respuestas

Muchos predicados definen algún tipo de ruta acíclica construida a partir de aristas definidas mediante una relación binaria, de manera bastante similar a la definición de cierre transitivo . Por lo tanto, se requiere una definición genérica.

Tenga en cuenta que las nociones definidas en la teoría de grafos no coinciden fácilmente con lo que comúnmente se espera. En particular, no nos interesan los nombres de los bordes.

Peor aún, también la teoría de grafos ha cambiado un poco, introduciendo la noción de caminata , señalando

Tradicionalmente, sendero se refería a lo que hoy se suele conocer como paseo abierto. Hoy en día, cuando se expresa sin ninguna calificación, se suele entender que un camino es simple, lo que significa que no se repiten vértices (y, por tanto, aristas). (El término cadena también se ha utilizado para referirse a un recorrido en el que todos los vértices y aristas son distintos).

Entonces mi pregunta es: ¿Cómo nombrar y definir esta funcionalidad?

Lo que he hecho hasta ahora es definir:

path(Rel_2, Path, X0,X)

El primer argumento tiene que ser la continuación de la relación, que es un objetivo incompleto al que le faltan dos argumentos más. Luego viene el Patho el par de vértices.

Uso de ejemplo

n(a, b).
n(b, c).
n(b, a).

?- path(n,Xs, a,X).
   Xs = [a], X = a
;  Xs = [a, b], X = b
;  Xs = [a, b, c], X = c
;  false.

Implementación

:- meta_predicate(path(2,?,?,?)).

:- meta_predicate(path(2,?,?,?,+)).

path(R_2, [X0|Ys], X0,X) :-
   path(R_2, Ys, X0,X, [X0]).

path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
   call(R_2, X0,X1),
   non_member(X1, Xs),
   path(R_2, Ys, X1,X, [X1|Xs]).

non_member(_E, []).
non_member(E, [X|Xs]) :-
   dif(E,X),
   non_member(E, Xs).
false avatar May 19 '15 21:05 false
Aceptado

¿ Qué tal definir path/4así?

path(R_2, Xs, A,Z) :-                   % A path `Xs` from `A` to `Z` is ...
   walk(R_2, Xs, A,Z),                  % ... a walk `Xs` from `A` to `Z` ...
   all_dif(Xs).                         % ... with no duplicates in `Xs`.

Para ayudar a la terminación universal, intercambiamos los dos objetivos en la conjunción anterior...

path(R_2, Xs, A,Z) :-
   all_dif(Xs),                         % enforce disequality ASAP
   walk(R_2, Xs, A,Z).

... y utilice la siguiente implementación diferida de all_dif/1:

all_dif(Xs): - % impone la desigualdad de términos por pares
   congelar (Xs, all_dif_aux (Xs, [])). % (puede retrasarse)

all_dif_aux([], _).
all_dif_aux([E|Es], Vs):-               
   maplist (dif(E), Vs), % nunca se retrasa
   congelar(Es, all_dif_aux(Es,[E|Vs])). % (puede retrasarse)

walk/4está definido como path/4y path/5dado por el OP:

:- meta_predicate walk(2, ?, ?, ?).
walk(R_2, [X0|Xs], X0,X) :-
   walk_from_to_step(Xs, X0,X, R_2).

:- meta_predicate walk_from_to_step(?, ?, ?, 2).
walk_from_to_step([], X,X, _).
walk_from_to_step([X1|Xs], X0,X, R_2) :-
   call(R_2, X0,X1),
   walk_from_to_step(Xs, X1,X, R_2).

En mi opinión, lo anterior path/4es más simple y accesible, especialmente para los principiantes. ¿Estarías de acuerdo?

repeat avatar Jul 30 '2015 12:07 repeat

Quiero centrarme en nombrar el predicado.

  • A diferencia de maplist/2, el orden de los argumentos no es de primordial importancia aquí.

  • El nombre del predicado debe dejar claro el significado de los respectivos argumentos.

Hasta ahora es el path_from_to_edgesque más me gusta, pero también tiene sus pros y sus contras.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

Separémoslo:

  • pro: pathes un sustantivo, no se puede malinterpretar como un verbo. Para mí, está implícita una lista de vértices.

  • pro: fromrepresenta un vértice, y lo mismo ocurre con to.

  • Desventaja: edges es algo vago, pero usar lambdas aquí es la opción más versátil.

  • Desventaja: Según Wikipedia , un camino es un sendero en el que todos los vértices ( excepto posiblemente el primero y el último ) son distintos. Entonces eso debería aclararse en la descripción.

Usando lambdas para listas de vértices vecinos Ess:

?- Ess  = [a-[b],b-[c,a]], 
      From = a,
      path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
   Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]
;  Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]
;  Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c]
;  false.

Editar 2015-06-02

¡Otra oportunidad para mejorar los nombres! Esto se inclina más del lado de maplist/2...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

Aquí, graphpor supuesto, hay un sustantivo, no un verbo.

Con respecto al significado de "ruta": las rutas definitivamente deberían permitirlo From=Toy no excluirlo de forma predeterminada (con desigualdades de términos por pares). Es fácil excluir esto con un dif(From,To)objetivo adicional, pero no al revés.

repeat avatar Jun 02 '2015 11:06 repeat

No veo la razón para definir en la ruta/4 los argumentos "nodo inicial" y "nodo final". Parece que una simple ruta/2 con la regla y la lista de nodos debe ser suficiente.

Si el usuario desea una lista que comience con algún nodo (por ejemplo, 'a'), puede consultar la declaración como: ruta (alguna_regla, ['a'|Q]).

Un usuario podría, por ejemplo, solicitar una ruta que tenga una longitud de 10 en la forma: longitud (P, 10), ruta (alguna_regla, P).

*Anexo 1*

Se pueden agregar fácilmente algunos objetivos de utilidad, pero no son el tema principal. Ejemplo, ruta/3 con nodo inicial es:

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).

*Anexo 2*

La adición del último nodo como argumento podría dar la idea falsa de que este argumento impulsa el algoritmo, pero no es así. Supongamos con el ejemplo:

n(a, b).
n(a, c).
n(a, d).

y ejecución del algoritmo de seguimiento para la consulta:

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

Como puede ver, en este caso el algoritmo no aplica la fuerza bruta. Por este motivo, si no se mejora el algoritmo, sugiero no agregar "nodo final" como argumento de "ruta".

pasaba por aqui avatar May 31 '2015 09:05 pasaba por aqui