# Questions tagged [search-algorithms]

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

106 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k 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)$ ...
906 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: ...
440 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 ...
302 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 ...
39 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 ...
361 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 ...
3k 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 ...
104 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 ...
48 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 ...
153 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 ...
128 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-...
857 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 ...
296 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 ...
469 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 ...
36 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, ...
33 views

### number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
131 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: ...
26 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 ...
49 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 ...
29 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 ...
334 views

### How to traverse a graph in reverse dfs order

For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
29 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 ...
29 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 ...
35 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 ...
1k views

### Prove that a hamiltonian DAG has a single topological sort

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort". This is pretty much the idea of what I've come along: lets prove by ...
547 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 ...
335 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'...
98 views

### Problem understanding Nilsson's general graph search and A* algorithm

I'm reading several books that present A* algorithm. More precisely, I'm Nilsson's "Artificial Intelligence a New Synthesis" and a textbook on problems of artificial intelligence which is written in ...
584 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 ...
24 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 ...
487 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 ...
105 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 ...
345 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 ...
131 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 ...
21 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 ...
32 views

### Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
24 views

### Structure Preserving Continuous Hash Function

This question was originally posted on super user, but redirected here based on some suggestions. I am completely new with computer science, and not only recently did I run into the notion of hashing....
97 views

### Space complexity of breadth-first search

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor. ...
32 views

### Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
56 views

### Multi Agent Sokoban Solvers state of the art

I am researching into coding a solver for a variant of the Sokoban game with multiple agents, restrictions (eg. colors of stones, goals) and relaxations (push AND pull possible etc.) By researching ...
17 views

### Probabilistic switching between breath-first and depth-first

I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and ...
170 views

### Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
32 views

### Searching Algorithm on Connected Graph

This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math. Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
23 views

### Spatial index search that returns sorted results

I need to perform a spatial index search while also sort the results by one of the dimensions. Backstory: I have a map with lots of 2D objects and when the user interacts with the map I need to ...
20 views

### fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
37 views

### How to use HITS algorithm to rank pages

I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
274 views

### Complexity of bisection method for finding an interval

Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval \$[a_0,b_0]\subset [a,b]...
46 views

### Finding non-overlapping combinations of spans/bitarrays

My first post here so please correct me if my terms are off or needs clarification. Suppose I have several sets of lists of spans. I define a span as a pair of indexes: begin and end index in a ...