Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

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

Matching algorithm to find pattern match in rectangles

I am trying to write an algorithm to find the best (if any) match for a pattern of rectangles. Essentially, given a database of three different arrays of rectangles. The color is irrelevant here, it's ...
1
vote
0answers
12 views

Structure Preserving Continuous Hash Function

This question was originally posted on super user, but redirected here based on some suggestions. I am completely new with computer science, and not only recently did I run into the notion of hashing....
5
votes
1answer
75 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
1
vote
1answer
68 views

Space complexity of breadth-first search

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor. ...
1
vote
0answers
16 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
0
votes
0answers
34 views

Given an array of sum and an array how can to find if all the sums are possible using distinct elements of array?

example: if we have array of int as 1 2 3 and sum array is given 3,3 we can form this sum as {1,2} and {3} if the sum array is 5 3 we can not create the sum array, we can for {2,3} but not enough ...
1
vote
0answers
39 views

Multi Agent Sokoban Solvers state of the art

I am researching into coding a solver for a variant of the Sokoban game with multiple agents, restrictions (eg. colors of stones, goals) and relaxations (push AND pull possible etc.) By researching ...
0
votes
2answers
29 views

Karp-Rabin - what is the input for the worst case time complexity?

I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet: String "AAAAAAAA" ...
1
vote
1answer
87 views

Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
2
votes
1answer
70 views

Understanding Correctness of Bidirectional Dijkstra

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10: https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%...
0
votes
1answer
20 views

How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

Consider the following matrix: Input: The entire list of coordinates ranging from (0,0) to (4,4). A list indicating certain coordinates which cannot be used to generate a path reached. So, each ...
2
votes
1answer
43 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
1
vote
0answers
14 views

Probabilistic switching between breath-first and depth-first

I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and ...
3
votes
1answer
27 views

Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?

Note: The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA. I need to scan both columns (shown below) to find any number of column 1 ...
0
votes
1answer
25 views

Tree search returning parents and children

I've a flat structure where a node references its parent instead of children class Node(int Id, Node Parent, string Data); Given a list of all nodes, and a ...
0
votes
1answer
45 views

What are possible uses for cross, back and forward edges after the DFS visit?

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles. What are other ...
3
votes
1answer
101 views

Search a sorted array that ends with zeros in O(log n) time

I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted. If I make a binary search including the 0's I get $O(\log(m))$. ...
4
votes
1answer
85 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
0
votes
2answers
39 views

Algorithm for searching in BST with only <

How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.
0
votes
0answers
17 views

best first search (lowest cost first search) time complexity [duplicate]

I'm working on a homework assignment directly related to this question: Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis Anyway it's ...
1
vote
1answer
161 views

Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best ...
1
vote
1answer
94 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
5
votes
1answer
59 views

Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...
1
vote
1answer
51 views

Two Minimax AIs playing against each other

I am trying to have my Minimax AI chess players play against each other. I was a bit confused about an implementation detail. Let's call black my first minimax AI ...
6
votes
1answer
85 views

Index matching algorithm without hash-based data structures?

I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time. Given two arrays $...
1
vote
1answer
50 views

What is a search problem?

I'm looking for a formal and broad definition. Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a ...
1
vote
2answers
42 views

Term for the tree of all paths starting from a given vertex in a graph

What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex? This is the tree that is implicitly or explicitly constructed when ...
1
vote
2answers
90 views

Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
2
votes
1answer
24 views

Name of double sided search algorithms

I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
2
votes
2answers
36 views

Measuring the Probability of Error for a Potential BPP Algorithm

Problem Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space ...
0
votes
0answers
13 views

Identify row or column addition or deletion in a table

I'm looking for a solution which can able to identify the any row or column addition or deletion in a table of numbers. What I have thought of as of now by using the LCS i.e. "Longest common sub-...
2
votes
1answer
129 views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
0
votes
1answer
18 views

Sorting on non-linear topology

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular ...
1
vote
0answers
22 views

How to find all numbers that there distance from given point are less or equall to integer n? [closed]

Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$? Example: suppose we ...
0
votes
0answers
80 views

Does BFS or DFS perform better to solve the Towers of Hanoi problem?

Use the DFS and BFS algorithms to solve the Towers of Hanoi problem. Which performs better and why? Towers of Hanoi Towers of Hanoi visualization When I think of the Towers of Hanoi problem, I ...
1
vote
0answers
32 views

Searching Algorithm on Connected Graph

This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math. Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
0
votes
2answers
162 views

How to calculate time complexity of a randomized search algorithm?

Example: Finding an element from a sorted array Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
4
votes
1answer
62 views

Grover's Algorithm result when the desired element is not present

What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?
1
vote
2answers
75 views

Detailed step of Dijkstra's algorithm performance analysis

Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf about the performance of Dijkstra's algorithm on Page 118, we are given: 4.4.3 Running time At the level of abstraction of Figure ...
0
votes
0answers
197 views

Egg dropping problem

Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...
2
votes
0answers
109 views

Why is it true that given a monotonic heuristic function, A* can be seen as Dijkstra's algorithm where no node needs to be processed more than once?

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: $$...
0
votes
0answers
30 views

How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
2
votes
0answers
23 views

Good examples of consistent/admissible heuristics in non-graphical domains?

I'm preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions. Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic ...
0
votes
0answers
16 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
1
vote
0answers
21 views

Spatial index search that returns sorted results

I need to perform a spatial index search while also sort the results by one of the dimensions. Backstory: I have a map with lots of 2D objects and when the user interacts with the map I need to ...
0
votes
1answer
21 views

Keywords/terminology for using “extra” information in search problems?

I am trying to find references on a particular idea, but I don't know which keywords to use in a google search. the idea is: as an example, consider graph search. maybe the problem is: find a path ...
1
vote
0answers
17 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
0
votes
2answers
70 views

Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
0
votes
1answer
39 views

Optimality of A* search

I use the A* search algorithm to to search for the shortest path from S to G. The evaluation function is $f(n) = g(n) + h(n)$. Since node A and B have the same estimated total cost, I choose to go ...
0
votes
0answers
154 views

8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once. But ...