A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.

learn more… | top users | synonyms

1
vote
1answer
42 views

Generating hard puzzles for a backtracking snake

Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer. There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get ...
4
votes
1answer
132 views

Finding an element in a sorted array with at most three queries to larger elements

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
0
votes
2answers
42 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
0
votes
0answers
18 views

TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
1
vote
1answer
83 views

Time complexity of 8-queen, by placeing one by one without attack

I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack. One approach to achieve goal state is to "add a queen to any ...
0
votes
1answer
33 views

How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet? [closed]

I am looking for an automated way to answer the question: what are the URLs on the world wide web that contain at least two strings from a set of strings. So if I have a set of strings {"A", "B" and ...
1
vote
2answers
80 views

Decomposing the search problem into several small problems

I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either: Searching through the original graph. or By decomposing it into several ...
0
votes
0answers
33 views

Search problems that can also be solved by junction trees and searching cliques

Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$. Let $P$ ...
2
votes
2answers
246 views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
1
vote
0answers
87 views

Does FNP-complete = NP-complete?

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong. So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
0
votes
2answers
282 views

Worst case scenario in binary search tree retrieval

Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$). What is the number of comparisons that will occur in the worst case scenario, if we ask ...
1
vote
1answer
112 views

Efficient algorithms for finding a region in $\mathbf R^2$

This question is an extension of a previous question I've asked. Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 ...
1
vote
0answers
53 views

LInear time algorithm to find the diameter of a tree [duplicate]

This is NOT HW, this is from Skienas book, and I just couldn't solve it at all. Please give me a hand here, in understanding and solving it, thanks. Let G = (V, E) be a binary tree. The distance ...
4
votes
2answers
443 views

Uniform-cost Search Problem

Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem? Definitions: ...
0
votes
0answers
151 views

Solving algorithmic problems

Is the first step in solving a "tough" algorithmic problem always asking whether it's hard in the sense that other tough problems can be reduced to it? Not to make the scope of this question tight, ...
6
votes
1answer
125 views

BPP search: what does boosting correctness entail?

It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how ...
1
vote
1answer
1k views

Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org . Currently, I am working on the "Search in Pacman" Project; ...
12
votes
1answer
230 views

Coverage problem (transmitter and receiver)

I try to solve the following coverage problem. There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers are covered by any transmitter. ...
9
votes
2answers
194 views

How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
3
votes
1answer
474 views

Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

I'm reading through the RMIT course notes on state space search. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A heuristic function ...
1
vote
2answers
137 views

Complexity of an optimisation problem in 3D

I have a collection $P \subseteq \mathbb{R}^3$ of $N$ particles and there is a function $f : P^2 \to \mathbb{R}$. I want to find which configuration of the system minimizes the value of $f$. Can ...
16
votes
2answers
1k views

Optimization version of decision problems

It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem optimization/search version: Given an undirected unweighted graph ...