es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo codificar un programa en Prolog que realice comparaciones en grafos.

16 Jul, 2023 Programación

Estoy tratando de codificar un programa en Prolog que dice verdadero si todos los caminos de a a b tienen el mismo tamaño. Por ejemplo: tenemos un camino de a a b y otro de a a c a b, aquí es falso porque hay dos caminos de a a b con tamaños diferentes, el primero es 1 y el otro es 2. Todos deben tener el mismo tamaño, de lo contrario es falso.

Comencé haciendo esto para obtener la longitud de cada camino, pero estoy atascado aquí, solo necesito comparar si hay dos caminos iguales o no, si es así, luego comparamos los dos resultados, si tienen la misma longitud entonces es verdadero, de lo contrario es falso, pero no sé cómo hacerlo en Prolog:

chemin1(X, Y):-
    arete(X,Y).
chemin1(X, Y):-
    arete(X,Z),
    chemin1(Z,Y).

chemin2(X, Y, N):-
    arete(X, Y),
    N is 1.
chemin2(X, Y, N):-
    arete(X, Z),
    N1 is 1,
    chemin2(Z, Y, N2),
    N is N1+N2.
Tags:  

Answer

  1. Avatar for davy.ai
    davy.ai

    Para comparar si todos los caminos de a a b tienen el mismo tamaño, puedes modificar tu predicado chemin2/3 para hacer un seguimiento de la longitud de cada camino. Luego, puedes usar un predicado auxiliar para verificar si todos los caminos tienen la misma longitud. Aquí tienes una implementación de ejemplo:

    chemin1(X, Y) :-
    arete(X, Y).
chemin1(X, Y) :-
    arete(X, Z),
    chemin1(Z, Y).

chemin2(X, Y, N) :-
    arete(X, Y),
    N = 1.
chemin2(X, Y, N) :-
    arete(X, Z),
    chemin2(Z, Y, M),
    N is M + 1.

same_length([]).
same_length([_]).
same_length([L1, L2 | Rest]) :-
    L1 = L2,
    same_length([L2 | Rest]).

same_length_paths(Start, End) :-
    findall(Len, chemin2(Start, End, Len), Lengths),
    same_length(Lengths).

    En esta implementación, same_length_paths/2 es el predicado principal que puedes usar para verificar si todos los caminos desde Start hasta End tienen la misma longitud. Utiliza findall/3 para obtener una lista de todas las longitudes de los caminos, y luego verifica si todas tienen la misma longitud utilizando same_length/1. Ten en cuenta que same_length/1 toma una lista de longitudes de caminos y utiliza la recursión para verificar si todas las longitudes adyacentes son iguales.

    Para probar tu implementación, puedes usar algunos casos de prueba como:

    ?- same_length_paths(a, b).
true.

?- same_length_paths(a, c).
false.

?- same_length_paths(a, d).
false.

    donde arete/2 está definido de manera adecuada para describir las aristas del grafo.

Comments are closed.