# Questions tagged [search]

The tag has no usage guidance.

47 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

### Difference between cost and the heuristic function in A* search

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
17 views

### Frontier steps for greedy best first search

I've been asked to list the frontier steps for greedy best-first search for the graph in the picture below. I've attempted to recreate the algorithm in Golang, as shown below: ...
1 vote
28 views

### Unusual version of a binary search algorithm

For one dimensional, continuous binary search most effective algorithm would remember boundaries. For example if boundaries are 0.7 and 0.9, point to check would be 0.8. And if result is 'too small', ...
87 views

### Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking

I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article. ...
60 views

### How to find time complexity of Breadth First Search for this tree?

This is what I got from another forum, but honestly doesn't make much sense to me. Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be ...
1 vote
27 views

### Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
115 views

### Searching through an unsorted array with a better than O(n) complexity?

This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't ... 55 views

### Why is a regex search less efficient than a normal search?

On a lot of messaging applications, regex search isn't enabled due to a "linear scan". I'm not sure why this is the case. Can someone explain?
102 views

### How to find long trails in a multidigraph

I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
1 vote
39 views

### Given consumer grade hardware,what is a reasonable upper bound for size of search space?

There's a gacha RPG I'm trying to get better at. I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output. The equations themselves ...
29 views

### Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the ...
10 views

### Finding the point with smallest x-ordinate between two given y-ordinates [duplicate]

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the ...
157 views

528 views

### Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic". The wikipedia page on hyper-heuristics states that they are "heuristic ...
1 vote
2k views

### A* Search Algorithm Implementation with Priority Queue

I've got a question regarding the A* search algorithm's implementation. According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
48 views

### B/B+ trees without leftmost pointers

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers: node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ] Now suppose that I ...
133 views

### Steps to create a heuristic for solving a problem

I am completely new to AI and doing self-learning to acquire this knowledge. I went through the different available search algorithm like BFS, DFS and A* but something that I can't understand is a ...
74 views

### How does topic or tag suggestion algorithms work?

I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings. For ...
1 vote
33 views

### Better algorithm for aggregating data from various LDAP systems

I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like ...
1 vote
278 views

### Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
1 vote
43 views

### Is graph search of shortest (optimal) path an instance of optimisation?

I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm. I am not too familiar with graphs / trees ...
122 views

### Non-quadratic search for specific difference between elements in sorted array

New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either ...
306 views

### Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
1 vote
2k views

### special case of best first search algorithms

I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/
401 views

### What is the most recent comparison of signature files and inverted indices?

Modern papers on search indices often contain a statement that inverted indexes (posting lists) are categorically superior to signature files (bloom filters). Here are some examples from papers ...
101 views

### Algorithmic complexity of Sub-array with sum = target algorithm

Question: Given an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X E.g: If array is [1, 3, 5, 18] and X = 8 Output: True, if X = 10, ...
657 views

### Ski design usaco problem alternative solution

problem statement for SKICOURSE is this Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow ...
1 vote
111 views

### Taking intersection in large search

As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once ...