Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

160 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
2k views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
Jan Hudec's user avatar
  • 658
7 votes
1 answer
1k views

Find maximum in array without comparisons between elements

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: ...
sas's user avatar
  • 201
5 votes
0 answers
478 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
Delgan's user avatar
  • 151
5 votes
1 answer
282 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
neet's user avatar
  • 51
4 votes
0 answers
181 views

Searching a bitonic array with roughly $2\log n$ comparisons

I don't know how to search a bitonic array with roughly $2\log n$ comparisons in the worst case. What I am trying now is to find the maximum integer using roughly $\log n$ comparisons (binary search) —...
ikhvjs's user avatar
  • 141
4 votes
0 answers
115 views

How do search engines implement fuzzy search?

Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses". How is Google able to return near-...
minseong's user avatar
  • 161
4 votes
0 answers
52 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
Jáchym Barvínek's user avatar
4 votes
0 answers
49 views

Any elegant approach to search where users have permissions on subset of records?

I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some ...
Asad Iqbal's user avatar
4 votes
0 answers
831 views

Why are the conditions for optimality different for A* tree and graph search?

I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's ...
Conor Igoe's user avatar
4 votes
0 answers
440 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
coder000001's user avatar
4 votes
0 answers
4k views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
Loves Probability's user avatar
3 votes
0 answers
187 views

Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
zol's user avatar
  • 31
3 votes
0 answers
189 views

Intellij string search and highlight algorithm

I'm searching for an alogrithm that takes two strings, a query and a string that is to be searched for the query. The algorithm should result in a 'found' when the string contains the characters of ...
Philip Müller's user avatar
3 votes
0 answers
515 views

Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters. Storing strings is for sure more space-efficient and ...
Martin Thoma's user avatar
  • 2,360
3 votes
0 answers
58 views

Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
fingerprints's user avatar
3 votes
0 answers
281 views

Post's Correspondence Problem - BFS or DFS?

This question has recently occurred to me as I was working on an implementation of the (Bounded) Post's Correspondence Problem. Basically, which method is generally best for PCP? Breadth-first or ...
Fiery Phoenix's user avatar
3 votes
0 answers
196 views

A case study for search techniques in AI

We are teaching an artificial intelligence class and we need a different case study other than geographical maps (the popular example is the map of Romania) to explain the difference between Breadth-...
Muaad ElSharif's user avatar
3 votes
0 answers
2k views

Estimating size of state space

I have been studying search problems in AI, and I am having some troubles understanding some points in these concepts: State Space: "represents the environment of the problem, the set of all states ...
Salma's user avatar
  • 31
3 votes
0 answers
462 views

How to make an anytime version of alpha beta pruning?

I wish to use alpha beta pruning in a problem with following constraints: Terminal nodes are likely too distant to be found in most searches Instead I want to maximize an evaluation function There ...
Brendan Hill's user avatar
3 votes
1 answer
763 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
dimitris93's user avatar
3 votes
0 answers
546 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
Jonas Köhler's user avatar
2 votes
0 answers
42 views

Quantum search with input as a classical circuit

Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
Loic Stoic's user avatar
2 votes
0 answers
74 views

Understanding MTD-f

In the MTD-f algorithm: ...
Chris's user avatar
  • 123
2 votes
0 answers
38 views

Pairwise intersections of segments in a rectangle

Let V be a set of vertical segments, and H be a set of segments parallel to a line (e.g. a line with slope -1). We want to find a data structure for set S = V ∪ H to find all pairs (v,h) of segments ...
Waseem Akram's user avatar
2 votes
0 answers
226 views

Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
Chemin's user avatar
  • 21
2 votes
0 answers
22 views

SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
Celelibi's user avatar
  • 453
2 votes
0 answers
25 views

SMA*+: f-cost estimation of re-generated nodes

I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
Celelibi's user avatar
  • 453
2 votes
1 answer
179 views

Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
EulerMacaroni's user avatar
2 votes
0 answers
79 views

Smart String search algorithm

I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible. For example, if a query is for the ...
user9041346's user avatar
2 votes
0 answers
81 views

What's a minimum-window alpha beta search algorithm?

