Questions tagged [searching]
For questions about various search algorithms.
114
questions
3
votes
1answer
64 views
Can you find an invertible submatrix?
Given an $m\times n$ matrix $\mathbf{A}$ $(m\gneqq n)$, I'm trying to efficiently find all $n\times n$ invertible submatrices using a computer. Equivalently, I'm trying to find which rows of $\mathbf{...
0
votes
0answers
22 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 ...
1
vote
1answer
16 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?
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
2answers
37 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 ...
6
votes
1answer
1k views
Searching for rock-hard integers.
For integer $k\geq 0$ written $d_jd_{j-1}\dots d_1$, where $d_i$ are single-digit integers, define
$$R(k) :=
\begin{cases} d_j^{d_1}d_{j-1}^{d_2} \dots d_{j/2}^{{d_{j/2 + 1}}}, & j \text{ is ...
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 ...
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
55 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
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 ...
12
votes
1answer
122 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 ...
1
vote
3answers
2k 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 ...
1
vote
2answers
230 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 ...
0
votes
1answer
576 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 ...
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
1answer
28 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
1answer
77 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 ...
0
votes
1answer
54 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
1answer
136 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
0answers
56 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
0answers
44 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 ...
0
votes
2answers
822 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
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 ...
0
votes
1answer
1k 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?
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
244 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 ...
1
vote
1answer
671 views
Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs
Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting.
I was wondering if hamilton cycles, euler paths and euler cycles can ...
0
votes
0answers
155 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 ...
1
vote
3answers
518 views
Why a binary search algorithm works?
Let $n$ be a positive integer and $f \colon \{1,\dots,n\} \to \mathbb{R}$ be a decreasing function with $f(1) \ge 1$. We are interested in finding the largest number $k\in \{1,\dots,n\}$ such that $f(...
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 ...
2
votes
0answers
114 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 \...
1
vote
0answers
118 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 ...
0
votes
1answer
103 views
Is there an algorithm that search multiple duplicate pair combination without a loop?
I'm not a math person. My question sounds vague so an example is probably better.
I have a large list of arrays. Here's 3:
...
1
vote
1answer
71 views
Smart enumeration of a subset of graphs obtained from a parent graph
Suppose i have a graph $G$ of $n$ nodes. For each node someone has given us a recipe $R$ how to replace the node with a graph. So for node $i$, i have $m_i$ choices of graphs to replace it with. Thus, ...
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 ...
1
vote
2answers
25 views
Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function [closed]
A Boolean function $f(n)$ 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 \mathcal ...
1
vote
2answers
365 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
597 views
Prove that a connected undirected graph G is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for G
My question is in the title but to restate:
Prove that a connected undirected graph $G$ is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for $G$. (BFS ...
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
161 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 ...
-1
votes
1answer
70 views
Partition integers into $M$ sets
Given a circular list of two numbers $-1,+1$.I have to partition them into $M$ sets each containing $K$ numbers. Each set has to consist of consecutive $K$ numbers from that list. The set can start ...
4
votes
1answer
77 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 ...
0
votes
1answer
759 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 ...
1
vote
1answer
521 views
Algorithm to find difference between two array members
I have a question concerning algorithms and time complexity(analysis).So I have a field A,which is sorted and has natural numbers where n is >=2(ascending order).How would you write an algorithm which ...
0
votes
2answers
90 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
64 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....
