Enhancing Greedy Policy Techniques for Complex Cost-Sensitive Problems
Camelia Vidrighin, Rodica Potole · InTech eBooks · 2008
Advances in Greedy Algorithms 152 time/memory the search strategy needs to find the solution), optimality (the ability of the strategy to find the best solution, according to the optimization criterion).The next section presents two important search strategies, with their derivatives.Moreover, their performance criteria are discussed and compared.An uninformed search strategy (sometimes called blind search) performs in the absence of knowledge about the number of steps or the path cost from the current state to the goal.The most prominent approaches in this category are breadth first search and depth first search.As opposed to uninformed methods, the informed search strategy employs problem-specific knowledge.The best first search strategy from this category is reviewed, and one of its simplest, yet effective versions, greedy search.The common pattern in all strategies is the expansion of the current node (i.e.considering its successors as candidates for finding the path to goal), while the particularity consists in the order in which the neighbors are evaluated for expansion. Fundamental search strategiesIn the breadth first search strategy the root node is expanded first.In the second step, all nodes generated by it are expanded, in the third step, their successors, and so on.This means that at every step the expansion process occurs for nodes which are at the same distance from the root, and every expanded node in a step is on the boundary of the covered/uncovered region of the search space.Breadth first search considers a systematic approach, by exhaustively searching the entire state space without considering the goal until it finds it.Due to the fact that the whole space is covered, the strategy is complete (i.e. on a finite space, the solution is found, in case there is one).Moreover, the strategy is optimal.The drawback is the large complexity, both in time and space: O(b d ), where b represents the branching factor (i.e.number of descendents of a node) and d the depth of the space.Breadth first search can be implemented using a general search strategy with a FIFO queue for the states (Russell & Norvig, 1995).Uniform cost search comes as a flavor of breadth first search.Assuming a cost function g(n) is considered, breadth first search is modified by expanding the lowest cost node (min g(n)) on the boundary.The default distance to the root, used by the breadth first search is replaced by some specific cost function g(n) (i.e. for breadth first search, g(n)=depth(n) by default).Thus, the systematic approach of covering the space is relaxed to reach the optimal solution faster.Dijkstra's algorithm is a uniform cost search algorithm.The depth first search strategy has a similar approach, but instead of expanding nodes on the boundary, it always expands one node at the deepest level.In case the search reaches a dead end, where no expansion is possible, a node on a shallower level is considered.This way, the "horizontal" approach of covering the states space is replaced by a "vertical" one.Depth first search can be implemented by a general search strategy if a stack is used to keep the states.That is, the FIFO policy is replaced by a LIFO.The major advantage of this strategy is reduced space requirement: O(bm), where m is the maximum depth.The time complexity remains in the exponential domain: O(b m ).The drawback is that the method is neither complete, nor optimal.This is the reason why it should be avoided for spaces with large or infinite max depths.By imposing an upper limit to the maximum depth of a path these pitfalls can be avoided.This modified strategy is implemented by depth-limited search.In this situation, the strategy becomes complete, if the depth of the solution is smaller than the threshold imposed, yet it is still not optimal.www.intechopen.