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.
1
vote
0answers
45 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
121 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
1answer
116 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
97 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
198 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
181 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. ...
7
votes
2answers
139 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
153 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
124 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 ...
9
votes
2answers
490 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 ...
