Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [search-algorithms]

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

2
votes
1answer
55 views

Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing ...
1
vote
0answers
28 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
2
votes
0answers
223 views

How to traverse a graph in reverse dfs order

For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
0
votes
1answer
30 views

Algorithm to find a shortest past under a special condition

I am trying to come up with an algorithm that calculates the length of shortest rectangle movement in a given bitmap. For example, let's say we have a 24x24 bitmap where 1 is black pixel and 0 is a ...
2
votes
1answer
57 views

Local search (Hill Climbing) scope and definition

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-...
0
votes
1answer
254 views

How to calculate number of nodes opened by BFS?

In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I I know that the equation for BFS is b1 + b2 + ...... + (bd+1 - b) Where b is ...
1
vote
1answer
31 views

data structure admitting top items with prefix

A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
-1
votes
1answer
16 views

Count points on same distance from set of points

Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
1
vote
1answer
33 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
4
votes
0answers
33 views

Any elegant approach to search where users have permissions on subset of records?

I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some ...
-2
votes
1answer
161 views

If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?

I was thinking yes because $0 \leq \sqrt{h(s)} < h(s)$ but I'm not entirely sure.
3
votes
1answer
154 views

Are the No Free Lunch theorems useful for anything?

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,...
0
votes
0answers
257 views

Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
0
votes
1answer
35 views

Given a set of points, find the one closest to a given point

So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me. I need to write code that will take in a ...
-1
votes
1answer
38 views

Using computer vision instead of algorithms?

I have been thinking of a problem i have here with a calendar scheduler where i basically want to split a year into seconds and have access to the dataset of whole year. In this year i assign blocks ...
1
vote
2answers
123 views

Best way we know search for an integer

Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?" My ...
2
votes
1answer
37 views

Finding the best poker hand in a connected grid structure where order matters

I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation. This grid has 12 random cards, in random positions. Each ...
0
votes
0answers
34 views

Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
1
vote
2answers
54 views

Finding an index such that $A[i] = i$ in a strictly increasing integer array

I'm looking for a hint for solving the following problem : Given an array $A[1, \dots, k]$ of integers where $A[1] < A[2] < \dots < A[k]$ write pseudocode for an algorithm that ...
1
vote
0answers
22 views

How can I find the pattern with one mismatch at most by modifying Naive Algorithm?

I want to modify the Naive algorithm to find out if there is any occurrence of the string P in T as a substring with at most one mismatch - where a mismatch is either one of the following: INSERT, ...
1
vote
2answers
29 views

How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

Disclaimer: First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either. The Problem: I'm working on a search algorithm ...
1
vote
1answer
27 views

Generate a unique number for a set of sequences of letters

A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I ...
0
votes
1answer
55 views

Returning two array indices in an array for a given value

Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A[F] is the first value equal to x and A[L] is the ...
0
votes
1answer
42 views

Hueristic Algorithm to find the maximum clique

Let the algorithm be defined as follows: Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every ...
2
votes
0answers
27 views

Search algorithm with constraint of proximity to another point

Let us consider a plain search algorithm (Dijkstra being one example) which will calculate the shortest path from A to B. Now introduce the additional constraint that the path must be as close as ...
0
votes
0answers
35 views

Bounding time complexity of A star

Ive never seen in my studies an attempt to bound the time complexity for finding a solution with A star when : The goal state is gaurenteed to exist The heuristics is admissible and consistent The ...
2
votes
2answers
577 views

Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
2
votes
1answer
35 views

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average ...
0
votes
0answers
53 views

Algorithm to find extrema of a function?

What are some simple algorithms that find the maximum of a function in a certain domain? The function $f$ is guaranteed to have 1 maximum and no other turning points between $a$ and $b$, how can I ...
0
votes
1answer
56 views

How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more

Taken from Artificial Intelligence A Modern Approach : Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this : Now obviously this is not true as in ...
1
vote
1answer
119 views

consistent heuristic - does it always exist?

I am studying for an artificial inteligence class, and i have to classify the following sentence "For any search space, there is always an admissable and consistent A* heuristic". Well, i know that ...
1
vote
1answer
33 views

Is it possible to obtain dynamic tree with two dimensions in big matrix

Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions). In some of the coordinates of the matrix ...
0
votes
2answers
2k views

Number of comparisons in Binary search

I know this question is very trivial to ask, but I have got some doubt while solving this problem.Code is given below ...
1
vote
1answer
204 views

If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal ...
1
vote
3answers
100 views

Solving a discrete optimization problem

Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative ...
2
votes
0answers
23 views

Heuristic Consistency with float multiplications

I'm running A* search with a theoretically consistent heuristic. I'm doing a lot of float multiplications, and I'm not sure how best to ensure that my heuristic remains consistent down to the last ...
0
votes
1answer
44 views

Check if current interval is overlapping some intervals, or is being overlapped

Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our ...
5
votes
1answer
310 views

nlp: phonetic edit distance between a word and the closest of a set of words

Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large ...
0
votes
1answer
124 views

Finding an element in a infinite unsorted doubly linked list

Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)
1
vote
0answers
144 views

Prove that a convex combination of admissible heuristics is admissible

I got this question that's been troubling me for some time. If $h_1$ and $h_2$ are admissible heuristic functions, prove that $h_3 = (c-1)\,h_1 + c\,h_2$, $0 < c < 1$, is also an admissible ...
-2
votes
2answers
3k views

DFS on weighted graphs

I have the following weighted graph with connected nodes. I've made some connections red just to be easier on the eye. I am applying DFS on this graph and I am not sure if this is correct because on ...
3
votes
1answer
80 views

Globally-optimized nearest neighbors lookup

I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors in $\mathbb{R}^a$. These two sets are disjoint: $\mathcal{A}\...
1
vote
1answer
187 views

What is branch factor for beam search in RNNs like TensorFlow's Magenta?

TensorFlow's Magenta melody generation module has a parameter for branch_factor1. What is it?
3
votes
1answer
495 views

Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size?

Magenta's melody_rnn_generate method includes a parameter beam_size. What is it and how does affect the melody?
3
votes
2answers
568 views

Is there an algorithm that can solve chess within the span of a human lifetime?

According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree: A machine... would require over $10^{90}$ years to ...
1
vote
4answers
3k views

I'm looking for an algorithm to find unknown patterns in a string

I am trying to detect patterns in huge code bases. I managed to filter the entire codebase into a tagged string, as in: ABACBABAABBCBABA The result should be: ABA *3 CBA *2 I'm trying to build / use ...
2
votes
1answer
1k views

Finding all edges of an undirected graph which are in some cycle in linear time

As a reduction from another problem, I am trying to deal with finding all edges which are part of some cycle in an undirected graph $G=(V,E)$ in time $O(|V|+|E|)$. My first idea is to use DFS and ...
4
votes
1answer
179 views

Fastest search algorithm in a sorted list with certain error rate-limiting constraints

This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle. Problem description:...
2
votes
1answer
336 views

Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
1
vote
1answer
90 views

Conflict Detection Algorithm

I have been trying to come up with a better algorithm that detects conflicts in the scenarios below. Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we ...