CODEWITHSUNDEEP
algorithmoptimizationlogic
Mohammad Namakshenas
Mohammad Namakshenas

Reputation: 85

Confused about the definition of "Exact Algorithm"

What does it mean by saying "an algorithm is exact" in terms of Optimization and/or Computer Science? I need a precisely logical/epistemological definition.

Upvotes: 6

Views: 6434

Answers (3)

tony
tony

Reputation: 1651

In optimization, there are two kinds of algorithms. Exact and approximate algorithms.

Exact algorithms can find the optimum solution with precision.

Approximate algorithms can find a near optimum solution.

The main difference is that exact algorithms apply in "easy" problems. What makes a problem "easy" is that it can be solved in reasonable time and the computation time doesn't scale up exponentially if the problem gets bigger. This class of problems is known as P(Deterministic Polynomial Time). Problems of this class are used to be optimized using exact algorithms. For every other class of problems approximate algorithms are preferred.

Upvotes: 3

Panos Kalatzantonakis
Panos Kalatzantonakis

Reputation: 12683

Exact and approximate algorithms are methods for solving optimization problems.

Exact algorithms are algorithms that always find the optimal solution to a given optimization problem.

However, in combinatorial problems or total optimization problems, conventional methods are usually not effective enough, especially when the problem search area is large and complex. Among other methods we can use heuristics to solve that problems. Heuristics tend to give suboptimal solutions. A subset of heuristics are approximation algorithms.

When we use approximation algorithms we can prove a bound on the ratio between the optimal solution and the solution produced by the algorithm.

E.g. In some NP-hard problems there are some polynomial-time approximation algorithms while the best known exact algorithms need exponential time.

For example while there is a polynomial-time approximation algorithm for Vertex Cover, the best exact algorithm (using memoization) runs in O(1.1889n) pp 62-63.

Upvotes: 7

Gene
Gene

Reputation: 46990

The term exact is usually used to mean "the opposite of approximate". An approximation algorithm finds a solution to a slight variation of an optimzation problem that admits soltions that are "close" to the optimum in some sense, but nonetheless are desirable. As @Sirko said in the comments, the approximation is usually of interest because the exact problem is intractable or undecidable, where the approximate version is not. Often, more than one kind of approximation may be of interest.

Here are examples:

  1. An exact algorithm for the Traveling Salesman problem is NP Complete. The TSP is to find a route of minimum length L for visiting each of N cities on a map. NP Completeness says the best known algorithms still need time that is an exponential function of N. An approximation algorithm for TSP finds a route of length no more than cL for some fixed c > 1. For example, you can easily construct the minimum spanning tree of the cities in time that is a polynomial in N and walk around the tree, covering each edge twice, to obtain an approximatoin algorithm for the case c = 2. The implied goal is to find algorithms for constants c as close to one as possible.

  2. An exact algorithm for compiling a program that produces correct results in minimum time from any given source code is - under reasonable assumptions - undecidable. Yet of course we use "optimizing compilers" every day that improve the speed of code with no promise of true optimality.

Upvotes: 4

Related Questions