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
0answers
43 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
15 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 ...
1
vote
0answers
9 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
15 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
17 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
20 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
12 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
56 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
27 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
15 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 ...
3
votes
1answer
474 views

How binary search works in real world scenario?

In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers. But in real world, we may search for a name of an employee ...
1
vote
1answer
43 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 ...
0
votes
1answer
35 views

String Search - how to find the “most” accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
1
vote
1answer
53 views

provably optimal search algorithms?

In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-...
-1
votes
0answers
22 views

How do you determine k in a k-gram index?

In information retrieval theory, k-gram indexes can be used for wildcard queries. I often see 3-gram examples, but if I were to build a system how would I choose $k$?
-1
votes
0answers
15 views

Algorithm to determine an approximate distribution of leaf node depths in a massive tree

I am conducting some analysis of game trees (often consisting of 10^50 or more nodes). I'd like to determine, in a given game, how deep in the tree the leaf nodes tend to be. That is, how long the ...
1
vote
0answers
13 views

How to use HITS algorithm to rank pages

I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
1
vote
0answers
23 views

Complexity of bisection method for finding an interval

Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
2
votes
0answers
26 views

Find combination of array elements that exceed maximum array element

Say I have an array of integers like so: [2,2,3,5,5,5,5,6,6,7,7,7,7,9,10] I'd like to find all combinations of these values that when summed exceed the maximum (in ...
2
votes
1answer
31 views

Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
1
vote
1answer
103 views

KMP - longest palindromic prefix

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word. I've seen this algorithm used for determining if a word is rotation of ...
0
votes
1answer
52 views

Visit all vertices of a graph

I need to find the fastest route passing in all vertices Each vertex is a class. I can choose the number of classes for semester. Some classes have prerequisites (A and B need to be done one semester ...
1
vote
1answer
48 views

Algorithmic Design to Undo Rotation of Array

An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$. That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $...
3
votes
2answers
48 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
1
vote
0answers
26 views

Finding non-overlapping combinations of spans/bitarrays

My first post here so please correct me if my terms are off or needs clarification. Suppose I have several sets of lists of spans. I define a span as a pair of indexes: begin and end index in a ...
1
vote
1answer
33 views

Duplicate elements in Queue for BFS Maze Algorithm

I'm fairly new to studying data structures and algorithms. I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and ...
0
votes
1answer
90 views

Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
0
votes
2answers
68 views

A data structure to do a specific lookup fast

I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items ...
0
votes
0answers
16 views

Search techniques to find desired output with complex interdependencies

I am trying to generate output consisting of three-tuples (A,B,C), where A,B, and C are three different datatypes representing different values. I also have a collection of functions $f_i \in F$ ...
0
votes
0answers
43 views

Prove lower bound of searching algorithm on Young Tableau

I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!
2
votes
1answer
42 views

Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?

So this is my question. I am trying to understand this part of the book: At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just ...
4
votes
1answer
51 views

Subgraph isomorphism on star multi-graphs with labelled edges

My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...
2
votes
2answers
55 views

How to graph search a LTL-generated Buchi automaton to generate valid execution paths

I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification. For ...
1
vote
0answers
32 views

What is the meaning of the “*” in names of various learning/search algorithms?

For example, consider L* algorithm for learning a regular language, or A* search algorithm. What do these names - in particular, the star character - mean? It looks like it might be the case that the ...
1
vote
1answer
28 views

Find an edge that is completely visible from point outside a polygon (Convex Hull)

I want to implement algorithms from this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf In particular, I am currently dealing with the one in ...
1
vote
1answer
70 views

Time complexity of transforming one string to another

Here is the problem: Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production ...
1
vote
1answer
74 views

Understanding Binary Search for Kth Smallest element in an Array

The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...
2
votes
1answer
19 views

Efficient membership check in multiple ranges

Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l_n$, upper bound $u_n$). The program receives a number $x$; it must return all ranges in $S$ that ...
1
vote
1answer
20 views

Justification behind this heuristic in SMA*+

I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them ...
4
votes
2answers
35 views

Find the fastest duration for a certain distance in a walk

I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic ...
1
vote
0answers
117 views

Feeding real-time data and binary search algorithm termination

This question was asked in our exam long a go and I don't remember exact words. The scenario was, Initially you are given a set of finite data to start with, and a key value (which you have to find ...
0
votes
0answers
25 views

Minimal search endpoints?

Assume that for each building in a city there is a known subset of the city's buildings that can be seen from that building (being in a building counts as "seeing a building" as well so for every ...
0
votes
0answers
75 views

Find optimal path in BFS and DFS

In UCS it is clear that we find the cheapest cost path. In BFS and DFS we can get the order of output nodes. But How can we find the optimal path in BFS ans DFS in following cases?
1
vote
1answer
37 views

How many queries does it take to find the best flight?

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and ...
0
votes
0answers
27 views

Generation vs expansion BFS

I can not understand the difference between generation and expansion of nodes. How the time and space complexity of BFS are different in each two scenarios? ...
2
votes
1answer
90 views

Variant of nim game with particular rules

Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the ...
0
votes
1answer
415 views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
1
vote
1answer
22 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 ...
0
votes
0answers
32 views

Fuzzy, nonsequential string search algorithm?

Is there an algorithm that can find p + stuff within t, where stuff is any set of characters,...