(* :Title: Common functions used for Heuristic Searches *)
(* :Authors: Raza Ahmed and Brian L. Evans *)
(*
:Summary:
*)
(* :Context: HeuristicSearch`GeneralSearch` *)
(* :PackageVersion: $Revision: 1.17 $ *)
(*
:Copyright: Copyright 1996 by Regents of the University of California
Permission is hereby granted, without written agreement and without
license or royalty fees, to use, copy, modify, and distribute this
software and its documentation for any purpose, provided that the above
copyright notice and the following two paragraphs appear in all copies
of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
ENHANCEMENTS, OR MODIFICATIONS.
*)
(* :History: *)
(* :Keywords: *)
(*
:Source:
*)
(* :Warning: *)
(* :Mathematica Version: 2.0 *)
(* :Limitation: *)
(*
:Discussion:
*)
(* :Functions: *)
(* B E G I N P A C K A G E *)
BeginPackage[ "HeuristicSearch`GeneralSearch`" ];
(* U S A G E I N F O R M A T I O N *)
CostReductionFactor::usage =
"CostReductionFactor is an option for the BreadthFirstSearch and
DepthFirstSearch routines.
A setting of 2 will attempt to reduce the cost by a factor of 2.";
EvaluationFunction::usage =
"EvaluationFunction is option for the search routines.
It specifies a function that returns the cost of an expression.";
GoalFunction::usage =
"GoalFunction[problem, parameter, evalfun] is a function
which accepts the problem as one of the arguments and the parameter
by which the cost has to be reduced. If the function is used
under one of the uninformed search algorithms, then the parameter
should be supplied as the optional argument. For the usage within
the uninformed algorithm, see the usage of the uninformed search
algorithm to be used.";
GoalTest::usage =
"GoalTest[state, goal, evalfun] is used by the uninformed search
algorithm. It takes the state on which the goal test is supposed
to be applied and the goal which is set by calling the GoalFunction
before testing for the goal state.";
RuleBasedSuccessorFunction::usage =
"RuleBasedSuccessorFunction[expr, rules] is the default function
for the package to generate the successors of the expression expr
by applying the transformation rules to every subexpression of expr.";
SuccessorFunction::usage =
"SuccessorFunction is an option that specifies a function to generate
a list of possible new states from an existing state. The function
must take two arguments: an expression and a list of rules. In the
search functions, it applies a set of transformation rules to various
parts of the expression to generate a list of equivalent expressions.";
SmallestInList::usage =
"SmallestInList[list, evalfun] returns the element in the list with
the lowest cost returned by evalfun.";
TransformationRules::usage =
"TransformationRules is an option for the various search routines.
It should be set to a list of rules such as {a -> b, c[d_] :> d^2}.";
(* E N D U S A G E I N F O R M A T I O N *)
Begin[ "`Private`" ]
(*
provides the goal for polynomial given the cost reduction
parameter and the problem
*)
GoalFunction[problem_, parameter_, evalfun_] :=
N [ evalfun[problem] / parameter ]
(* checks if the state provided as an argument is the goal state *)
(* it returns a boolean value as the output *)
GoalTest[state_, goal_, evalfun_] :=
If [ evalfun[state] <= goal, True, False]
(* Take a problem and a list of evaluation rules as arguments *)
(* and go recursively through the problem and evaluates if the *)
(* rule applies; if the rule gets applied, a successor state is *)
(* generated and appended to the list of successor states *)
RuleBasedSuccessorFunction[problem_, transformationrules_] :=
Module[{},
$transformationrules = transformationrules;
$successors = {};
$problem = problem;
recursivesubsuccessorfunction[ problem ];
Select[ Flatten[ $successors ], (# =!= $problem)& ]
]
(*
a recursive function to be used by the SuccessorFunction
to walk down the tree
*)
recursivesubsuccessorfunction[problem_] :=
Module[ {subexpressionstobereplaced},
subexpressionstobereplaced = Map[ Replace[problem, #]&,
Select[ $transformationrules,
MatchQ[problem, First[#]]& ] ];
If[ subexpressionstobereplaced =!= {},
$position = Position[$problem, problem];
AppendTo[ $successors, Map[ replacementfunction, subexpressionstobereplaced ] ] ];
Scan[ recursivesubsuccessorfunction, problem ]
]
(*
this function is to be used with the map function to replace the subexpressions
in the tree of the expression
the replaced subexpressions are those with which the patterns in the evaluations
are matched
*)
replacementfunction[problem_] := ReplacePart[ $problem, problem, $position ]
(* function which chooses the minimum cost subexpression determined *)
(* from the evaluation function and the expression *)
SmallestInList[successor_, evalfun_] :=
Module[ {costlist, successors},
successors = successor;
successors = successors /. Sequence -> List;
costlist = Map[evalfun, successors];
Part[ successors, First[Position[costlist, Min[costlist]]] ] ]
Protect[ CostReductionFactor, EvaluationFunction, GoalFunction,
GoalTest, RuleBasedSuccessorFunction,
SuccessorFunction, SmallestInList, TransformationRules ];
End[];
EndPackage[];