New answers tagged

0

According to Artificial Intelligence: A Modern Approach 4th edition in IDA* the cutoff is the $f$-cost($g+h$); at each iteration, the cutoff value is the smallest $f$-cost of any node that exceeded the cutoff on the previous iteration. In other words, each iteration exhaustively searches an $f$-contour, finds a node just beyond that contour, and uses that ...


0

The answer to my question can be found in the paper Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm (2011), in particular section Similarities of DA and UCS, so you should read this paper for all the details. DA and UCS are logically equivalent (i.e. they process the same vertices in the same order), but ...


1

I was struggling with the same question. This is what I came up with after thinking it through. With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and ...


1

It depends on the stopping condition. If the stopping condition is "stop as soon as any vertex is encountered by both the forward and backward scan", then bidirectional uniform-cost search is not a correct algorithm -- it is not guaranteed to output the optimal path. But it is possible to adjust the stopping condition to make bidirectional ...


4

Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$: Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next is $\frac{1}{4}$, the following is $\frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. ...


0

As stated in my other answers here and here, the space complexity of these search algorithms is calculated by looking at the largest possible number of nodes that you may need to save in the frontier during the search. Iterative deepening search (IDS) is a search algorithm that iteratively uses depth-first search (DFS), which has a space complexity of $O(bm)$...


0

Norvig & Russell's book (section 3.5) states that the space complexity of the bidirectional search (which corresponds to the largest possible number of nodes that you save in the frontier) $$O(2b^{d/2}) = O(b^{d/2}).$$ The intuition behind this result is that (as opposed to e.g. uniform-cost search or breadth-first search, which have space (and time) ...


1

UCS is optimal (but not necessarily complete) Let's first recall that the uniform-cost search (UCS) is optimal (i.e. if it finds a solution, which is not guaranteed unless the costs on the edges are big enough, that solution is optimal) and it expands nodes with the smallest value of the evaluation function $f(n) = g(n)$, where $g(n)$ is the length/cost of ...


0

The space complexity of the breadth-first search algorithm is $O(b^d$) in the worst case, and it corresponds to the largest possible number of nodes that may be stored in the frontier at once, where the frontier is the set of nodes (or states) that you are currently considering for expansion. You can take a look at section 3.5 (page 74) of the book ...


Top 50 recent answers are included