Merge pull request kennyledet#227 from Yonaba/master

patrickyevsukov · patrickyevsukov · commit 9f465e32100d · 2014-01-28T16:16:36.000-08:00
Iterative Deepening Depth First Search
diff --git a/Breadth_First_Search/Lua/Yonaba/bfs_test.lua b/Breadth_First_Search/Lua/Yonaba/bfs_test.lua
@@ -28,7 +28,7 @@ run('Testing linear graph', function()
   local comp = function(a, b) return a.value == b end
   local ln_handler = require 'linear_handler'
   ln_handler.init(-2,5)
-	local bfs = BFS(ln_handler)
+  local bfs = BFS(ln_handler)
   local start, goal = ln_handler.getNode(0), ln_handler.getNode(5)
   assert(same(bfs:findPath(start, goal),  {0,1,2,3,4,5}, comp))
 
@@ -41,7 +41,7 @@ run('Testing grid graph', function()
   local gm_handler = require 'gridmap_handler'
   local bfs = BFS(gm_handler)
   local map = {{0,0,0,0,0},{0,1,1,1,1},{0,0,0,0,0}}
-	gm_handler.init(map)
+  gm_handler.init(map)
 
   gm_handler.diagonal = false
   local start, goal = gm_handler.getNode(1,1), gm_handler.getNode(5,3)
diff --git a/Depth_First_Search/Lua/Yonaba/dfs.lua b/Depth_First_Search/Lua/Yonaba/dfs.lua
@@ -52,7 +52,7 @@ local function backtrace(node)
   return path
 end
 
--- Initializes Breadth-Fist search with a custom handler
+-- Initializes Depth-Fist search with a custom handler
 local DFS = class()
 function DFS:initialize(handler)
   self.handler = handler
diff --git a/Depth_Limited_Search/Lua/Yonaba/dls.lua b/Depth_Limited_Search/Lua/Yonaba/dls.lua
@@ -43,14 +43,14 @@ local function backtrace(node)
   return path
 end
 
--- Initializes Breadth-First search with a custom handler
+-- Initializes Depth-Limited search with a custom handler
 local DLS = class()
 function DLS:initialize(handler)
   self.handler = handler
 end
 
 -- Clears all nodes for a next search
--- Must be called inbetween consecutive searchs
+-- Must be called in-between consecutive searches
 function DLS:resetForNextSearch()
   local nodes = self.handler.getAllNodes()
   for _, node in ipairs(nodes) do
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/class.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/class.lua
@@ -0,0 +1,15 @@
+-- Minimalistic class implementation
+
+local class = function(attr)
+  local klass = attr or {}
+  klass.__index = klass
+  klass.__call = function(_,...) return klass:new(...) end
+  function klass:new(...)
+    local instance = setmetatable({}, klass)
+    if klass.initialize then klass.initialize(instance, ...) end
+    return instance
+  end
+  return setmetatable(klass,{__call = klass.__call})
+end
+
+return class
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/gridmap_handler.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/gridmap_handler.lua
@@ -0,0 +1,86 @@
+-- A grid map handler
+-- Supports 4-directions and 8-directions moves
+
+-- This handler is devised for 2d bounded grid where nodes are indexed
+-- with a pair of (x, y) coordinates. It features straight (4-directions)
+-- and diagonal (8-directions) moves.
+
+-- Implements Node class (from node.lua)
+local Node = require 'node'
+function Node:initialize(x, y) self.x, self.y = x, y end
+function Node:toString() return ('Node: x = %d, y = %d'):format(self.x, self.y) end
+function Node:isEqualTo(n) return self.x == n.x and self.y == n.y end
+
+-- Direction vectors for straight moves
+local orthogonal = {
+  {x =  0, y = -1},
+  {x = -1, y =  0},
+  {x =  1, y =  0},
+  {x =  0, y =  1},
+}
+
+-- Direction vectors for diagonal moves
+local diagonal = {
+  {x = -1, y = -1},
+  {x =  1, y = -1},
+  {x = -1, y =  1},
+  {x =  1, y =  1}
+}
+
+-- Checks of a given location is walkable on the grid.
+-- Assumes 0 is walkable, any other value is unwalkable.
+local function isWalkable(map, x, y) return map[y] and map[y][x] and map[y][x] == 0 end
+
+local nodes = {}
+
+-- Handler implementation
+local handler = {}
+
+-- Inits the search space
+function handler.init(map)
+  handler.map = map
+  nodes = {}
+  for y, line in ipairs(map) do
+    for x in ipairs(line) do
+      table.insert(nodes, Node(x, y))
+    end
+  end
+end
+
+-- Returns an array of all nodes in the graph
+function handler.getAllNodes() return nodes end
+
+-- Returns a Node
+function handler.getNode(x, y)
+  local h, w = #handler.map, #handler.map[1]
+  local k = (y - 1) * w + (x%w == 0 and w or x)
+  return nodes[k]
+end
+
+-- Returns manhattan distance between node a and node b
+function handler.distance(a, b)
+  local dx, dy = a.x - b.x, a.y - b.y
+  return math.abs(dx) + math.abs(dy)
+end
+
+-- Returns an array of neighbors of node n
+function handler.getNeighbors(n)
+  local neighbors = {}
+  for _, axis in ipairs(orthogonal) do
+    local x, y = n.x + axis.x, n.y + axis.y
+    if isWalkable(handler.map, x, y) then
+      table.insert(neighbors, handler.getNode(x, y))
+    end
+  end
+  if handler.diagonal then
+    for _, axis in ipairs(diagonal) do
+      local x, y = n.x + axis.x, n.y + axis.y
+      if isWalkable(handler.map, x, y) then
+        table.insert(neighbors, handler.getNode(x,y))
+      end
+    end
+  end
+  return neighbors
+end
+
+return handler
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/iddfs.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/iddfs.lua
@@ -0,0 +1,90 @@
+-- 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 '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
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/iddfs_test.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/iddfs_test.lua
@@ -0,0 +1,86 @@
+-- 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 '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 '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 '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)))
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/linear_handler.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/linear_handler.lua
@@ -0,0 +1,57 @@
+-- A linear boundless 1D space map handler
+
+-- This handler is devised for 1-directional continuous space, where
+-- nodes are represented with consecutive integer values: 0, 1, 2, etc.
+-- Similar to a range (interval) with no bounds.
+-- i.e., the path from 5 to 0 would be 5, 4, 3, 2, 1, 0.
+
+-- Implements Node class (from node.lua)
+local Node = require 'node'
+function Node:initialize(value) self.value = value end
+function Node:toString() return ('Node: %d'):format(self.value) end
+function Node:isEqualTo(n) return self.value == n.value end
+
+-- Finds a specific node in an array
+local function array_find(array, value)
+  for i, v in ipairs(array) do
+    if v.value == value then return v end
+  end
+end
+
+-- Internal cache for all nodes
+local nodes = {}
+local limits = {}
+
+-- Handler implementation
+local handler = {}
+
+-- Inits the search space with bounds
+function handler.init(from, to)
+  limits.low, limits.high = from, to
+  for i = from, to do
+    table.insert(nodes, Node(i))
+  end
+end
+
+-- Creates and returns a Node
+function handler.getNode(value) return array_find(nodes, value) end
+
+-- Returns an array of all nodes in the graph
+function handler.getAllNodes() return nodes end
+
+-- Returns the distance between node a and node b
+function handler.distance(a, b) return math.abs(a.value - b.value) end
+
+-- Returns an array of neighbors of node n
+function handler.getNeighbors(n)
+  local neighbors = {}
+  if n.value - 1 >= limits.low then
+    table.insert(neighbors, handler.getNode(n.value - 1))
+  end
+  if n.value + 1 <= limits.high then
+    table.insert(neighbors, handler.getNode(n.value + 1))
+  end
+  return neighbors
+end
+
+return handler
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/node.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/node.lua
@@ -0,0 +1,16 @@
+-- Node class abstraction
+
+-- This class represents an abstraction of a Node.
+-- It should implemented with additional functions when
+-- writing a custom handler.
+
+-- See dfs.lua comment header.
+-- See custom handlers for reference (*_hander.lua).
+
+local class = require 'class'
+
+local Node = class ()
+Node.__eq = function(a, b) return a:isEqualTo(b) end
+Node.__tostring = function(n) return n:toString() end
+
+return Node
diff --git a/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/point_graph_handler.lua b/Iterative_Deepening_Depth_First_Search/Lua/Yonaba/point_graph_handler.lua
diff --git a/Iterative_Deepening_Depth_First_Search/tags b/Iterative_Deepening_Depth_First_Search/tags
