Questions tagged [search-algorithms]

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

100 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
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)$ ...
6
votes
1answer
831 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: ...
5
votes
0answers
394 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 ...
5
votes
0answers
288 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 ...
4
votes
1answer
88 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 ...
4
votes
0answers
38 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 ...
4
votes
0answers
344 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 ...
4
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
91 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 ...
3
votes
0answers
122 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-...
3
votes
0answers
658 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 ...
3
votes
0answers
269 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 ...
3
votes
1answer
13k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
3
votes
0answers
459 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 ...
2
votes
0answers
114 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: $$...
2
votes
0answers
23 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 ...
2
votes
0answers
46 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 ...
2
votes
0answers
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 ...
2
votes
0answers
300 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 ...
2
votes
0answers
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 ...
2
votes
0answers
28 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 ...
2
votes
0answers
34 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 ...
2
votes
0answers
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 ...
2
votes
0answers
520 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 ...
2
votes
0answers
275 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'...
2
votes
0answers
95 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 ...
2
votes
1answer
559 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 ...
2
votes
0answers
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 ...
2
votes
0answers
458 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 ...
2
votes
0answers
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 ...
2
votes
0answers
314 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 ...
2
votes
0answers
78 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
2
votes
0answers
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 ...
1
vote
0answers
31 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 ...
1
vote
0answers
14 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....
1
vote
1answer
71 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. ...
1
vote
0answers
16 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
14 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 ...
1
vote
1answer
112 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, ...
1
vote
0answers
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, ...
1
vote
0answers
21 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 ...
1
vote
0answers
18 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
1
vote
0answers
24 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 ...
1
vote
0answers
177 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]...
1
vote
0answers
41 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 ...
1
vote
0answers
32 views

What is the meaning of the “*” in names of various learning/search algorithms?

For example, consider L* algorithm for learning a regular language, or A* search algorithm. What do these names - in particular, the star character - mean? It looks like it might be the case that the ...
1
vote
0answers
125 views

Feeding real-time data and binary search algorithm termination

This question was asked in our exam long a go and I don't remember exact words. The scenario was, Initially you are given a set of finite data to start with, and a key value (which you have to find ...
1
vote
0answers
42 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...