New answers tagged search-algorithms
2
Note that a path from the root to $heap[i]$ is in the sorted order. Moreover, the path length is $O(\log n)$. You just need to do binary search on this path. For that, you need to access the $i^{th}$ ancestor of any node in the heap in $O(1)$ time. Assuming $1$ based indexing, the $1^{st}$ ancestor of $heap[i]$ is located at $\lfloor \frac{i}{2} \rfloor$ ...
1
I believe you can use any algorithm for heuristic search. On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.
3
In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this).
However, if you know more about the structure of the array, there are plenty of things you can do.
For example, imagine the array has the following property: its elements are sorted increasingly up to a ...
1
The value that you've got is the number of searches required in the worst case by binary search. Each function call is responsible for only 1 search. And your recurrence relation justifies that. So the recurrence relation you wrote is for the number of searches. Indeed we require $\log n +1$ searches if it's a worst case. Take any $n$, say $n=7,8$, and try ...
1
I think you might have misunderstood the heuristic function. It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$. The closer this estimate is to the true value, the better A* will perform.
The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $...
1
They can't possibly be on the same scale throughout the search, if by that you mean that $g(n) \approx h(n)$ for every node encountered near the search. Near the start, you'll have $g(n) \approx 0$, so $g(n) \ll h(n)$. Near the goal node, you'll likely have $h(n) \approx 0$, so $h(n) \ll g(n)$.
On the other hand, it is possible to have the range of values ...
0
No. Assume towards contradiction that it is true, then ignore $f$ completely (choose some $f$ which is constant)
Then, what your statement would say is that $h,g$ are admissible $\implies h+g$ is admissible.
In particular, for any admissible function $g$, choose $h=g$, and your statement implies $2g$ is admissible. Apply the statement again to get that $3g$ ...
1
You can answer the first question with binary search. Lets consider you're now discussing the interval $[l, r]$, and $m = \frac{(l + r)}{2}$. If $A[m] = m$, you have found an answer and you shall stop the search. If $A[m] < m$, then the answer must be in the interval $[m + 1, r]$, because if $i \le m$, then $A[i] \le A[m] - (m - i) < m - (m - i) = i$ (...
2
Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF ๐น, doesnโt mean that ๐=๐๐, because the algorithm could output a Boolean formula ๐บ such that if ๐น is unsatisfiable, ๐บ is a minimal unsatisfiable core of ๐น; if ๐น is satisfiable, ๐บ is a subset of the clauses of ๐น and it is satisfiable. Therefore, the output of ...
1
This is not the right place to ask for people to review your code, but it's perfectly normal for Dijkstra's algorithm and Uniform Cost Search (BFS) to return different paths. Indeed, a shortest path on a weighted graph is not necessarily the one that uses less edges.
As an example you can consider the graph $G=(V,E)$ with $V=\{s,u,v\}$, $E=\{(s,u), (u,v), (s,...
Top 50 recent answers are included
