Questions tagged [search-algorithms]
Algorithms for finding an element in some specified data-structure (most commonly, in a tree).
693
questions
0
votes
0
answers
22
views
Manhattan distance always less node expansion than misplaced tiles heuristic?
I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles.
I generated data that said that for a particular random board, misplaced tiles did less node ...
0
votes
1
answer
29
views
Time complexity of search algorithms?
Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ?
If so, how do we prove it?
- 101
5
votes
5
answers
3k
views
Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
2
votes
2
answers
81
views
Any text similarity algorithms for substrings?
I need to implement simple search on Python package names and I'm struggling with ranking the results. Considered Levenshtein distance, but it would give too low ranking for matches which contain the ...
- 285
1
vote
1
answer
68
views
Faster selection algorithm for small order statistics
SELECT(A,p,r,i) is an algorithm that
partitions $A[p:r]$ around the $i$ th order statistic ie. in the output, we have $l\in A[p:p+i-2]<A[p+i-1]< h\in A[p+i:...
- 129
0
votes
0
answers
8
views
The Multi-Room Muddy Forehead Puzzle with Varied Color Perception
Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
- 129
0
votes
2
answers
124
views
Minimum number of comparisons to find $2$nd smallest element
Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$
comparisons in the worst case. (Hint: Also find the smallest element.) [1]
I tried but I have no idea how to, e....
- 129
0
votes
0
answers
39
views
Graph Search Algorithms that are practically fast on dense graphs
I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
0
votes
0
answers
21
views
Is this Greedy Search or Uniform Cost Search?
In the below Image, S is the starting point and E is the end point.
Image link
Now, the Title of the video says that its a Greedy Best First Search.
However, while browsing stackoverflow, I came ...
- 1
1
vote
1
answer
30
views
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
I am trying to write a program to analyze Java programs and figure out the
transitive closure of the ...
- 125
0
votes
0
answers
37
views
Data structure for arithmetic logical queries
Abstract Problem
I'm looking for a data structure that will (1) allow me to make queries of the form A.x - B.x <= 0.1 AND A.y + B.y >= C.y + D.y and (2) allow ...
- 161
0
votes
1
answer
71
views
How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem.
I have elements from 1 to n and I am trying to cover all of the elements using the ...
- 11
0
votes
0
answers
20
views
Help regarding alpha-beta search
I am self teaching myself basics of AI, from the internet, I am trying to do pset3 of MIT's 6.034 here at
https://ocw.mit.edu/courses/6-034-artificial-intelligence-fall-2010/pages/assignments/
the ...
0
votes
0
answers
20
views
Cutting trees using depth bounded search?
I'm looking at writing a FPT (fixed parameter tractable) algorithm that takes in a tree; $T = (V, E)$. And a set of pairwise distinct vertex pairs (from $V$), $H$ and a $k>0$. Does there exist a ...
- 101
1
vote
0
answers
38
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 ...
- 215
2
votes
1
answer
80
views
Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time.
If $f(-1)<0$ and $f(1)>0$, then by ...
- 5,720
1
vote
0
answers
80
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 ...
- 11
0
votes
0
answers
17
views
Zero Knowledge Protocol for Search Problem
Does anyone know any zero-knowledge protocol that addresses the search problem, i.e. finding the output to a query without revealing the query or any other output?
2
votes
0
answers
40
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 ...
- 213
2
votes
1
answer
164
views
Why is this proof that CHESS is in EXPTIME correct?
I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
- 23
3
votes
1
answer
111
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
0
votes
0
answers
39
views
Performing fuzzy search queries on a large database of strings
I have a large database of strings (~10 million)
I need to perform fuzzy search queries which would find the best match inside that database.
The best match meaning the one that has the highest 'score'...
- 113
0
votes
0
answers
59
views
What is the difference between Local Beam Search and Stochastic Beam Search?
I know that both of them select K randomly, and then choose the best K, as I understand the ...
user157493
1
vote
1
answer
156
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 129
1
vote
2
answers
122
views
Perfect ordered hash function on ordered sequence
I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.:
$(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$
...
- 287
0
votes
0
answers
31
views
CPU limit for bitap algorithm bitmask
We have bitap (shift OR) algorithm that searches for a substring in a text.
Bitap algorithm uses bit masks, so that it can perform bitwise operations very fast with the help of CPU.
For example:
...
- 101
1
vote
2
answers
370
views
Ordered sequence with logarithmic insert and remove
Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity.
<...
- 13
0
votes
3
answers
89
views
Given two sets of coordinates, find out neighboring ones
I have two sets of 2-dimensional coordinates on an integer grid, $A$ and $B$
$A = \{(x_{A1},y_{A1}), (x_{A2}, y_{A2}), (x_{A3}, y_{A3}), \dots\}$
$B = \{(x_{B1},y_{B1}), (x_{B2}, y_{B2}), (x_{B3}, y_{...
- 191
2
votes
1
answer
300
views
Understanding Rabin-Karp's rolling hash computation
Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
- 183
0
votes
1
answer
128
views
How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.
What ...
- 225
0
votes
1
answer
18
views
Algorithm to find best order for items on pages with a fixed height
I am looking for an algorithm to find the best order of items to fit on pages.
Consider the following case, we have a page with the height = 300
We have images with the following heights - [150,200,...
1
vote
1
answer
100
views
If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?
I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\...
- 203
0
votes
0
answers
71
views
How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?
I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following:
Greedy search minimises estimated path-cost to goal.
But it's ...
- 203
0
votes
0
answers
75
views
How do these search algorithm diagrams work? How am I supposed to interpret them? And what algorithms do those last three represent?
I was shown these diagrams in the context of search algorithms. The green tile shows the initial state, and the orange tile shows the goal state. I am told that each option shows a path each search ...
- 203
1
vote
0
answers
51
views
Is there a comprehensive list of searching algorithms for sorted (and possibly unsorted) arrays available anywhere?
Classic searching algorithms such as binary searching and dictionary searching search sorted arrays based on a given element and make estimations on their own. What I'm looking for is a list of more ...
- 11
0
votes
1
answer
30
views
Hill climbing method searching special polynomial equations
I have system of two polynomial two variables, second order; monomials are {${1,x,y,x^2,xy,y^2}$}
I want find special systems of polynomials: two or more roots in specified range, two root close to ...
- 141
0
votes
0
answers
8
views
Optimising for many points in a monotone function
I'm trying to optimise (to a certain precision) a monotonic function for many points (100+). I know a-priori that the function is continuous, with some parts zero derivative. I know that all points ...
1
vote
1
answer
118
views
search with inadmissible heuristics
I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the ...
- 163
0
votes
0
answers
34
views
Iterative algorithm for assembly index? [duplicate]
DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
- 125
1
vote
2
answers
66
views
Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays
Consider an array A[1..n] that first increases up to some point p then it decreases until some point q and then increases again. That is A[k] < A[k + 1] for all k in [1..p] and [q..n] and A[k] >...
- 57
1
vote
2
answers
82
views
Existence of some search algorithms
The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$.
The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$
So in order to be able to use a search ...
- 119
0
votes
2
answers
53
views
Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)
I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than
O(N²)
...
0
votes
1
answer
112
views
Simulated Annealing - Intuition
Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below:
...
- 121
1
vote
1
answer
85
views
$O(n \log n)$ Algorithm for first Train Problem
On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
- 11
1
vote
1
answer
168
views
A nearest neighbor data structure for meshes
I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
- 177
1
vote
0
answers
47
views
Search algorithm with at most a constant $k$ failed accesses [duplicate]
Let $A$ be an array sorted in non-increasing order. Let $m$ be a natural number. For example, let $m = 10$. We want to find the index $i$ such that $A[:i]$ contain elements less than or equal to $m$, ...
0
votes
1
answer
119
views
Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?
I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
- 101
1
vote
1
answer
92
views
Efficient search of a large set of documents to find documents that only contain a particular set of words
Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language.
Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
- 111
1
vote
0
answers
65
views
Unusual version of a binary search algorithm
For one dimensional, continuous binary search most effective algorithm would remember boundaries.
For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
2
votes
0
answers
65
views
