Questions tagged [searching]
For questions about various search algorithms.
138
questions
0
votes
0
answers
45
views
Find upper and/or lower bounds for the least prime $p$ such that $p^n + k$ is the product of $n$ distinct primes
Well, first of all, happy new year to everyone.
I am trying to solve the following problem: "Let $k$ be a fixed natural number. Find the least prime $p$ such that there exists a natural number $...
- 28.2k
1
vote
1
answer
54
views
Median of medians algorithm [closed]
My question is I don't understand how we determine the constant in T(T(n/3), T(n/5)). For example, we divide elements into 9 groups and get a formula like this
T(n) <= T(n/9) + T(7n/9) + O(n)
I don'...
- 13
0
votes
1
answer
23
views
Need a concise way to query a database with limited filters
I have two observers identifying pets - Sam and Cindy. For each pet, Sam and Cindy have to say what kind of pet they see (dog, cat, leprechaun, etc.). They enter their results into a database and I ...
- 1
0
votes
0
answers
16
views
Fast Orthogonal Vector Lookup
Let's say I have a (very large) set of embeddings $\mathbf{v_i} \in \mathbb{R}^d$, and a query embedding $\mathbf{q} \in \mathbb{R}^d$. I know there are a number of fast approximate nearest neighbour ...
- 1
0
votes
0
answers
33
views
Seeking math category for ranking example
I’m searching for the correct math category for a problem so I can hire a developer, but need to know the general approach (I hope math exchange is an appropriate forum for this question)
This ...
- 109
0
votes
0
answers
15
views
How can I read in the following definition of A star search:
I would like to get a more interpretable definition of the following algorithm. I would appreciate any help here. Thanks!
- 103
2
votes
1
answer
60
views
Do weights of edges affect the shortest path in 2D grid undirected graph
I'm struggling with the shortest path finding problem in a road network in my program:
Given a map, the roads are arranged as a 2D grid, and the roads intersect to form a series of nodes. There are ...
- 23
0
votes
0
answers
45
views
alpha beta pruning for multiple players
I have just finished implementing the min-max algorithm for a three-player game. I currently want to implement alpha-beta pruning but I, unfortunately, am unable to find any clear methods on how to ...
0
votes
0
answers
23
views
finding the first intersection between a 3d line and set of points
I need to solve this
I have a line in space, starts with (X_0,Y_0,Z_0) and defined by angles θ,φ as:
x=r sinθ cosφ;
y=r sinθ sinφ ;
z=r cosφ
we also have a huge set of points distributed in ...
- 1
1
vote
0
answers
98
views
Probability of linear search with repeated elements.
I am trying to find the probability that a linear search on an array of size n takes j comparisons. We are looking for the element x and there are k x's in the array where 0 < k < n. I tried ...
- 21
1
vote
1
answer
106
views
Algorithim to choose comparison pairs for topological sorting
I'm trying to find or create an algorithm to roughly sort arbitrary objects using pairwise comparison where the only concern is minimizing the number of comparisons. So my question is essentially is ...
0
votes
0
answers
60
views
A root-find algorithm for the first-zero of a discontinuous function?
I'm working on a problem at work that requires me to search for the first date (x) that a financial model returns a value greater than zero (y>0).
Our current approach is simple. Start a guess-and-...
- 1
1
vote
0
answers
247
views
Calculate all possible paths in graph
I have a number of graphs that look similar to this:
Graph
In this image, there are 4 levels and 4 node per level: Green is level 1, Blue is level 2, Pink is level 3 and Yellow is level 4.
Graph - ...
0
votes
1
answer
55
views
Number Of Global Optima in Single Solution Metaheuristics
I am reading the book "Metaheuristics From Design to Implementation" written by El-Ghazali Talbi and on page 91, in the "Single-solution based metaheuristics" section, he says ...
- 181
1
vote
0
answers
36
views
Searching a vector space (ish?)
I come from a computer science background so please forgive any math transgressions I make.
I will try to describe what I'm looking for as best as I can.
I've been looking into methods of searching a ...
0
votes
0
answers
45
views
Finding an optimal solution in a tile painting game
images are posted as links because I don't have enough points, sorry
The Problem
Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal ...
2
votes
1
answer
87
views
Is discrete quasiconvexity just as good as discrete convexity?
(I will frame the discussion below in terms of concavity because it suits the examples I have on hand, but the same arguments apply to convexity, too.)
Consider a function $p(h)$ defined for $h$ on a ...
- 1,215
0
votes
0
answers
759
views
What are some real life examples of UCS (Uniform Cost Search)
Studying search algorithms I've been fascinated by UCS and its similarity to the Djikstra algorithm in some cases. Has anyone any real life example of a possible use of this UCS algorithm to solve ...
0
votes
2
answers
78
views
All possible triangles in terms of edges in RCCP
NB: This question was first posted in Stack Overflow, it has been moved here on suggestion.
I'm stuck on finding an efficient algorithm to the following problem:
Given a complete undirected graph G ...
1
vote
1
answer
215
views
How can I generate a pruning table for tetrads?
I'm currently creating a Rubik's Cube Solver and am having some difficulty generating pruning tables. Pruning tables contain information that is used to prune search tree branches, exponentially ...
- 19
6
votes
2
answers
194
views
Graph puzzles: Constructing graphs from tiles
There is a vast literature on the reconstruction conjecture which says that two graphs with the same deck $D$ are isomorphic. The deck is the multi-set of vertex-deleted subgraphs of a graph (which ...
- 17.7k
0
votes
0
answers
87
views
Prove we can't Finding an element $A[i]=i^2$ in sorted array with $\log n$ time.
We are given a sorted array$A[1..n]$, we are searching to find an
element that $A[i]=i^2$ in array. How we can prove that we can't do it in
$O(\log n)$?
My idea:
do a linear search in array in $O(n)$...
- 331
0
votes
1
answer
157
views
Find an element that repeated $\frac{n}{5}$ times in sorted array
We are given a sorted array$A[1..n]$, we are searching to find an
element that repeated $\frac{n}{5}$ times in array.How we can do it in
$logn$?
I find an solution in $O(n)$,with checking each ...
- 331
0
votes
1
answer
106
views
Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
- 141
0
votes
0
answers
67
views
Binary Search average time complexity
I'm looking for explanations for this solution.
I have tried and found the solution in book Art of Computer Programming. Volume 3. Sorting and Searching. Second Edition but this didn't help me at all. ...
- 1
1
vote
1
answer
193
views
Efficient directional nearest-neighbor search among rectangles
I have a large set of rectangles with random orientation and size. Say up to $10000$ rectangles, which are non-overlapping.
For every rectangle, I need to find the nearest compatible neighbor. Two ...
user65203
1
vote
2
answers
40
views
Searching/Sorting Algorithm
I just started studying algorithms and data structures and came across this problem:
Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in ...
- 105
1
vote
1
answer
289
views
Binary Search, probability of element being found
What is the probability of an element being found? What would the math probability formula look like for an element being found? What is the probabilistic analysis of an element being found?
I have ...
- 111
3
votes
1
answer
373
views
Can you find an invertible submatrix?
Given an $m\times n$ matrix $\mathbf{A}$ $(m\gneqq n)$, I'm trying to efficiently find all $n\times n$ invertible submatrices using a computer. Equivalently, I'm trying to find which rows of $\mathbf{...
- 16.6k
1
vote
1
answer
55
views
Find all traces satisfying a set of linear temporal logic (LTL) formulas
I want to compute all finite traces up to a given length that satisfy a set of linear temporal logic formulas. Does such an algorithm exist?
- 11
0
votes
2
answers
584
views
Finding initial lower and upper bounds for bisection search for polynomial's roots
When computing the nth root of a polynomial equation using bisection search, how does one find the upper and lower bounds of where to search?
Is there some kind of formula to bound the nth root to a ...
user739402
5
votes
1
answer
1k
views
Searching for rock-hard integers.
For integer $k\geq 0$ written $d_jd_{j-1}\dots d_1$, where $d_i$ are single-digit integers, define
$$R(k) :=
\begin{cases} d_j^{d_1}d_{j-1}^{d_2} \dots d_{j/2}^{{d_{j/2 + 1}}}, & j \text{ is ...
0
votes
0
answers
23
views
Searching with a 1D car?
Consider the task of programming a 1D car starting on point $0$.
The car drives 1 km / min ( to both left and right).
The task is to find a coin at an unknown integer distance $x$ (in km) from the ...
- 13.7k
1
vote
1
answer
47
views
Difficulty understanding the relation between the representation of a number and the time complexity of searching for (0, N - 1)?
Please refer here to the direct resource that I don't understand.
Let's take the number $X = 245436$, we can represent the following as $$X = 2 \times 10^5 + 4 \times 10^4 + 5 \times 10^3 + 4 \times ...
- 261
1
vote
0
answers
29
views
Is it okay to not provide a whitelist when using the Hill-Climbing algorithm?
So, I'm trying to use Hill-Climbing for a Bayesian learning network. For some reasons, I do not know all of the variables that I'm going to use and hence, I cannot provide a whitelist or a blacklist ...
- 11
1
vote
0
answers
25
views
Which uniformed search algorithm is the best here?
So I have an exercise like this where I have to choose the best strategy. I wonder here which one is the best:
A robotic engineer wants to add movement planning ability to a small
mobile robot. ...
- 11
1
vote
0
answers
114
views
Is this how you calculate the reservation price?
I was wondering if you could help me make sure I have things correct. Weitzman (1979) (Optimal search for the best alternative) considers a decision maker that is facing n boxes, each box has ...
- 11
2
votes
0
answers
84
views
Do "randomized single player problems" always have optimal strategy? How to find one?
What I mean by a "randomized single player problem" is roughly the following:
Certain information of the game is derived from a known random distribution (can assume uniform) and is hidden from the ...
- 21
12
votes
1
answer
141
views
Searching for a point on the real line
A pin is dropped at a random point $p$ on the real line, with $p$ determined from a normal distribution with mean $0$ and standard deviation $\sigma$. You are dropped on the real line at $x=0$ and ...
- 223
3
votes
3
answers
7k
views
How to apply DFS on a disconnected graph.
I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph.
How would I go through it in DFS?
My current ...
- 31
3
votes
2
answers
716
views
Finding Lowest Elevation Path Between Two Points
Let's say I have a matrix of values that represent heights with function $f(x,y)$ and I am trying to find the "lowest value path" beween two points. So this would be the reverse of hill climbing, as ...
- 15.5k
0
votes
1
answer
2k
views
Binary Tree mathematical equation for number of internal nodes [closed]
I was wondering how does this equation:
$$\frac n2 + \frac n4 + \frac n8 + \dots + 1$$
go to:
$$1 + 2 + 4 + \dots + \frac n2$$
and then to:
$$\sum_{i=0}^{h-1} 2^i,\; \text{where $h$ is the height ...
- 13
3
votes
0
answers
91
views
Lost in a Forest Problem 3d Verision: Point and Plane
The lost in a forest problem is famous, specifically see this problem. The problem takes place in the plane. Consider the following 3d version. There is a point $p \in \mathbb{R}^3$ and a plane $P$ ...
user581970
2
votes
1
answer
35
views
Restricted query problem
I am considering a problem which seems very classic but have no idea where to find the related results. Any help or comment will be appreciated.
Given a non-empty set $S$, a set $Q$ of the subsets of ...
- 91
2
votes
1
answer
474
views
What is the best way to guess a number in a limited number of guesses?
A random integer is picked from 0 to 100. You can make 5 guesses at what the number is, and after each guess, you are told if your guess was too high or too low. What strategy maximizes your ...
-1
votes
1
answer
117
views
Open Nodes More Than Twice during A* Search?
This space graph fulfilled the monotone condition of :
h(v) ≤ h(u) + c(v, u) and h(t) = 0
But during A* searching in a space graph, I have one a node (y) which ...
- 123
1
vote
1
answer
251
views
Breadth first search with bidirectional edges
Since this is a Breadth first search I would say that the answer would be S-B-E-F-G since it is the first path to get searched ...
user504783
0
votes
0
answers
145
views
A* search at cost $g(n)=0$
Wouldn't the answer be Greedy Best First Search since the path cost $= 0$?
Which search strategy is simulated by the $A*$ search algorithm if we take cost function$ g(n) =
0$ if one assumes no ...
user504783
1
vote
0
answers
55
views
Shrinking size of search space using only conjunctions in machine learning
In Chapter 1 of Kubat's An Introduction to Machine Learning he introduces the problem of classifying pies as positive or negative based on $5$ attributes, with $3, 2, 3, 2$ and $3$ possible values ...
- 36
0
votes
2
answers
4k
views
Find a unique path in a graph that's colored in red and blue
I was given the next assignment:
Let $G=(V,E)$ be an undirected graph and connected,such that every $e\in E$ has a color-blue or red.
Given the same $G$ and some $a,b\in V$ ,construct an efficient ...
- 613