Questions tagged [searching]

For questions about various search algorithms.

Filter by
Sorted by
Tagged with
0
votes
0answers
35 views

Finding an optimal solution in a tile painting game

images are posted as links because I don't have enough points, sorry The Problem Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal ...
2
votes
0answers
9 views

Is discrete quasiconvexity just as good as discrete convexity?

(I will frame the discussion below in terms of concavity because it suits the examples I have on hand, but the same arguments apply to convexity, too.) Consider a function $p(h)$ defined for $h$ on a ...
0
votes
0answers
34 views

What are some real life examples of UCS (Uniform Cost Search)

Studying search algorithms I've been fascinated by UCS and its similarity to the Djikstra algorithm in some cases. Has anyone any real life example of a possible use of this UCS algorithm to solve ...
0
votes
2answers
47 views

All possible triangles in terms of edges in RCCP

NB: This question was first posted in Stack Overflow, it has been moved here on suggestion. I'm stuck on finding an efficient algorithm to the following problem: Given a complete undirected graph G ...
1
vote
1answer
71 views

How can I generate a pruning table for tetrads?

I'm currently creating a Rubik's Cube Solver and am having some difficulty generating pruning tables. Pruning tables contain information that is used to prune search tree branches, exponentially ...
6
votes
2answers
118 views

Graph puzzles: Constructing graphs from tiles

There is a vast literature on the reconstruction conjecture which says that two graphs with the same deck $D$ are isomorphic. The deck is the multi-set of vertex-deleted subgraphs of a graph (which ...
-1
votes
0answers
66 views

Prove we can't Finding an element $A[i]=i^2$ in sorted array with $\log n$ time.

We are given a sorted array$A[1..n]$, we are searching to find an element that $A[i]=i^2$ in array. How we can prove that we can't do it in $O(\log n)$? My idea: do a linear search in array in $O(n)$...
0
votes
1answer
79 views

Find an element that repeated $\frac{n}{5}$ times in sorted array

We are given a sorted array$A[1..n]$, we are searching to find an element that repeated $\frac{n}{5}$ times in array.How we can do it in $logn$? I find an solution in $O(n)$,with checking each ...
0
votes
1answer
56 views

Maximum matching for general graph

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
0
votes
0answers
53 views

Binary Search average time complexity

I'm looking for explanations for this solution. I have tried and found the solution in book Art of Computer Programming. Volume 3. Sorting and Searching. Second Edition but this didn't help me at all. ...
1
vote
1answer
65 views

Efficient directional nearest-neighbor search among rectangles

I have a large set of rectangles with random orientation and size. Say up to $10000$ rectangles, which are non-overlapping. For every rectangle, I need to find the nearest compatible neighbor. Two ...
1
vote
2answers
36 views

Searching/Sorting Algorithm

I just started studying algorithms and data structures and came across this problem: Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in ...
1
vote
1answer
71 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 ...
0
votes
0answers
28 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$ ...
3
votes
1answer
136 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{...
1
vote
1answer
25 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
2answers
153 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
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
23 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
79 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
53 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
128 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 ...
3
votes
3answers
4k 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 ...
2
votes
2answers
411 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
1k 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
87 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
34 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
144 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
68 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
152 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
68 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
53 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
2k 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
34 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
2k 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
30 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
295 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
917 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
202 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
563 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
101 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
125 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
133 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
119 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
81 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
50 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 ...