New answers tagged search-algorithms
2
Since you already implemented IDA$^*$ you certainly understand why it expands more nodes than A$^*$, i.e., it starts from the start state with a new depth-first traversal in each iteration. Note first that, the overall number of nodes visited by IDA$^*$, while necessarily larger than A$^*$ is not that much larger. The reason is that the number of nodes at ...
1
An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries. In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do ...
1
Look at maximum interval scheduling.
Assign an interval $(s_i, t_i)$ to each performer, for $i=1,\dots,N$, meaning that the performance starts at time $s_i$ and has a duration of $t_i - s_i$.
Assume for now that all the intervals are sorted by their end time.
Just for simplicity assume also that all times are distinct (this assumption is unnecessary).
Your ...
1
This is a simple Interval Scheduling Maximization problem, which can be solved in O(n log(n)) time via a simple greedy algorithm. The trick is to sort performances according to end time and not start time.
Here is the description of the solution found on the Wikipedia page I linked:
Several algorithms, that may look promising at first sight, actually do ...
1
Imagine your tree looks as follows:
You are looking for the leaf with minimum label and the label of each internal nodes represents the heuristic value associated with the subtree routed at that node.
If the width of your beam is just $1$, you start at the root and then go $\rightarrow 5\rightarrow7\rightarrow0$.
If the width of your beam is $2$, you ...
2
Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs.
Even if it is not directly related to your question, I could not avoid citing the following paper:
F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A ...
1
One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function ...
4
The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach.
A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a ...
0
If you don't want the exact nearest neighbour but would be satisfied with finding points that are not too far off, then you should take a look at Approximate nearest neighbour search.
Wikipedia suggests the following approaches:
Locality-sensitive hashing
Best bin first
Balanced box-decomposition tree
Depending on the distribution of your data, not all ...
0
Suppose there are n pixels on the screen.
We add the neighbours onto the queue only if they haven't yet been processed.
This way a pixel is added onto the colouring queue only if it hasn't been coloured yet.
Thus a pixel can be added onto the queue for a maximum of 1 time.
So if there are n pixels, then at most n additions would be done to the queue and ...
Top 50 recent answers are included
