For questions about various search algorithms.

learn more… | top users | synonyms

-1
votes
3answers
22 views

Reducing TIC-TAC TOE State Space by using Symmetry in Artificial Intelligence

Im learning Heuristics in AI.I see that for brute force search there are 9! states.But the textbook says that first 3 levels are reduced by symmetry.How does that work?
0
votes
0answers
15 views

Optimally exploring a 2d grid

Given a 2D grid and an unknown starting location, what is the best way to search every node? The size of the grid would be known prior to starting but the method should scale easily.
1
vote
1answer
33 views

Exploiting geometric invariants via group theory

Let $T$ be the set of all plane triangles. The problem is to find $t \in T$ s.t.h. a predicate $P(t)$ holds. At present, I'm doing this by a form of randomized search procedure (effectively via a ...
1
vote
1answer
22 views

Need help understanding a simplification in a simultaneous search model.

The problem I am trying to solve is $\max_{k \in \mathbb{N}} \int_0^1 u d F(u)^k - ck$, where the associated utility is an iid random variable U following $F(\cdot)$ on [0,1]. $c > 0$ is the ...
2
votes
1answer
24 views

Find the three closest surrounding neighbors from a data

I have a data of coordinates $x$ and $y$ where we know the range of both variables, e.g. $(x,y)\in[0,1]^2$. So for a given any random point $\theta_0=(x_0~~y_0)^T$ in the range of $x$ and $y$ I would ...
0
votes
0answers
25 views

Fewest questions to reach an arbitrary confidence level about the number of words a person knows in a foreign language

I have a list of 13060 Chinese characters that are pre-sorted from most frequently used to least frequently used. I would like to design a simple test to determine the total number (or approximate ...
1
vote
0answers
34 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
0
votes
0answers
33 views

Breadth First Search Question

The adjacency matrix for a simple graph is shown here (as an HTML table). The questions below refer to the graph that this table represents. Give the path that is found from vertex G to vertex E ...
0
votes
0answers
15 views

Estimate parameters of a system on realtime defined as follows

I have a motor I need to estimate the parameters on real time. To simplify the problem I will put the general equation in matrix form that governs it in discrete time: $$ u_q(k) = \left[ ...
1
vote
1answer
80 views

Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
0
votes
0answers
53 views

binary search worst case for a set database of entries some good some bad

A database has 10,000 sorted entries, 20% known to be good. When looking up a record in the database, the good entries account for 60%. Two design options are considered to store the data in the ...
0
votes
0answers
22 views

Obtaining Pareto front for more than 2 objectives

I have a reasonably tractable problem withe >2 objectives in which I apply multi-objective evolutionary algorithms (MOEA) like PSO, ACO, GA. I would like to compare the performance and quality of ...
0
votes
1answer
40 views

A mathematical expression for “grid search”?

I've got a question whether there is a mathematical expression for a grid search? I have two parameters a and b in [0;1]. Depending on the values of a and b, I get a value for my function (the value ...
2
votes
0answers
18 views

n-dimensional searching alogrithm

If you want to store various points in a $n$ dimensional (here $n=2$) space. Is there a possibility to do that with a tree (as a binary-tree for $n=1$ is usually used) for efficient and fast finding ...
10
votes
1answer
202 views

The “find my car” problem: proper interpretation and solution?

This has been asked at least twice here, but both questions have accepted answers which are wrong. I don't really know any good way to draw attention to the question besides asking again and being a ...
1
vote
2answers
56 views

How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
0
votes
1answer
57 views

Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
3
votes
1answer
74 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
1
vote
1answer
133 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
3
votes
1answer
439 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
1answer
20 views

Binary search in merged arrays.

Given two arrays, sorted by ascending. Result array is first array and second at the end of first. Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5]. How to find element ...
1
vote
0answers
45 views
0
votes
1answer
42 views

How to extract all the points from a noisy surface?

I have points representing a bridge like in this picture: My goal is to get all the points that are in the red box. These points all share a common surface that is not necessarily planar. The ...
2
votes
0answers
127 views

A* vs D* vs Dijkstra [closed]

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
0
votes
2answers
190 views

Shortest Path between two vertices of a weighted, undirected graph IN LINEAR TIME

Studying for an algorithms test, and a surprisingly simple problem has me somewhat stumped. The following is the question: My issue has been - looking online, everyone uses this kind of problem to ...
1
vote
1answer
124 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
0
votes
0answers
44 views

How to search for an object in more efficient way?

I have a doubt how to check if structure contains an object. Simple sketch of my structure: Root - is a group which can contain groups, keys, values. Group - can contain groups keys, values. Key - ...
1
vote
0answers
34 views

State Space Search

I searched in the web about simple example about State Space Search, but I didn't find any simple and clear one. Can anybody explain to me what State Space Search about by a simple example? Thanks ...
1
vote
1answer
31 views

Having objects trajctories and directions how to find where objects traverse same path?

I have N objects that travel on some trajectories (unique for each object). At each agent curve point we can get object speed (direction). Having some distance ...
1
vote
1answer
466 views

Breadth-first search tree

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find ...
1
vote
1answer
1k views

Term-document vs document-term matrix [closed]

I am not sure if this is the right website to ask this question but I cant figure out where else to get the answer so, please, dont be mad :-) As my bachelor thesis/project, I am trying to construct ...
2
votes
0answers
165 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
0
votes
1answer
43 views

Trivial case of $s \in T$

I was reading paper A Formal Basis for the Heuristics Determination of Minimum Cost Paths in section B "Some Definition About Graphs" there is footnote that say "We exclude the trivial case of $s \in ...
4
votes
1answer
2k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
0
votes
1answer
523 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
1
vote
0answers
54 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
1answer
1k views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
2
votes
1answer
80 views

Searching for a secret, given a non-uniform distribution

Let $s$ be an unknown bit string of length $n$. Let $p(i, b)$ be the probability that $i$-th bit of $s$ is equal to $b \in \{0,1\}$. What's the fastest method to find $s$, given the distribution ...
0
votes
1answer
120 views

Ranking System :S

My math experiences I had at school are not very advanced and I'm struggling with a calculation right now... I'm programming an image Search script for my company where you can find all pictures we ...
3
votes
2answers
434 views

In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the ...
2
votes
2answers
3k views

What is the best strategy for a guess-my-number game?

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure: Player B decides on a number between ...
7
votes
2answers
2k views

Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time. Given a set of ...
3
votes
4answers
3k views

Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E Hi, I ...
0
votes
1answer
74 views

In Mathematica, is there a way to set a variable to the lowest value in a matrix?

It seems that a major aspect of this question is figuring out whether or not I can search the matrix and compare values.
1
vote
1answer
231 views

calculating walks in an undirected graph using linear algebra identity

I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says: Walks: which allow both nodes and edges to be ...
1
vote
1answer
147 views

Is there a simple function which can be used to determine the two “next” search indexes in a binary search?

Edit: question simplified to remove confusion Assuming a sorted list of items with indexes from 1 to N, and given only an index number ...
6
votes
3answers
6k views

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
12
votes
3answers
802 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...