# Questions tagged [searching]

For questions about various search algorithms.

137 questions
Filter by
Sorted by
Tagged with
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
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 ...
• 23
0 votes
0 answers
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 ...
0 votes
0 answers
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
0 answers
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 ...
• 21
1 vote
1 answer
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 ...
0 votes
0 answers
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-...
0 votes
0 answers
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 ...
0 votes
0 answers
63 views

• 16.1k
1 vote
1 answer
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?
• 11
0 votes
2 answers
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 ...
5 votes
1 answer
1k views

• 261
1 vote
0 answers
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
0 answers
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. ...
• 11
1 vote
0 answers
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 ...
2 votes
0 answers
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 ...
12 votes
1 answer
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 ...
• 223
3 votes
3 answers
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 ...
3 votes
2 answers
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 ...
• 15.1k
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$ ...
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 ...
2 votes
1 answer
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 ...
-1 votes
1 answer
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 ...
• 123
1 vote
1 answer
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 ...
0 votes
0 answers
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
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
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 ...
• 613
1 vote
0 answers
40 views

### Algorithms To Search Partially known Graph

I am right now searching and saving the graph structure of english wiktionary, saving each page as a vertex and its hyperlinked pages as another nodes that are connected with unweighted edges. So I ...
• 549
0 votes
1 answer
3k views

### Maximum of minimum number of moves required for hardest 8 puzzle

I have read that the hardest 8 puzzle requires 31 steps to solve, i.e. every solvable 8 puzzle can be solved in max. 31 steps. How is that?
• 201