< Courses‎ | CS 332L‎ | Spring 2006‎ | Kunhan Kim
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Homework 5

1. In prolog mod is the mod function.
?- X is 23 mod 20.
X = 3.

Use the range/3 predicate and the mod function to generate a list of the divisors of a number.

?- divisors(28, Ds).
Ds = [1, 2, 4, 7, 14]
range(High, High, [High]).
range(Low, High, [Low|Rest]) :- Low @=< High, Next is Low+1, range(Next, High, Rest).

divisors(D, Ds) :- X is D - 1, range(1, X, R), divisors_help(R, D, Ds).
divisors_help([], _, []).
divisors_help([H|T], D, [H|Ds]) :- X is D mod H, X = 0, divisors_help(T, D, Ds).
divisors_help([H|T], D, Ds) :- X is D mod H, X \= 0, divisors_help(T, D, Ds).

2. Do the homework at the end of Prolog and graphs by using the following strategy.
• See if there is a path of length 0.
• If not, see if there is a path of length 1.
• If not, see if there is a path of length 2.
• If not, see if there is a path of length 3. Etc. This strategy is known as Generate and Test. You are generating the integers in sequence and then testing to see if there is a path of that length. You continue to do that until you find a path or you determine that no path is possible. In some cases you might simply search forever. (You will learn about this in CS 486.)
• Use something like is_integer/1 to generate successively larger integers.
• Assume you know the total number of edges in the graph. Don't allow the possible length of the path to exceed the total number of edges. That is, as you increment the possible path length, don't allow it to exceed the total number of edges. If no path is found, fail.
• On backtracking generate longer and longer paths up to the limit of the maximum possible path length. When no further paths less than or equal to the maximum are found, fail. Given the data in Prolog and graphs, the following is one possible output.
?- shortestPath(1, 5, Path).

Path = [1, 2, 5] ;

Path = [1, 4, 5] ;

Path = [1, 3, 5] ;

Path = [1, 2, 3, 5] ;

Path = [1, 4, 3, 5] ;

Path = [1, 3, 4, 5] ;

Path = [1, 3, 2, 5] ;

Path = [1, 2, 3, 4, 5] ;

Path = [1, 4, 3, 2, 5] ;

No

?-

/* prolog tutorial 2.15 Graph structures and paths */

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).

connected(X,Y) :- edge(X,Y) ; edge(Y,X).

path(A,B,Path) :-
travel(A,B,[A],Q),
reverse(Q,Path).

travel(A,B,P,[B|P]) :-
connected(A,B).
travel(A,B,Visited,Path) :-
connected(A,C),
C \== B,
\+member(C,Visited),
travel(C,B,[C|Visited],Path).

shortestPath(A, B, Path) :- shortestPath_help(A, B, Path, 0, 8). /* assume 8 is total number of edges */
shortestPath_help(A, B, Path, S, L) :- X is L - 1, S =< L, shortestPath_help(A, B, Path, S, X).
shortestPath_help(A, B, Path, _, L) :- path(A, B, Path), length(Path, L).

3. To avoid backtracking forever once one finds the longest possible path, you will have to modify is_integer/1 so that it fails when it reaches a limit. That is, convert is_integer/1 to be is_integer(+Max, ?Int), which on backtracking returns in Int all integers less than or equal to Max.
?- is_integer2(6, Int).

Int = 0 ;

Int = 1 ;

Int = 2 ;

Int = 3 ;

Int = 4 ;

Int = 5 ;

Int = 6 ;

No

?-

is_integer2(Max, Int) :- is_integer2_help(0, Max, Int).
is_integer2_help(S, Max, Int) :- X is Max - 1, S < Max, is_integer2_help(S, X, Int).
is_integer2_help(_, Max, Int) :- Int = Max.

4. Use generate and test to find (on backtracking) all perfect integers—i.e., integers which are the sum of their divisors.
?- is_perfect(X).

X = 6;

X = 28; …

sum([], 0).
sum([H|T], Sum) :- sum(T, S), Sum is S + H.

is_perfect(X) :- is_perfect_help(6, X).
is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S = A, X = A.
is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S = A, B is A + 1, is_perfect_help(B, X).
is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S \= A, B is A + 1, is_perfect_help(B, X).