Rearrangement Of Polynomials Using
Search Algorithms

Introduction

Polynomials can be rearranged in a certain way so that the form obtained by the manipulation could match some desired form. One such rearrangement is assigning the multiplications in the polynomial to have some units of cost by some factor higher than the units of cost assigned to the additions in the polynomial. This way the optimal form in terms of  cost would be  Horner's form which would then have the least number of multiplications.

An nth order polynomial in its standard form has its structure such that the number of the multiplications are maximized. As the assigned cost of the  multiplication was five times as much as the cost of the addition, the original structure of the polynomial had to be altered in such a way that the resulting form would  mathematically be  equivalent but at the same 
time, the form would be such that the number of multiplications in the  polynomial get  minimized.  To accomplish the task, four search  algorithms were used.  The  algorithms used  were divided into two classes:  informed and the  uninformed search algorithms. The uninformed search algorithms have no available information to guess the  location of the  goal state and thus have to go exhaustively through the search tree. However, they can identify the goal state if they ever reach it. Search algorithms generate the new successor states using legal operations on the current state. The two uninformed search algorithms used include breadth first search and the  depth first search. The informed search algorithms on the  other hand include some sort of heuristic to help  the  navigation to the  goal state. The two informed search algorithms used were hill climbing and simulated annealing.

The following polynomial will be used throughout  the  book to illustrate the working of the search algorithms

polynomiallocal = A x + B x^2 + C x^3 + D x^4 + E x^5

Background

All the algorithms require a successor function to be passed in. If one is not passed in, then the  default  successor function will be used which also requires the rules to be passed in to be used by the default successor function. An evaluation function specific to the problem should be passed  in otherwise the default evaluation function will  be  processed which is simply the number of leaves in the mathematical expression.

If the uninformed search algorithms are used, then the factor by which the cost has to be reduced should be passed in so that the goal state could be determined.

If the simulated annealing is used then the cooling schedule along with the maximum number of iterations should be provided. If they are not passed in, then the default cooling schedule along with the default number of iterations equal to twenty will be used by the algorithm. The exact names of the parameters can be determined by the usage statements. The examples of running along with some results are shown below the captions "Example".

The following statement will load all the required packages required to run the algorithms.

Needs[ "HeuristicSearch`Master`" ]

The following section will provide some insight into the working of the four search algorithms.  Discussion of informed search algorithms will follow the discussion of uninformed search algorithms.

Breadth First Search

The breadth first search goes through the search tree and makes a list of nodes to be explored.  Each time a node is plucked out of the list of nodes from the front. The node is checked to see if it is the goal state.  If the plucked up node is the goal state, then the  search stops and provides the node as the result.  If the node is not the goal state, then its successors are found using the successor function. The successors of the node are then appended at the end of the list of nodes to be explored. In this way, the search goes breadth wise through the tree and explores the tree in the row wise fashion starting from the given problem.

The time complexity of the search technique is exponential. This is because for each new node, the algorithm generates a new set of successors to be evaluated.

The memory requirement of the algorithm is also exponential because the algorithm has to store all the nodes to be explored in the memory.

However, it should be noted that the algorithm is complete.

Examples

BreadthFirstSearch[polynomiallocal, 
                   EvaluationFunction -> InitEvalPoly,
                   SuccessorFunction -> PolySuccessorFunction,
                   CostReductionFactor -> 1.5 ]

BreadthFirstSearch[polynomiallocal, 
                   EvaluationFunction -> InitEvalPoly,
                   SuccessorFunction -> PolySuccessorFunction,
                   CostReductionFactor -> 2 ]

Note: The  cost  has been reduced by the  factor of 1.5 and 2 
respectively.

Depth First Search

This algorithm differs from the breadth first search in the manner that it appends the newly explored nodes at the beginning of the list of nodes to be explored. In that way, the first successor of the newly explored node is explored next. Thus the search algorithm goes straight down the tree to look for the goal state. Once it reaches the leaf of the tree, it backs off and goes to the next successor in the last explored set of the successors.

The time complexity of the depth first search is same as the breadth first search in the worst case, because in the worst case, both of the search algorithms will have to go through the whole tree.  The user can explore this fact by the running the two algorithms in the tree without a goal.  This situation can be handled by varying the parameter associated with the goal function.

It should be noted that the space complexity of the algorithm is linear.  However, the depth first search technique outperforms the breadth first search in the tree structures where there are many goal states.  The other situation where the depth first search might outperform the breadth first search is when the goal state is situated in deepest of the layers of a tree.  This situation is very similar to the situation encountered in the case of polynomials where more factored form is preferred over the less factored form. That is the reason why the depth first search performs much better than the breadth first search in the present case.

