# 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) ...
1k views

### Average complexity of linear search with weighted probability

Question: Consider the list $L[0:n]$ where $n = 2k – 1$. Calculate the average complexity $A(n)$ of Linear Search, where the following conditions all hold simultaneously: the probability that search ...
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 ...
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 ...
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 ...
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 ...
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 ...
317 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 ...
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 ...
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 ...
51 views

5k views

### In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the ...
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?
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 ...
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 ...
1 vote
128 views

### Exhaustive Search

Suppose you have a vector of array with N elements, and each element can be an integer between 0 and M. For example, "1, 3, 0, 4, 0" where N = 5 and M = 4. I want to find this array by just doing an ...
1k views

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. ...
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 ...
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 ...