Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [search-algorithms]

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

0
votes
0answers
17 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, i=1..N} defined by their vertex coordinates (x,y) and a convex polygon P, also defined by its vertex coordinates, find all polygons S_i ...
3
votes
1answer
30 views

Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...
1
vote
1answer
26 views

Two Minimax AIs playing against each other

I am trying to have my Minimax AI chess players play against each other. I was a bit confused about an implementation detail. Let's call black my first minimax AI ...
6
votes
1answer
77 views

Index matching algorithm without hash-based data structures?

I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time. Given two arrays $...
1
vote
1answer
40 views

What is a search problem?

I'm looking for a formal and broad definition. Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a ...
1
vote
2answers
41 views

Term for the tree of all paths starting from a given vertex in a graph

What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex? This is the tree that is implicitly or explicitly constructed when ...
1
vote
2answers
69 views

Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
2
votes
1answer
20 views

Name of double sided search algorithms

I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
2
votes
2answers
23 views

Measuring the Probability of Error for a Potential BPP Algorithm

Problem Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space ...
0
votes
0answers
12 views

Identify row or column addition or deletion in a table

I'm looking for a solution which can able to identify the any row or column addition or deletion in a table of numbers. What I have thought of as of now by using the LCS i.e. "Longest common sub-...
2
votes
1answer
65 views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
0
votes
1answer
18 views

Sorting on non-linear topology

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
1
vote
0answers
20 views

How to find all numbers that there distance from given point are less or equall to integer n? [closed]

Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$? Example: suppose we ...
0
votes
0answers
55 views

Does BFS or DFS perform better to solve the Towers of Hanoi problem?

Use the DFS and BFS algorithms to solve the Towers of Hanoi problem. Which performs better and why? Towers of Hanoi Towers of Hanoi visualization When I think of the Towers of Hanoi problem, I ...
1
vote
0answers
27 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, ...
0
votes
2answers
64 views

How to calculate time complexity of a randomized search algorithm?

Example: Finding an element from a sorted array Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
4
votes
1answer
48 views

Grover's Algorithm result when the desired element is not present

What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?
1
vote
2answers
59 views

Detailed step of Dijkstra's algorithm performance analysis

Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf about the performance of Dijkstra's algorithm on Page 118, we are given: 4.4.3 Running time At the level of abstraction of Figure ...
0
votes
0answers
105 views

Egg dropping problem

Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...
2
votes
0answers
88 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: $$...
0
votes
0answers
20 views

How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
2
votes
0answers
17 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 ...
0
votes
0answers
16 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
1
vote
0answers
19 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 ...
0
votes
1answer
21 views

Keywords/terminology for using “extra” information in search problems?

I am trying to find references on a particular idea, but I don't know which keywords to use in a google search. the idea is: as an example, consider graph search. maybe the problem is: find a path ...
1
vote
0answers
15 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
0
votes
2answers
60 views

Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
0
votes
1answer
28 views

Optimality of A* search

I use the A* search algorithm to to search for the shortest path from S to G. The evaluation function is $f(n) = g(n) + h(n)$. Since node A and B have the same estimated total cost, I choose to go ...
0
votes
0answers
44 views

8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once. But ...
3
votes
1answer
553 views

How binary search works in real world scenario?

In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers. But in real world, we may search for a name of an employee ...
1
vote
1answer
94 views

A* Search Algorithm Implementation with Priority Queue

I've got a question regarding the A* search algorithm's implementation. According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
0
votes
1answer
41 views

String Search - how to find the “most” accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
1
vote
1answer
58 views

provably optimal search algorithms?

In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-...
1
vote
0answers
17 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
54 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]...
2
votes
0answers
31 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
1answer
50 views

Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
1
vote
1answer
232 views

KMP - longest palindromic prefix

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word. I've seen this algorithm used for determining if a word is rotation of ...
0
votes
1answer
63 views

Visit all vertices of a graph

I need to find the fastest route passing in all vertices Each vertex is a class. I can choose the number of classes for semester. Some classes have prerequisites (A and B need to be done one semester ...
1
vote
1answer
48 views

Algorithmic Design to Undo Rotation of Array

An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$. That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $...
3
votes
2answers
49 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
1
vote
0answers
29 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
1answer
43 views

Duplicate elements in Queue for BFS Maze Algorithm

I'm fairly new to studying data structures and algorithms. I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and ...
0
votes
1answer
163 views

Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
0
votes
2answers
69 views

A data structure to do a specific lookup fast

I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items ...
0
votes
0answers
16 views

Search techniques to find desired output with complex interdependencies

I am trying to generate output consisting of three-tuples (A,B,C), where A,B, and C are three different datatypes representing different values. I also have a collection of functions $f_i \in F$ ...
0
votes
0answers
54 views

Prove lower bound of searching algorithm on Young Tableau

I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!
2
votes
1answer
43 views

Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?

So this is my question. I am trying to understand this part of the book: At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just ...
4
votes
1answer
55 views

Subgraph isomorphism on star multi-graphs with labelled edges

My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...