Course #1 : AFCAI Search Algorithms

State Space Search: Constructive search problems

• Uninformed/Blind Search
  • SimpleSearch1()
  • SimpleSearch2()
  • SimpleSearch3()
  • DepthFirstSearch()
  • BeardthFirstSearch()
  • DepthBoundedDFS()
  • DepthFirstIterativeDeepening()
• Heuristic Search: Knowledge Based Search
  • BestFirstSearch()
  • HillClimbing()

Solution Space Search:

• perturbation search problems
  • BeamSearch()
  • TabuSearch()
• Randomized Search
  • IteratedHillClimbing()
  • RandomWalk()
  • SimulatedAnnealing()
  • GeneticAlgorithm()

Case Study : TSP Problem

• Constructive method:
  • TSPNearestNeighbour()
  • GA’s
    • Path representation
    • Ordinal representation
    • Adjacency representation
  • Neural Networks
  • TSPACO()

Optimal Solution Search

• BritishMuseumProcedure()
• Branch&Bound()
• Refinement search
  • generalB&B()
  • Dijkstra’s Algorithm()
  • A* ()
  • IDA*()
  • RecursiveBFS()
  • Puring CLOSED
    • DivideAndConquerFrontierSearch()
    • SparseMemoryGraphSearch()
  • Pruning OPEN
    • BreadthFirstHeuristicSearch()
    • DivideandConquerBeamSearch()
    • BeamStackSearch()
    • DivideandConquerBeamStackSearch()

Rule Based Systems

• AO*
• RETE net

Planning

• ForwardStateSpacePlanning()
• BackwardStateSpacePlanning()
• GoalStackPlanning()
• PlanSpacePlanning()
• Means Ends Analysis
• NOAH
• Hierarchical Planning

Constaint Satisfaction

• Constraint Propagation
  • 1-consistency
  • 2-consistency
    • AC1()
    • AC3()
    • AC4()
  • Huffman clowes scene labelling
  • 3-consistency
    • PC1()
    • Pc2()
  • i-consistency
  • Directional consistency
    • DirectionalArcConsistency()
    • DirectionalPathConsistency()
    • AdaptiveConsistency()
    • Minimum width orderings
  • Back tracking
    • BackTracking()
    • BackTrackingwithLookAhead()
    • BackJumping(){Gashnig’s, Graph, Conflict directed}

Game Play

• MiniMax()
• AlphaBeta()
• SSS*()
• B*()