Questions tagged [searching]

For questions about various search algorithms.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
1answer
78 views

Optimal curve to find a lost person in a forest

I read a story about somebody getting lost in a forest, and, apart from sympathy, the following mathematical problem came to my mind. Suppose the lost person is sitting still at an unknown point in a ...
3
votes
0answers
69 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
0answers
46 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 ...
2
votes
1answer
29 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
0answers
115 views

IOI '96 Magic Squares: Reaching Squares Using Transformations

A magic square is $2\times 4$ matrix with entries $1, 2, \dots, 7, 8$ where no entry occurs twice (equivalent to a permutation). As an example, consider the following magic square: $\displaystyle \...
2
votes
1answer
139 views

Find the three closest surrounding neighbors from a data

I have a data of coordinates $x$ and $y$ where we know the range of both variables, e.g. $(x,y)\in[0,1]^2$. So for a given any random point $\theta_0=(x_0~~y_0)^T$ in the range of $x$ and $y$ I would ...
2
votes
0answers
266 views

n-dimensional searching alogrithm

If you want to store various points in a $n$ dimensional (here $n=2$) space. Is there a possibility to do that with a tree (as a binary-tree for $n=1$ is usually used) for efficient and fast finding ...
2
votes
0answers
230 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where $\...
1
vote
1answer
36 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 ...
1
vote
1answer
18 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?
1
vote
0answers
23 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
0answers
22 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
0answers
57 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 ...
1
vote
0answers
50 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 ...
1
vote
0answers
32 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 ...
1
vote
0answers
120 views

A variant on the travelling salesman problem

I have $M$ vertices $V_1$ through $V_m$, which are paired into $N$ edges edges $E_1$ through $E_n$. I wish to add $N-1$ additional edges to the graph to produce a path graph that visits all of the ...
1
vote
2answers
367 views

Way to Improve Binary Search when Search Space Changes

