Class: UniformCostSearch

Inherits:
SearchAlgorithm show all
Defined in:
lib/usearchtree/uniform.rb

Instance Attribute Summary

Attributes inherited from SearchAlgorithm

#goal, #history, #space, #start, #traversal, #tree

Instance Method Summary collapse

Methods inherited from SearchAlgorithm

#cost, #initialize, #path

Constructor Details

This class inherits a constructor from SearchAlgorithm

Instance Method Details

#search ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/usearchtree/uniform.rb', line 2

def search
    @list = [[0, @start]]
    until @list.empty?
        @history << @list.clone
        cost, parent_node = @list.shift
        @cache[parent_node.key] = parent_node.key
        @traversal << [cost, parent_node]
        return if parent_node == @goal
        pcost = cost
        parent_node.edges.each do |edge|
            node = edge.node
            cost = edge.cost + pcost
            if not @cache or not @cache.has_key? node.key
                @cache[node.key] = node
                unless @tree.has_key? node
                    @tree[node] = parent_node
                end
                @list << [cost, node]
            end
        end
    end
end