Examples

DepthFirstSearch[polynomiallocal, 
                 EvaluationFunction -> InitEvalPoly,
                 SuccessorFunction -> PolySuccessorFunction,
                 CostReductionFactor -> 1.5 ]

DepthFirstSearch[polynomiallocal, 
                 EvaluationFunction -> InitEvalPoly,
                 SuccessorFunction -> PolySuccessorFunction,
                 CostReductionFactor -> 2 ]

Note: The reduction in cost by the same factor is achieved the depth first search.

Hill Climbing

This is the search strategy that uses heuristic which in the present case is also the evaluation function.  The evaluation function tells which state of the successor states is the one with minimum cost.  The algorithm works as follows.  It first takes the problem as the current state and finds the next one by taking the smallest cost state of the newly generated successor states.  If the cost of the next state found by the above method is less than the cost of the current state, the current state is assigned the next state and the search goes on.  If the next state has the cost greater than the cost of the current state, the search is stopped and the current node is  returned as the result.

In the case of the polynomials, the hill climbing search outperforms other search strategies because of the way successor states are generated.  Since all the newly generated states are further factored, the next state cannot have the cost greater than the current state.  Also in this way, the algorithm does not have any local maximas to get stuck on and provides the form where the rule can no longer be applied on the resultant state.  This method thus give the optimal form for the rule devised to reach the solution for the problem.  It should however be noted that this optimal form is for the rule used in this context and could be drastically different for some other rule.  Also if some other rule is used, there is a possibility that the algorithm might encounter the local maximas.  This would happen if the new rule expands some terms in the polynomial before it gets to the form where the structure would be such that the cost could be minimized.

Examples

HillClimbing[polynomiallocal, 
             EvaluationFunction -> InitEvalPoly,
             SuccessorFunction -> PolySuccessorFunction]

Note: The optimal form has been achieved using the hill climbing algorithm.

Simulated Annealing

Simulated annealing is the second algorithm used in this context which uses a heuristic for an intelligent search. Instead of starting again randomly when stuck on a local maximum, the algorithm allows some downhill steps to escape the local maximum. The innermost loop of the simulated annealing is quite similar to hill climbing.  Instead of picking the best move, however, it picks a random move.  If the move actually improves the situation, it is always executed. Otherwise, the algorithm makes the move with some probability less than one.  The probability decreases exponentially with the "badness" of the move by the amount deltaE by which the evaluation is worsened.

A second parameter temperature is also used to determine the probability. At higher values of temperature, "bad" moves are more likely to be allowed. A temperature tends to zero, they become more and more unlikely, until the algorithm behaves more or less like hill climbing.  The schedule input determines the value of temperature as a function of how many cycles already have been completed.  The algorithm was developed from an explicit analogy with annealing-the process of gradually cooling a liquid until it freezes. The evaluation function corresponds to the total energy of the atoms in the material. Schedule determines the rate at which the temperature is lowered. Individual moves in the state space correspond to random fluctuations due to thermal noise. One can prove that if the temperature is lowered sufficiently slowly, the material will attain a lowest-energy (perfectly) ordered configuration.This corresponds to the statement that if the schedule lowers the temperature slowly enough, the algorithm will find a global optimum.

Examples

SimulatedAnnealing[polynomiallocal, 
                   EvaluationFunction -> InitEvalPoly,
                   SuccessorFunction -> PolySuccessorFunction,
                   MaxIterations -> 100]

SimulatedAnnealing[polynomiallocal, 
                   EvaluationFunction -> InitEvalPoly,
                   SuccessorFunction -> PolySuccessorFunction,
                   MaxIterations -> 500]

Note: Not a quite optimal form has been achieved because the default cooling function does not cool slowly enough.

Reference Manual

The functions used by the four search algorithms which are also available for the public usage include following.

General Algorithm Usage Functions:
The following functions could be found in the package named "GENERAL`GeneralSearch`"

DefaultEvaluationFunction
TheSmallest
RuleBasedSuccessorFunction
GoalFun
GoalTest

Polynomial Manipulation Functions:
The following functions could be found in the package named
"GENERAL`PolySearchFunctions`"

EvalPoly
InitEvalPoly
PolySuccessorFunction

For the complete usage information of the functions, use

?EvalPoly

References

[1] S. Wolfram, Mathematica: A System for Doing Mathematics by Computer, Redwood City, CA: Addison-Wesley, second ed., 1991.

[2] S. Russel and P. Norvig, Artificial Intelligence: A Modern Approach.  Englewood Cliffs, NJ: Prentice Hall, 1995.