I was skimming the Deep Blue overview paper and on page 242 it says: "The search control does not really implement the regular αβ search algorithm. Rather it implements a minimum-window αβ search ...
Robert C. Holland's user avatar
2 votes
0 answers
5k views

Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality,...
mariaprsk's user avatar
  • 401
2 votes
0 answers
38 views

A data structure for efficiently finding nodes relative to other (ex: if a node is earlier in a list than another node)

Suppose we have N elements, which we'll treat as a simple object. Is there a data structure I can use that will allow me to see which node appears earlier based on ...
Water's user avatar
  • 163
2 votes
0 answers
67 views

Reaching local optimality in simulated annealing

I am currently reading about local search techniques. I understand that local search algorithms tend to get stuck in local optima and therefore usually do not find globally optimal solutions. Thus, ...
balderdash's user avatar
2 votes
0 answers
32 views

How to implement a faceted search efficiently

I know Solr and the likes are able to provide faceted search out-of-the-box. But how is faceted search actually implemented technically? How are those engines able to efficiently search for items ...
user avatar
2 votes
0 answers
221 views

Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: $$...
maksadbek's user avatar
  • 139
2 votes
0 answers
72 views

Good examples of consistent/admissible heuristics in non-graphical domains?

I'm preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions. Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic ...
Spark's user avatar
  • 371
2 votes
0 answers
77 views

Find combination of array elements that exceed maximum array element

Say I have an array of integers like so: [2,2,3,5,5,5,5,6,6,7,7,7,7,9,10] I'd like to find all combinations of these values that when summed exceed the maximum (in ...
Cellydy's user avatar
  • 121
2 votes
0 answers
42 views

Avoiding collisions in space and time

Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
Michael O'Brien's user avatar
2 votes
0 answers
42 views

Search algorithm with constraint of proximity to another point

Let us consider a plain search algorithm (Dijkstra being one example) which will calculate the shortest path from A to B. Now introduce the additional constraint that the path must be as close as ...
user149408's user avatar
2 votes
0 answers
63 views

Heuristic Consistency with float multiplications

I'm running A* search with a theoretically consistent heuristic. I'm doing a lot of float multiplications, and I'm not sure how best to ensure that my heuristic remains consistent down to the last ...
user77948's user avatar
2 votes
0 answers
39 views

Dividing a set of goals among two search agents

Say we had two agents and we want them both to traverse a map concurrently. Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be ...
push's user avatar
  • 23
2 votes
0 answers
776 views

How to find all paths with n-distance from a node in a graph with cycles?

I have to find all the paths that have some n-distance from a start node. The destination node is not given. It seems that this problem is very hard to solve because in this scenario I am working with ...
darophi's user avatar
  • 121
2 votes
0 answers
33 views

A* orientation discretization

I have a space with obstacles I wish to find a path through. What I can do is discretize the space into a grid and use A* (or D* or whatever) to find a path through it. I wish to now add orientation ...
Damjan Dakic's user avatar
2 votes
0 answers
638 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
Bilal Akil's user avatar
2 votes
0 answers
111 views

Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
RasmusP_963's user avatar
2 votes
0 answers
586 views

Searching for multiple elements of an array

Suppose we have two sorted arrays $A$ and $B$, and we want to find the indices in $B$ of all elements of $A$. We can do this in $\mathcal O(|A|\log|B|)$ time by simply binary searching $|A|$ times. We ...
user2357112's user avatar
2 votes
0 answers
142 views

What limits the implementation of proximity operators for text indexing and searching?

I was asking on academia.se, if anyone knows scientific search engines offering a proximity operator like Google Web Search does, while Google Scholar Search does not. That's sad, because this ...
Hauser's user avatar
  • 121
2 votes
1 answer
4k views

Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
nick's user avatar
  • 21
1 vote
0 answers
70 views

Difference between Hadlock's algorithm and A* search

I recently read about pathfinding algorithms on grids. It seems two of the most popular are Lee's algorithm and Hadlock's algorithm. Other than the space optimizations that these algorithms employ, it ...
user308485's user avatar
1 vote
0 answers
139 views

Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
Error 404's user avatar