prolog programming homework
cfdingfvrus
prolog.zipdownload_20150824_130940/Assignment 2 - answers to example problems 0,1,2
solution to problem0 = [[1,2,3,4,5,6,7,8,0]] solution to problem1 = [[1,2,3,4,5,6,7,0,8], [1,2,3,4,5,6,7,8,0]] solution to problem2 = [[1,2,3,4,5,6,0,7,8], [1,2,3,4,5,6,7,0,8], [1,2,3,4,5,6,7,8,0]]
download_20150824_130940/idastar.txt
% Computational Intelligence: a logical approach. % Prolog Code. % Iterative deepening A* search, based on the generic search algorithm. % Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press. % Modified by Mike Barley, University of Auckland, 2014 :- dynamic problem/2. % solution(+ProblemName, ?Solution) solution(ProblemName, Solution) :- retractall(problem(_,_)), [ProblemName], problem(I,G), solutionAux(problem(I,G), Solution). % solutionAux(problem(+InitialState, +GoalState), -Solution) solutionAux(problem(InitialState, GoalState), Solution) :- retractall(is_goal(_)), assert(is_goal(GoalState)), idsearch(InitialState, RevSolution), reverse(RevSolution, Solution). % idsearch(N,P) is true if path P is a path found from node N % using iterative deepening A* search % Example query: idsearch(o103,P). idsearch(N,P) :- h(N,HN), writeln(['Trying Depth bound: ',HN]), dbsearch([node(N,[],0)],HN,[node(N,[],0)],natural,P). % dbsearch(F,DB,Q,How1,P) is true if a depth bound search from frontier F % can find a path P of length >= DB. % where Q is the initial frontier to (re)start from, % How specifies whether the previous bound failed naturally or gives % the minimum f-value for which the search failed. % The frontier is a list of node(Node,Path,PathLength) % where Node is a node, Path is the path found to Node, % PathLength is the length of the path. %dbsearch(F,_,_,_,_) :- % writeln(['Frontier: ',F]), % fail. dbsearch([],_,Q,NDB,S) :- number(NDB), writeln(['Trying Depth bound: ',NDB]), dbsearch(Q,NDB,Q,natural,S). dbsearch([node(N,P,DB)|_],DB,_,_,[N|P]) :- is_goal(N). dbsearch([node(N,P,PL)|F1],DB,Q,H,S) :- h(N,HN), HN+PL =< DB, neighbors(N,NewNs), subtract(NewNs, P, NNs), % loop elimination add_paths_db(NNs,N,[N|P],PL,F1,F2), dbsearch(F2,DB,Q,H,S). dbsearch([node(N,_,PL)|F1],DB,Q,H,S) :- h(N,HN), HN+PL > DB, min1(HN+PL,H,LUB), dbsearch(F1,DB,Q,LUB,S). % add_paths(NNs,N,Path,PL,F0,F1) add_paths_db([],_,_,_,F,F). add_paths_db([NN|R],N,Path,PL,F0,[node(NN,Path,PL1)|F1]) :- cost(N,NN,AC), PL1 is PL+AC, add_paths_db(R,N,Path,PL,F0,F1). min1(E,natural,V) :- !, V is E. min1(E,V,V) :- V =< E. min1(E,V,V1) :- V > E, V1 is E. % ************************************************** % writeln(L) is true if L is a list of items where each % item is written on a separate line, followed by a newline. writeln([]) :- nl. writeln([H|T]) :- write(H), nl, writeln(T). %% we are making all edge costs to be 1 %% if you want different edges to have %% different costs you must comment this out %% and include a cost predicate in the domain %% file cost(_,_,1).
download_20150824_130940/Version 2 Assignment 2 Description.pdf
CS367 Assignment 2 – Search [worth 6% of final grade]
Due: Monday 24th August 2015 at 1:00 am Assignment Description: This assignment is to write the neighbors/2 and h/2 (heuristic evaluation) relations for the eight sliding tile puzzle. You are given a version of the IDA* algorithm, its location is described below in the Resources section. What the eight tile puzzle looks like. There are 8 numbered tiles and 9 board locations. No two tiles can ever be in the same location.
For a given domain, the IDA* algorithm needs to be given a neighbors relation, neighbors(State, Neighbors) and a heuristic evaluation relation, h(State, Evaluation). You are to write the neighbors and h relations for the following domain: 8 Sliding Tile Puzzle (8STP): State Representation: An 8STP state describes which tiles are in which board locations. There are nine board locations and eight tiles and a blank. The tiles are numbered 1 through 8, and the blank is represented by the number 0. A state is represented by a list. In the list the first element indicates which tile is in the upper left hand location, the second element the upper middle location, etc. Example: The board shown above is represented by the list [2, 8, 3, 4, 1, 6, 5, 7, 0]. Problem Representation: The IDA* problem solver will be given problems to solve. The problem will be represented using a functor called “problem” and two arguments: initial state and goal state. For example: problem([2, 8, 3, 4, 1, 6, 5, 7, 0], [1,2,3,4,5,6,7,8,0]). neighbors(+State, -Neighbors) : This predicate returns the list of all the states directly reachable from State, you will probably write a number of clauses for this predicate. h(+State, -HeuristicValue): This predicate returns the Manhattan Distance of State from the goal state. The goal state can be accessed by h by querying “is_goal(GoalState)”.
mbar098� 10/8/15 10:43 AM Deleted: isGoal
Resources: There are a number of files available as resources for this assignment, they can be downloaded from this assignment’s webpage. The files are:
1. The IDA* algorithm, entitled idastar.pl. 2. Sample problem files, entitled problemn.pl, where n is an integer.
Submission: Submit the eight sliding tile puzzle domain description (the neighbors and h relations) in an ascii text file entitled eightPuzzle.pl. Any auxillary predicates that you have defined and used to simplify the writing of neighbors and h, also have to be included in eightPuzzle.pl. Late Submissions: If you submit your assignment after the due date but before two (2) days after the due date, then it will have 20% of its marks deducted. Assignments will not be accepted after that. General Comments: Your code can, obviously, use built-in and library predicates, but, except for is_goal/2, the only other predicates you can use are those you define in eightPuzzle.pl. You can write auxillary predicates to make the writing of neighbors and h easier, but they need to be defined.
mbar098� 10/8/15 10:43 AM Deleted: isGoal
