(* :Title: Common functions used for Search Algorithms *)
(* :Authors: Raza Ahmed and Brian L. Evans *)
(*
:Summary: This package contains the functions which are needed
for the search algorithms.
*)
(* :Context: HeuristicSearch`PolySearchFunctions` *)
(* :PackageVersion: $Revision: 1.10 $ *)
(*
: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`PolySearchFunctions`" ];
(* U S A G E I N F O R M A T I O N *)
PolynomialComponentCost::usage =
"PolynomialComponentCost function is used to specify the cost of addition and
multiplication encountered in the polynomial.";
PolynomialEvaluationCost::usage =
"PolynomialEvaluationCost[polynomial] computes the total implementation cost
to evaluate the polynomial.";
PolynomialSuccessorFunction::usage =
"PolynomialSuccessorFunction[problem, listofrules] uses the rule1list to
generate the rule1list to generate subpolynomials which are then
factored by the polyfactor. This list of the factored subpolynomials
are then appended to the rest of the terms of the polynomial to generate
the successor states to be used by the search algorithms.";
(* E N D U S A G E I N F O R M A T I O N *)
Begin[ "`Private`" ]
(* Global variable to keep track of implementation cost *)
$costtotal = 0;
(* PolynomialComponentCost *)
PolynomialComponentCost[Times] = 5;
PolynomialComponentCost[Plus] = 1;
(* costofpoly *)
costofpoly[_Integer] = 0;
costofpoly[_Symbol] = 0;
costofpoly[problem_Plus] := PolynomialComponentCost[Plus] (Length[problem]-1);
costofpoly[problem_Times] := PolynomialComponentCost[Times] (Length[problem]-1);
costofpoly[Power[_, exp_]] := PolynomialComponentCost[Times] (exp-1);
(* recursive evaluation function to determine the cost of a *)
(* polynomial given multiplication and the addition cost *)
evalpoly[problem_] :=
Module[ {},
$costtotal += costofpoly[problem];
Scan[evalpoly, problem];
$costtotal ]
(* the evaluation function for the polynomial with initialization code *)
PolynomialEvaluationCost[polynomial_] :=
Module[{localproblem},
localproblem = polynomial /. List -> Sequence;
$costtotal = 0;
evalpoly[localproblem] ]
(*
returns the different valuable combinations for a
polynomial choosing two elements
*)
rule1list[problem_] :=
Module[ {factlist, finalresult, newproblem, restlist},
newproblem = problem /. List -> Sequence;
$newproblem = newproblem;
If [ Length[$newproblem] == 2 && Head[$newproblem] === Times,
finalresult = {{$newproblem}},
newproblem = Apply[List, newproblem];
restlist = Map[ combine,
Map[headchange, rule[newproblem]] ];
factlist = Map[ polyfactor,
Map[headchange, rule[newproblem]] ];
finalresult = MapThread[Plus, {restlist, factlist}] ];
finalresult]
(*
Factors two terms of the polynomial provided to it by the specified rule
*)
polyfactor[a_. x_^n_. + b_. x_^m_.] :=
Module[ {result = {}},
If [ n < m, result = x^n (a + b x^(m-n))];
If [ m < n, result = x^m (a x^(n-m) + b)];
If [ m == n, result = x^m (a + b)];
result ]
(*
this function takes the polynomial and provides the successor
states of the polynomial depending on the rules specified
*)
PolynomialSuccessorFunction[problem_, listofrules_] := rule1list[problem]
(*
old head is converted to the new head by providing the problem
as the argument to the function. Also the function head[old] and
head[new] be called before the call to the function
*)
headchange[problem_] :=
If [ Head[problem] === List, problem /. List -> Plus, problem]
(*
this function is to be used under the rule1list to form the rulelist
from which the new successors for the polynomial would be generated
*)
rule[{}] = {};
rule[problem_] :=
Join[ Map[ List[First[problem], #]&, Rest[problem]],
rule[ Rest[problem] ] ]
genProgressiveList[problem_] :=
Table[ Drop[problem, n], { n, 0, Length[problem] - 2 } ]
allPairs[problem_] := Map[ List[First[problem], #]&, Rest[problem] ]
ruleIter[{}] = {};
ruleIter[problem_] :=
Apply[Join, Map[ allPairs, genProgressiveList[problem] ] ]
(* this function appends the terms other than the terms used in the *)
(* rulelist back to the terms used in the rulelist to generate the *)
(* valid successor functions *)
combine[prob_] := { Complement[$newproblem, prob] }
Protect[ PolynomialComponentCost, PolynomialEvaluationCost, PolynomialSuccessorFunction ];
End[];
EndPackage[];