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

learn more… | top users | synonyms

2
votes
2answers
43 views

Symmetry in Pattern Databases

I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the ...
0
votes
0answers
38 views

Find cell neighbors of a given edge in a 2D grid

In the figure below, cells are labeled row wise, and edges are labeled counter clockwise. For instance, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge ...
1
vote
1answer
41 views

Hill Climbing Search

With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a ...
-1
votes
0answers
23 views

How to write Boolean search expression?

I was reading the Kenneth Rosen's Discrete Mathematics books and trying to solve the exercise of the same. Where i came along with these question likes, What Boolean search would you use to look ...
1
vote
0answers
28 views

Good language for introduction to self-modifying algorithms? [closed]

So I am trying to find a language with which i can write code to build/search through deductive reasoning 'nets', as well as self-modify it's search algorithms based on information learned from these ...
-1
votes
0answers
24 views

How does the Learning Real Time A-Start work?

I am reading the book Artificial Intelligence: A Modern Approach Stuart Russell, Peter Norvig. It has the following pseudocode for LRTA* algorithm ...
3
votes
0answers
30 views

Heuristic for Rubik's cube [closed]

I am trying to understand Pattern Databases for designing heuristics. I am reading Richard E. Korf's book Heuristic Search. One of its paragraphs says The obvious heuristic for Rubik's Cube is a ...
4
votes
1answer
65 views

Find maximum in array without comparisons between elements

Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: ...
-2
votes
1answer
31 views

Best search in Heap Array

Can someone give me the best search algorithm in a max heap? In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < ...
1
vote
2answers
38 views

How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the ...
1
vote
1answer
53 views

Search Heuristics Where the Search Space Has No Gradient

If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the ...
6
votes
2answers
43 views

A key-value datastructure with fast (on average) member move and nearest neighbors search?

I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
3
votes
1answer
44 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
2
votes
0answers
28 views

How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse ...
0
votes
1answer
23 views

Why to implement Open list in Heuristic search with priority queue

I don't understand why do we need to implement Open list using priority queue? There could be other data structure. I understand the usage of priority queues from this example clearly. The newly ...
3
votes
0answers
69 views

Proof of correctness of A star search algorithm

I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm ...
0
votes
1answer
39 views

A problem solved by weighted median

Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily ...
1
vote
1answer
53 views

How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes ...
3
votes
2answers
81 views

Minimax algorithm when all the options are the same

tl;dr What does the Minimax algorithm do when all its options are the same? Consider this Minimax tree: (Green means the ends, orange minimize, blue maximize) (Source: Myself) Imagine this is the ...
0
votes
1answer
43 views

Searching through all program of a stack-based language with little memory

I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output. Given a program fragment, I can ...
4
votes
3answers
118 views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
1
vote
0answers
236 views

Moving a set of points in the plane subject to constraints

I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum. Let $X$ denote the disjoint union of $n$ one-point sets. Let ...
0
votes
0answers
7 views

Insert and search algorithm [duplicate]

My problem is that I have a list of pairs (1,x_1),..(n,x_n). At some point I'll have to add a pair (k,y) to the list where k Do you have any ideas on how to do this? My friend told me his method but ...
3
votes
1answer
99 views

An online algorithm to find the Pareto frontier elements

I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements). For instance. Given the following ...
0
votes
0answers
56 views

DAG, search for cheapest descendants with same color

Let $G=(V,E)$ be a DAG. For each $v\in V$ you have a color $c(v): V \rightarrow \left\{c_1 \ldots c_k \right\}$ where $k$ is a fixed number, and a weight $p(v)$. For every $v \in V$ you have to find ...
1
vote
0answers
99 views

Finding optimal element with two criteria

Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a ...
22
votes
2answers
1k views

How do I find my wife in a supermarket?

If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using? I think there are some ...
2
votes
1answer
57 views

Difference between heuristic-based searching and optimal path searching

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ...
3
votes
1answer
74 views