This question is inspired by a question posed about a Number Searching "game" on Stack Overflow. In essence, the premise of the game is to find a randomly chosen number between 1..N (where N in this ...
1
vote
0answers
104 views

Choosing from a group of unfriendly friends

I'm a social person with lots of friends![citation needed] Unfortunately, my friends don't really like each other. In fact, each of my friends only likes one other friend, and dislikes two others. ...
1
vote
1answer
66 views

Finding nearest value in a sorted set

I am interested in math notation of finding the nearest value in a sorted set of values to the given value. 3, 7, 10, 15, 20, 29, 48, 67, 94 If i want to find the nearest value to 23, it would be 20....
1
vote
0answers
170 views

Knights tour dfs search with look ahead

After Using a basic depth first search I was wondering if there was any way to predict a dead end before one becomes apparent? As I know I can stop there becoming multiple dead ends as in a single ...
1
vote
0answers
190 views

Computational complexity of DFS is the same as BFS when the result I want is a list of all cycleless paths?

Given an arbitrary yet low complexity directed graph ($\lt 50 $ nodes), is the computational complexity of a (breadth-first search)-based algorithm the same as that of a (depth-first search)-based ...
1
vote
0answers
20 views

Search on graphs, finding the best way for more than one driving object

I know about algorithms like A*, Breadth-First, Depth-First , and so on. These algorithms are based on a very bad assumption which makes them not working on actual situations. I give you an example : ...
1
vote
0answers
37 views

Enumerate 'one number from each set' from a set of sets in order of increasing sum.

This question is somewhat similar to: Algorithm wanted: Enumerate all subsets of a set in order of increasing sums but has a significant difference in that instead of enumerating all subsets of a set, ...
1
vote
1answer
77 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 ...
1
vote
0answers
199 views

Improving Simulated Annealing based on Measure of Goodness

can anyone answer this question or direct me to a reference that can help? Simulated Annealing returns the current state when the end of the annealing schedule is reached and if the annealing ...
1
vote
0answers
185 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
1
vote
0answers
49 views

Origin of the following equation

...
1
vote
0answers
47 views

State Space Search

I searched in the web about simple example about State Space Search, but I didn't find any simple and clear one. Can anybody explain to me what State Space Search about by a simple example? Thanks ...
1
vote
0answers
70 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
0
votes
0answers
21 views

Search algorithm with sets as variables

I apologize in advance if this sounds vague but I am trying to find directions as to what to look for. All the sets in this problem are finite. Suppose I have two functions $f_1:X_1\times Y_1->X_1$ ...
0
votes
0answers
23 views

Graph type and algorithm identification

Say I have the below digraph. Where each node represents an action, and edges represent a dependency on another action. I want to be able take pick an action, find the order in which I should do the ...
0
votes
0answers
16 views

What method should I use if I want to find best fit for a matrix $B$ inside matrix $A$

Assume that we have a real matrix $A$ with the size $n,m$. Then we have a real matrix $B$ with the size $i,j$ where $i << n$ and $j << m$. In other words, $B$ is much smaller than $A$. ...
0
votes
0answers
22 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 ...
0
votes
0answers
25 views

Site some sample problems about binomial coefficient and graph theory

I need to provide 10 each problem for the binomial coef and graph theory. The topic haven't introduced by the prof so I'm having a hard time creating problems on my own (well atleast im trying and ...
0
votes
1answer
40 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 ...
0
votes
0answers
61 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 ...
0
votes
0answers
29 views

How to find closest matching items for a given query?

Given 3 items i with probability values: p of belonging to 3 classes c as: ...
0
votes
0answers
246 views

Depth-first and breadth-first search variants

Are there special names for the following? two variants of depth first search: 1. the current node is visited before its children; 2. the current node is visited after its children; two variants of ...
0
votes
0answers
160 views

Need a better heuristic for solving a 2x2x2 rubiks cube

I am writing a Python program that solves a 2x2x2 rubiks cube using A* and beam search. However, if I scramble the puzzle more than ten times the program keeps running forever, and I think it is ...
0
votes
1answer
54 views

How many elements would have to be looked to locate these elements?

How many elements would have to be looked (binary search) at in order to find an integer 5000 at element 499 and an integer 7282 at element 686 assuming it's binary search algorithm and the total ...
0
votes
0answers
47 views

Efficient search strategy in a monotonic boolean function wherein the probability of solution location is known apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
0
votes
0answers
1k views

The number of comparisons in brute force string search

In the brute force approach to string search, how many character comparisons will the algorithm make when searching for "lido" in the string "supercalifragilisticexpialidocious"?
0
votes
0answers
163 views

A* algorithm: path in straight line?

Question for people acquainted with A* pathing algorithm. Is there a way to find straight line path throught A* algorithm while only having G-cost and H-cost values (and F-cost) and not having ...
0
votes
1answer
765 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 ...
0
votes
0answers
171 views

finding a threshold with minimum tries and limited search point

I would like to find a threshold with minimum number of tires; Let's say: I have a apartment with 120 floors and we have piece of glass. I would like to find in which floor the glass is starting to ...
0
votes
0answers
102 views

Combinatorial problem in a maze.

We have a robot trapped in a maze of size $M \times N$ but we don't know what is its position initially. We want the robot to exit the maze but each time we move it we cannot be sure if it did ...
0
votes
0answers
30 views

Uniqueness of spanning trees made using search algorithms?

For undirected graphs, the corresponding spanning trees can be obtained using various search algorithms like Depth-first search algorithm , Bredth-first algorithm, etc. I am not sure whether the ...
0
votes
0answers
128 views

Binary search for the worst case.

I want to analyze binary search for the worst case, completely mathematically without any ellipses(...). I solved out the recurrence of the binary search. $$ T(n+1)=T(n/2)+C $$ I've already searched ...
0
votes
0answers
51 views

How to search for an object in more efficient way?

I have a doubt how to check if structure contains an object. Simple sketch of my structure: Root - is a group which can contain groups, keys, values. Group - can contain groups keys, values. Key - ...