Questions tagged [search-algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
Dennis Gahm's user avatar
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?
NotaChoice's user avatar
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 ...
jacoboneill2000's user avatar
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 ...
Aivar's user avatar
  • 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:...
C.C.'s user avatar
  • 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 ...
Pole_Star's user avatar
  • 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....
C.C.'s user avatar
  • 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 ...
sharkeater123's user avatar
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 ...
whoAsked's user avatar
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 ...
Li Haoyi's user avatar
  • 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 ...
geofflittle's user avatar
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 ...
Ally Zane's user avatar
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 ...
Furrukh Jamal's user avatar
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 ...
Florian Suess's user avatar
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 ...
user308485's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Error 404's user avatar
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?
Biswashree Dey's user avatar
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 ...
Loic Stoic's user avatar
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 ...
alexland7219's user avatar
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 ...
aurel1510's user avatar
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'...
cubiii's user avatar
  • 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 ...
user avatar
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 ...
Anters Bear's user avatar
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), ...$ ...
Andrey Godyaev's user avatar
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: ...
VLC's user avatar
  • 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. <...
YogoWafel's user avatar
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_{...
2080's user avatar
  • 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 ...
giofrida's user avatar
  • 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 ...
Tita's user avatar
  • 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,...
HourenGorl's user avatar
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^\...
The Pointer's user avatar
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 ...
The Pointer's user avatar
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 ...
The Pointer's user avatar
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 ...
requiemman's user avatar
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 ...
Saku's user avatar
  • 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 ...
Lars Gebraad's user avatar
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 ...
Sam's user avatar
  • 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 ...
Galen's user avatar
  • 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] >...
JsonResponse's user avatar
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 ...
Miss Mulan's user avatar
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²) ...
David Hoyos's user avatar
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: ...
Solaxun's user avatar
  • 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 ...
spooni's user avatar
  • 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 ...
yosmo78's user avatar
  • 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$, ...
user1231231hd's user avatar
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 ...
Liam Kelly's user avatar
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, $\...
Xavier Taylor's user avatar
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', ...
Surprised Seagull's user avatar
2 votes
0 answers
65 views

Understanding MTD-f

In the MTD-f algorithm: ...
Chris's user avatar
  • 123

1
2 3 4 5
14