A string that takes a DFA from any state to a given state?

EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence"). Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition ...
0
votes
0answers
15 views

Look for a pair of elements closest to two start positions in both directions until a condition is met

For a list which contains a set of elements I have two starting positions pos1and pos2 that are selected randomly. Next, I check ...
1
vote
1answer
42 views

maximum distance in between points in taxicab metrics - inserting and deleting points

Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as $$|x_2-x_1| + |y_2-y_1|$$ Initially, there are given empty set of points. I think how to find maximum ...
1
vote
1answer
66 views

Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
7
votes
1answer
187 views

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates ...
2
votes
1answer
64 views

Algorithm for finding fixed cycles in bipartite graphs in sublinear time

Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K_{3,3}$ graph finding if it contains a cycle $C_4$. ...
0
votes
0answers
26 views

Optimal shortest path: When heuristic overestimates

Is it possible (or does there exists a special case) where the optimal shortest path is guaranteed even where the heuristic function always overestimates? Intentions for such a query : Trying to ...
-1
votes
1answer
48 views

How is this algorithm average case derived?

For a simple linear search on an unsorted list my textbook says the following: To determine the average case, you add the number of iterations required to find the target at each possible position ...
2
votes
0answers
725 views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
2
votes
0answers
16 views

A* orientation discretization

I have a space with obstacles I wish to find a path through. What I can do is discretize the space into a grid and use A* (or D* or whatever) to find a path through it. I wish to now add orientation ...
2
votes
2answers
83 views

String matching for wildcard-based records

Let's say that we have a string "1.2.3" and want to find a match for it in the following records: 1.2.9 1.4.5 1.*.3 For each ...
4
votes
1answer
71 views

Finding a target vector through applications of a binary operator

Let $\mathbb{X} = \mathbb{N} \cap [0, 255]$. I am given three vectors in $\mathbb{X}^3$ which I will denote by $v_i = [x_i, y_i, z_i]^T$ for $i \in \{1, 2, 3\}$. Now we have a binary operator ...
6
votes
2answers
200 views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
0
votes
0answers
44 views

Searching for routes on a chessboard [duplicate]

Ok so i have this program which I'm coding, basically this is what It's supposed to do. The input is an n by n chessboard with bombs painted on some of the squares. You are not supposed to step on ...
0
votes
0answers
32 views

How does Lucene build its inverted index so rapidly

I am writing a small Ruby on Rails engine that does simple full-text search. When someone imports text from a given model (eg. Articles, Posts, etc) an inverted index is built that looks like the ...
2
votes
0answers
71 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
1
vote
1answer
88 views

Starting BFS at s and t

INPUT: undirected graph, s, t OUTPUT: connectivity of s and t I perform BFS on s AND t, each taking turns to make one traversal. When a vertex exists in both s and t's BFS tree, we can assume it is ...
2
votes
1answer
41 views

What is the point of an active shape model in facial recognition?

From what I understood, active shape model are used in facial recognition. I figured out how the ASM works but I don't get why we use it. How this shape is suppose to be interpreted for facial ...
-1
votes
1answer
93 views

How to get an O(n) for a search algorithm [duplicate]

Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case. At the ...
-1
votes
5answers
238 views

How can there be 10 steps in the binary search algorithm for the phone book search problem?

The following example was given in an online lecture I was watching. A phone directory is 1000 pages long, and we have to find the name "Zurich Smith". The algorithm is as follows: Split the phone ...
1
vote
0answers
21 views

Fractional cascading vs merge [closed]

Fractional cascading allows me to search in k ordered lists. It requires every list to have same ordering (how would I otherwise insert elements from the cascade below, preserving order?). But why is ...
0
votes
0answers
9 views

Find all pairs of matching elements in two arrays [duplicate]

I have two arrays A & B, each with an element from one that corresponds to the other (for each a in A there is a b in B it corresponds to). And I don't want to brute-force check them all in ...