Questions tagged [searching]

For questions about various search algorithms.

Filter by
Sorted by
Tagged with
0
votes
2answers
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 ...
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
1answer
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 ...
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 ...
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 : ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
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
1answer
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 ...
0
votes
1answer
16 views

Prove that search in matrix takes mor than n comparisons

Let us call matrix $A$ ascending if $A_{kl}\ge A_{ij}, i \le k, j \le l$ for every $k$ and $l$. Given a number $x$ prove that determining whether $x$ is in an ascending matrix or not takes more than $...
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, ...
0
votes
1answer
4k views

Calculating the amount of times a binary search could run (worse case) without a calculator/calculating base 2 logs without a calculator.

Ok so I had a question on a test that I had to do without a calculator. And I can not figure out how in the world I am supposed to do it without a calculator. The question asked to find how many ...
0
votes
1answer
40 views

Minimum number of steps required to visit every “special” point on a rectangular gird

I am stucked at this problem: Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$ (I.e $G$ is a matrix that have $m$ rows and $n$ colums over the ...
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 ...
4
votes
3answers
308 views

Minimum number of steps required to visit every corner of a rectangular grid

I am stucked at this problem: Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$ (I.e $G$ is a matrix that have $m$ rows and $n$ colums over the ...
0
votes
2answers
79 views

How to prove $\frac15 n^2-42n-8\in Ω(n^2)$?

Here is my procedure: So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow \frac15 n^2-42n-8\ge cn^2]]$ Taking $B=1$. We have $\frac15 n^2-42n-...
1
vote
1answer
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, ...
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
1answer
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 ...
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
1answer
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 ...
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 ...
-1
votes
3answers
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?
1
vote
1answer
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 ...
1
vote
1answer
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 ...
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 ...
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
1answer
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 ...
0
votes
1answer
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 ...
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 ...
12
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
4
votes
1answer
95 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ($\...
1
vote
1answer
162 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
3
votes
1answer
1k views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers $...
1
vote
1answer
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 ...
1
vote
0answers
49 views

Origin of the following equation

...
0
votes
1answer
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 ...
2
votes
0answers
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* ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
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 - ...
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
1answer
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 ...
1
vote
1answer
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 ...
4
votes
1answer
7k views

Term-document vs document-term matrix [closed]

I am not sure if this is the right website to ask this question but I cant figure out where else to get the answer so, please, dont be mad :-) As my bachelor thesis/project, I am trying to construct ...
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 $\...