# Questions tagged [searching]

For questions about various search algorithms.

137 questions
Filter by
Sorted by
Tagged with
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!
34 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 ...
20 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 ...
18 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 vote
35 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 ...
1 vote
62 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 ...
33 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-...
30 views

### Are unordered lists and cardinality of continuum related?

Studying some basic search algorithms I found that looking for a specific element in an ordered list of length N requires o(log2(N)) operations ,whereas the same search in an completely unordered list ...
63 views

1 vote
43 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?
398 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

1 vote
26 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
24 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
96 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 ...
62 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 ...
135 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 ...
6k 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 ...
578 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 ...
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 ...
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$ ... 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 ...
338 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 ...
96 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 ...
1 vote
194 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 ... 96 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 ... 1 vote
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 ...
3k 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 ...
1 vote