# Questions tagged [searching]

For questions about various search algorithms.

143 questions
Filter by
Sorted by
Tagged with
61 views

### Search 2D space for optimal location to "bomb".

I am having trouble even searching for references here, do to not knowing the terminology. Well, and there are so many hits that are not this but just about overlap tests. Given a 2D (floating point) ...
• 141
54 views

### Is it possible to find something better than binary search for this problem?

Let's say we have $n$ urns (numbered $1$ through $n$) and the first $k$ urns have a ball in them (for some $k$ unknown to us) and the remaining urns are empty. Our goal is to determine $k$ by looking ...
• 1,460
29 views

### best search method in the complex plane

For real number search problems, the binary search algorithm is the go-to method. Yet, the answer becomes not so obvious when considering searching for some number $x$ such that $|x-Z_0|\leq R$. I ...
• 101
35 views

### search for specific value out of data set

I am looking for a function or formula how to determine the data set for a specific value (sum) out of a set of data in a table. The function should be the fastest possible search to achieve the ...
• 101
93 views

### Finding the Pareto frontier when the optimization problem is simple?

I am working on the following problem: Find integer $\vec{x}\geq 0$ within the solution space $\mathbf{A}\cdot \vec{x} \leq -1$ such that none of $(x_1, \ldots, x_n)$ can be made any smaller. In ...
• 17.7k
61 views

### DFS on disconnected components.

I was given the following graph. Does the DFS stop at c? So: a,b,d,c. or does it continue with the other component as well? I'm not sure on how it works with disconnected graphs but from what I read ...
• 49
49 views

### Height of a "random" binary search tree

See also this question, but I'd like to know the simpler case which in that question refers to CLRS 12.4 (looked it up - no formula found!). So, assume you have a list $L=\{1,\dots,n\}$ and an ...
223 views

### Prune graph to detect cycles: better than DFS?

By pruning a undirected graph G, I mean iteratively removing all leaves (nodes of degree 1) together with the incident edge from a graph until you are left with a single node (G contained no cycle) or ...
• 123
1 vote
234 views

### Seeking Proof: Can Rubik's Cube States be Mapped to a Euclidean Space of a Certain Dimension?

I am currently researching a problem that involves mathematics and computer science, and I am hoping to get advice or guidance from experts in the field. My question pertains to finding a mapping that ...
• 11
51 views

• 17.7k
1 vote
75 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
802 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 ...
1k views

• 271
1 vote
30 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 ...
1 vote
35 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
142 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 ...
112 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 ...
152 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 ...
• 259
9k 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 ...
1k 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 ...
• 16.3k
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
103 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$ ...
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 ...