# Questions tagged [searching]

For questions about various search algorithms.

116 questions
Filter by
Sorted by
Tagged with
91 views

### Expected number of iterations of an exhaustive search

I want to find complexity of the exhaustive search over $M = |X|$ elements which are uniformly distributed to find a particular $x \in X$. My attempt: Each element has $\frac{1}{M}$ probability to ...
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....
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 ...
284 views

### Counterexample for statement about binary search tree

Let's say, key $k$ was found in a leave of a binary search tree. Let $P$ be the search path from the root of the tree to the node with key $k$. Let set $A$ contain all nodes left from path $P$. Let ...
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 ...
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 ...
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 : ...
1k views

### What is line search

I hear a lot about line search in optimization. I am fine with the methods like Gradient Descent but what is line search and its uses? Intuitively from what I understand right now, line search is ...
22 views

### looking for function endless, nonlinear, has positive derivitive and has inverse

I am trying to find a function that suits my needs for an AI project that I am working on the specifications are below. If you know any function that fits that description please let me know or if not ...
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 ...
129 views

### Average case complexity of linear search average when guaranteed a single match in the search list?

I'd like to calculate the average case performance of linear search. According to wikipedia: If the value being sought occurs once in the list, and all orderings of the list are equally likely, the ...
16 views

36 views

### How to implement an algorithm for specific kinds of search in a graph

Imagine i have a graph called G. G has some parts. In one part, every node describes a person. I have another part in G which contains interests as nodes. ( Imagine that person A likes music. So, ...
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 ...
750 views

### Weakly unimodal function using Golden Section Search

I was going through the Golden Section Search https://en.wikipedia.org/wiki/Golden_section_search and as I understand it should work for every unimodal function. Here, the definition of unimodal ...
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 ...
39 views

### Does this search method exist and what is it called?

I would like to search some function $f(x)$ "greedily" for a certain condition. Assume the condition $c = f(x_1)$ returned by this function is currently false and I can increase the input $x$ to the ...
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 ...
3k views

### Reducing TIC-TAC TOE State Space by using Symmetry in Artificial Intelligence

Im learning Heuristics in AI.I see that for brute force search there are 9! states.But the textbook says that first 3 levels are reduced by symmetry.How does that work?
61 views

### Exploiting geometric invariants via group theory

Let $T$ be the set of all plane triangles. The problem is to find $t \in T$ s.t.h. a predicate $P(t)$ holds. At present, I'm doing this by a form of randomized search procedure (effectively via a ...
36 views

### Need help understanding a simplification in a simultaneous search model.

The problem I am trying to solve is $\max_{k \in \mathbb{N}} \int_0^1 u d F(u)^k - ck$, where the associated utility is an iid random variable U following $F(\cdot)$ on [0,1]. $c > 0$ is the ...
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 ...
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 ...
724 views

### Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customerās record in the database, the good customers account for 60%. Two ...
177 views

### A mathematical expression for “grid search”?

I've got a question whether there is a mathematical expression for a grid search? I have two parameters a and b in [0;1]. Depending on the values of a and b, I get a value for my function (the value ...
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 ...
301 views

### The “find my car” problem: proper interpretation and solution?

This has been asked at least twice here, but both questions have accepted answers which are wrong. I don't really know any good way to draw attention to the question besides asking again and being a ...
766 views

### How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
701 views

### Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
95 views

31 views

### Binary search in merged arrays.

Given two arrays, sorted by ascending. Result array is first array and second at the end of first. Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5]. How to find element ...
49 views

...
52 views

### How to extract all the points from a noisy surface?

I have points representing a bridge like in this picture: My goal is to get all the points that are in the red box. These points all share a common surface that is not necessarily planar. The ...
1k views

### A* vs D* vs Dijkstra [closed]

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
968 views

### Shortest Path between two vertices of a weighted, undirected graph IN LINEAR TIME

Studying for an algorithms test, and a surprisingly simple problem has me somewhat stumped. The following is the question: My issue has been - looking online, everyone uses this kind of problem to ...
228 views

### Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
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 - ...
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 ...
42 views

### Having objects trajctories and directions how to find where objects traverse same path?

I have N objects that travel on some trajectories (unique for each object). At each agent curve point we can get object speed (direction). Having some distance ...
803 views

### Breadth-first search tree

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find ...
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 \$\...