iterative deepening depth first search


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Generic Iterative Deepening Depth-First search algorithm implementation
-- See : http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

-- Notes : this is a generic implementation of IDDFS algorithm.
-- It is devised to be used on any type of graph (point-graph, tile-graph,
-- or whatever. It expects to be initialized with a handler, which acts as
-- an interface between the search algorithm and the search space.

-- The IDDFS class expects a handler to be initialized. Roughly said, the handler
-- is an interface between your search space and the generic search algorithm.
-- This ensures flexibility, so that the generic algorithm can be adapted to
-- search on any kind of space.
-- The passed-in handler should implement those functions.
-- handler.getNode(...)   ->  returns a Node (instance of node.lua)
-- handler.getNeighbors(n) -> returns an array of all nodes that can be reached
--                            via node n (also called successors of node n)

-- The actual implementation uses recursion to look up for the path.
-- Between consecutive path requests, the user must call the :resetForNextSearch()
--  method to clear all nodes data created during a previous search.

-- The generic Node class provided (see node.lua) should also be implemented
-- through the handler. Basically, it should describe how nodes are labelled
-- and tested for equality for a custom search space.
-- The following functions should be implemented:
-- function Node:initialize(...) -> creates a Node with custom attributes
-- function Node:isEqualTo(n)    -> returns if self is equal to node n
-- function Node:toString()      -> returns a unique string representation of
--                                  the node, for debug purposes

-- See custom handlers for reference (*_hander.lua).

-- Dependencies
local class = require 'utils.class'

-- Builds and returns the path to the goal node
local function backtrace(node)
  local path = {}
  repeat
    table.insert(path, 1, node)
    node = node.parent
  until not node
  return path
end

-- Runs a depth limited search
local function depthLimitedSearch(finder, start, goal, depth)
  if start == goal then  return backtrace(start) end
  if depth == 0 then return end
  start.visited = true
  local neighbors = finder.handler.getNeighbors(start)
  for _, neighbor in ipairs(neighbors) do
    if not neighbor.visited then
      neighbor.parent = start
      local foundGoal = depthLimitedSearch(finder, neighbor, goal, depth - 1)
      if foundGoal then return foundGoal end
    end
  end
end

-- Initializes IDDFS with a custom handler, and an maximum
-- depth search, which arbitrarily defaults to 10.
local IDDFS = class()
function IDDFS:initialize(handler, maxDepth)
  self.handler = handler
  self.maxDepth = maxDepth or 10 -- arbitrary constant
end

-- Clears all nodes for a next search
-- Must be called in-between consecutive searches
function IDDFS:resetForNextSearch()
  local nodes = self.handler.getAllNodes()
  for _, node in ipairs(nodes) do
    node.visited, node.parent = nil, nil
  end
end

-- Returns the path between start and goal locations
-- start   : a Node representing the start location
-- goal    : a Node representing the target location
-- returns : an array of nodes
function IDDFS:findPath(start, goal)
  for depth = 1, self.maxDepth do
    self:resetForNextSearch()
    local p = depthLimitedSearch(self, start, goal, depth)
    if p then return p end
  end
end

return IDDFS
-- Tests for iddfs.lua
local IDDFS = require 'iddfs'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function same(t, p, comp)
  for k,v in ipairs(t) do
    if not comp(v, p[k]) then return false end
  end
  return true
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing linear graph', function()
  local comp = function(a, b) return a.value == b end
  local ln_handler = require 'handlers.linear_handler'
  ln_handler.init(-2,5)
  local iddfs = IDDFS(ln_handler)

  local start, goal = ln_handler.getNode(0), ln_handler.getNode(5)
  assert(same(iddfs:findPath(start, goal),  {0,1,2,3,4,5}, comp))

  iddfs.maxDepth = 4
  assert(not iddfs:findPath(start, goal))

  iddfs.maxDepth = 8
  start, goal = ln_handler.getNode(-2), ln_handler.getNode(5)
  assert(same(iddfs:findPath(start, goal),  {-2,-1,0,1,2,3,4,5}, comp))

  iddfs.maxDepth = 6
  assert(not iddfs:findPath(start, goal))
end)

run('Testing grid graph', function()
  local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
  local gm_handler = require 'handlers.gridmap_handler'
  local iddfs = IDDFS(gm_handler)
  local map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
  gm_handler.init(map)

  local start, goal = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
  iddfs.maxDepth = 15
  assert(same(iddfs:findPath(start, goal), {{1,1},{1,2},{1,3},{2,3},{3,3},{4,3},{5,3}}, comp))

  iddfs.maxDepth = 5
  assert(not iddfs:findPath(start, goal))
end)

run('Testing point graph', function()
  local comp = function(a, b) return a.x == b[1] and a.y == b[2] end
  local pg_handler = require 'handlers.point_graph_handler'
  local iddfs = IDDFS(pg_handler)

  pg_handler.addNode('a')
  pg_handler.addNode('b')
  pg_handler.addNode('c')
  pg_handler.addNode('d')
  pg_handler.addEdge('a', 'b')
  pg_handler.addEdge('a', 'c')
  pg_handler.addEdge('b', 'd')

  local comp = function(a, b) return a.name == b end
  local start, goal = pg_handler.getNode('a'), pg_handler.getNode('d')
  iddfs.maxDepth = 3
  assert(same(iddfs:findPath(start, goal, 3), {'a','b','d'}, comp))

  iddfs.maxDepth = 1
  assert(not iddfs:findPath(start, goal, 1))
end)
--]]
print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))