orbital.algorithm.template
Class WAStar

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      orbital.algorithm.template.BestFirstSearch
          orbital.algorithm.template.AStar
              orbital.algorithm.template.WAStar

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm

public class WAStar
extends AStar

WA^* search class.

Time and memory requirements can be lowered significantly by multiplying the heuristic function h(n) by a constant W>1. WA^* uses evaluation function f(n) = g(n) + W*h(n). However solutions are no longer optimal but at most W times from optimal.

Author:

André Platzer

See Also:

"Pohl, I. (1973). The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving. In Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI-73), pages 20-23, Stanford, California, IJCAII.", Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.BestFirstSearch

BestFirstSearch.OptionIterator

Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic

Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

EvaluativeAlgorithm.EvaluationComparator

Constructor Summary

WAStar(double W, Function heuristic)

WAStar(Function heuristic)

WAStar(Real W, Function heuristic)
Create a new instance of WA^* search.

Method Summary

Function	getEvaluation() f(n) = g(n) + W*h(n).
Real	getWeight() Get the weighting argument W for the evaluation function.
boolean	isOptimal() at most W times from optimal if heuristic is admissible.
void	setWeight(Real W) Get the weighting argument W for the evaluation function.

Methods inherited from class orbital.algorithm.template.AStar

complexity, getHeuristic, setHeuristic, spaceComplexity

Methods inherited from class orbital.algorithm.template.BestFirstSearch

createTraversal

Methods inherited from class orbital.algorithm.template.GeneralSearch

getProblem, search, solve, solveImpl

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

solve

Constructor Detail

WAStar

public WAStar(Real W,
              Function heuristic)

Create a new instance of WA^* search. Which is a best first search using the evaluation function f(n) = g(n) + W*h(n).

Parameters:

W - the weighting argument W for the evaluation function.

heuristic - the heuristic cost function h:S→R embedded in the evaluation function f.

See Also:

getEvaluation()

Preconditions:

W >= 1.

WAStar

public WAStar(double W,
              Function heuristic)

WAStar

public WAStar(Function heuristic)

Method Detail

getWeight

public Real getWeight()

Get the weighting argument W for the evaluation function.

setWeight

public void setWeight(Real W)

Get the weighting argument W for the evaluation function.

getEvaluation

public Function getEvaluation()

f(n) = g(n) + W*h(n).

Specified by:

getEvaluation in interface EvaluativeAlgorithm

Specified by:

getEvaluation in interface HeuristicAlgorithm

Overrides:

getEvaluation in class AStar

Returns:

the evaluation function f:S→R used to evaluate (either utility or cost) value of states.

isOptimal

public boolean isOptimal()

at most W times from optimal if heuristic is admissible.

Overrides:

isOptimal in class AStar

Returns:

whether this search algorithm is optimal, i.e. whether solutions found are guaranteed to be optimal.