Questions tagged [search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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: ...
user avatar
1 vote
0 answers
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', ...
user avatar
2 votes
1 answer
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. ...
user avatar
-1 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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: ...
user avatar
2 votes
2 answers
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 ...
user avatar
0 votes
1 answer
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?
user avatar
2 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
2 answers
157 views

$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it. All remaining cells on right are filled with zeros. For example, $m=10, n=4$: $$A = \{...
user avatar
  • 1
1 vote
1 answer
131 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
user avatar
  • 315
0 votes
2 answers
198 views

The best approach to search for closest object in hash map holding arraylist without changing data structure

Imagine the game handled server sided, don't think of a visual problem. Given a game 2D map, with size of n * n. The game contains objects (such as door, wall, a table). Each tile position (x,y) can ...
user avatar
  • 1
0 votes
1 answer
121 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
user avatar
0 votes
1 answer
39 views

Pagination of results from different sources merged by a unified scoring function

Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\...
user avatar
  • 227
-3 votes
1 answer
40 views

Is Google search personalized? [closed]

Pardon me if this is a very naive question. Suppose I search for something on Google and my next-door neighbour searches for the same thing (on Google) at the same time. Do we get the same or ...
user avatar
3 votes
3 answers
319 views

Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
user avatar
  • 27
1 vote
0 answers
17 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
user avatar
0 votes
2 answers
656 views

Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
user avatar
2 votes
1 answer
57 views

Extend binary search

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries, indexed from 0 to $N-1$ and I have to find $K$ of them that satisfy some constraint. The ...
user avatar
  • 121
2 votes
1 answer
1k views

Search vs planning in artificial intelligence

I'm studying artificial intelligence following the Russell & Norvig book. We did a search and planning part that for me is the same (at least on the representation). I'd like to know what is the ...
user avatar
  • 242
3 votes
1 answer
75 views

Finding $k$-th element in prefix of size $i$

Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
user avatar
  • 1,398
1 vote
1 answer
44 views

Kth smallest element in an arra [duplicate]

What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
user avatar
  • 499
1 vote
1 answer
3k 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 ...
user avatar
1 vote
0 answers
63 views

An algorithm for getting the position index

Consider these two equation. $$ m_1+m_2+m_3+m_4 = M_m\\ |m_1|+|m_2|+|m_3|+|m_4| = N_m $$ where $\{m_i,M_m,N_m\}\in \mathbb{Z}$. Given the value of $(N_m,M_m)$ we can find the different solutions ...
user avatar
  • 111
4 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 13
2 votes
0 answers
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 ...
user avatar
  • 121
0 votes
1 answer
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 ...
user avatar
  • 3
2 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 215
1 vote
1 answer
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 ...
user avatar
  • 103
1 vote
1 answer
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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.:/
user avatar
  • 11
7 votes
1 answer
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 ...
user avatar
  • 529
0 votes
0 answers
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, ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 111
1 vote
1 answer
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 ...
user avatar
5 votes
1 answer
1k views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
user avatar
10 votes
1 answer
878 views

Why Is KD-Tree-based Nearest Neighbor Exponential in K?

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
user avatar
  • 200
4 votes
1 answer
117 views

How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?

I heard Google creates indexes of pages. Even then, the number of indexes goes with time. Why wouldn't this slow down the search?
user avatar
2 votes
3 answers
102 views

Fast comparison with a tolerance

I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$. I want to do this by ...
user avatar
  • 3,912
3 votes
2 answers
2k views

Why does an admissible heuristic mean A* is optimal?

An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter? Say we have optimal path A ...
user avatar
  • 33