Orbital library

orbital.algorithm.template
Class WAStar

java.lang.Object
  extended by orbital.algorithm.template.GeneralSearch
      extended by orbital.algorithm.template.BestFirstSearch
          extended by orbital.algorithm.template.AStar
              extended by 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.

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.