Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what is an approximate algorithm". In daily operation, I believe that many people have doubts about what an approximate algorithm is. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "what is an approximate algorithm"! Next, please follow the editor to study!

What is an approximate algorithm?

Approximate algorithm is a way to deal with the NP completeness of optimization problems, and it can not ensure the optimal solution. The goal of the approximate algorithm is to approach the optimal value as close as possible in polynomial time.

Although it can not give the exact optimal solution, it can converge the problem to the approximate value of the final solution. Its goal meets the following three key characteristics:

Be able to run efficiently in polynomial time

Can give the optimal solution.

Valid for each problem instance.

Background

The evaluation of mathematical expressions is often accompanied by constants, variable analysis and the order of equations, which can be used to measure the complexity of approximation. This kind of assessment divides the problem into P and NP difficult problems.

Strategies for P problem and NP problem

P problem refers to the problem that can be solved in polynomial time.

NP stands for uncertain polynomial time (nondeterministic polynomial time), and NP problem refers to the approximate verification of the answer in polynomial time. But at present, it has been found that many of these problems take exponential time to solve.

P and NP strategy.

The real debate is whether P=NP or P ≠ NP. Some previous studies have proved that both are correct. If a problem is polynomial power, then there are multiple optimal algorithms. Therefore, in the NP complete problem, there are two methods to find the near-optimal solution, and then choose the most suitable algorithm.

If the input size is small, an algorithm with exponential run time may be more appropriate.

Secondly, by replacing the deterministic algorithm with the approximate algorithm, we can still find the near-optimal solution in the polynomial time.

The complexity of the approximation algorithm can be inferred from the input size and approximation factor. Next, we use some examples to explore how these algorithms can be applied to practical problems.

Partition problem (Partition Problem)

In the field of computer science, the problem is defined as: given a multiple positive integer set X, it can be divided into subsets X1 and X2 with equal sum of two elements, that is, the sum of the values of each subset is equal to the other subset.

For example, X1 = {3magistrate, 3pence2, 3pyror2) can be divided into X1and X2, the sum of the two numbers is 11.

Similarly, X = {1pr 3je 1je 2je 1je 2} can be divided into X1 = {2je 1Jet 1} and X2 = {3je 2}. The sum of the two subsets is 5. Interestingly, this is not the only solution. The sum of the values of X1 = {1prit 3rec 1} and X2 = {2rect 1pr 2} is also 5, which indicates that there are multiple possible subsets.

This is the NP complete problem. There is a pseudo-polynomial time dynamic programming solution, and the near-optimal solution of the problem can be obtained.

Methods and decision steps

Now, let's analyze this problem and break it down into several separate standard problems. Here, we want to find a subset in which the sum of the elements of the multiset is equal, then the problem can be decomposed into the following two problems:

Subset sum problem: the sum of the elements of the subset X equals the number W.

Multi-channel digital segmentation: given the integer parameter W, determine how to divide X into W equal subsets.

Approximate algorithm

As mentioned above, after decomposing the partition problem into multipath segmentation and subset sum problems, we can consider the algorithms developed for these problems, including:

Greedy digital segmentation (Greedy number Partitioning)

The algorithm iterates through all the numbers and assigns each number to a subset with the smallest sum. If the numbers are not sorted, their runtime complexity is O (n), and the approximation rate is about 3 prime 2. Its Python pseudo code is as follows:

Def find_partition (numbers): "" Separate the available numbers into two eqal sum series.

Args: numbers: collection of numbers, for example list of integers.

Returns: Two lists of numbers. "" X = [] Y = [] sum_X = 0 sum_Y = 0 for n in sorted (numbers, reverse=True): if sum_X

< sum_Y: X.append(n) sum_X = sum_X + n else: Y.append(n) sum_Y = sum_Y + n return (X, Y) 将数字排序，则运行时复杂度增加到 O(n logn)，近似率增加到 7/6。如果数字在 [0,1] 范围内均匀分布，则近似率约为 1 + O(log logn/n)。 分区问题图示。 上图用二叉树的形式展示所有分区。树的根部表示集合中的最大数，每一级对应输入数字，每个独立分支对应不同的子集。遍历这些集合需要深度优先遍历（depth-first traversal），所需的空间复杂度为 O(n)，时间复杂度为 O(2^n)。 适用性： 该算法可以根据情况进行修改，以便改善运行时复杂度。每一级的首要目标是构建一个分支，将当前数字分配给总和最小的子集。首先通过贪婪数字分割找出总和，然后切换到优化，得到全多项式时间近似解。 Karmarkar-Karp 算法 Karmarkar-Karp 算法指以降序方式排列数字的最大差分方法，该方法将差值替换掉原来的数字不断放进集合中。其 Java 伪代码实现如下： int karmarkarKarpPartition(int[] baseArr) { // create max heap PriorityQueue heap = new PriorityQueue(baseArr.length, REVERSE_INT_CMP); for (int value : baseArr) { heap.add(value); } while (heap.size() >

1) {int val1 = heap.poll (); int val2 = heap.poll (); heap.add (val1-val2);}

Return heap.poll ();}

The algorithm includes input set S and parameter k. The S is divided into k subsets so that the sum of the numbers in these subsets is equal, thus the desired output is constructed. The algorithm includes the following key steps:

Arrange numbers in descending order

Replace the original number with a difference until there is only one number

The backtracking algorithm is used to complete the partition.

Applicability:

The algorithm assumes partition by building a binary tree. Each level represents a pair of numbers, the branch on the left replaces the number with a difference, and the branch on the right places the difference in the same subset. The algorithm first obtains the solution through the maximum difference, and then continues to find a better approximate solution. It requires a space complexity of O (n), but in the worst case it may require a time complexity of O (2 ^ n).

Packing problem

The packing problem has many practical applications. For example, how to fundamentally improve India's waste management system. This problem can be solved through the packing problem to help the authorities decide how many bins are needed for the x-volume of garbage.

Container ships: the practical application of the packing problem.

In the field of computer science, this problem can be used in a variety of memory management techniques. In this algorithm, we can package objects of different shapes and sizes by removing redundancy and minimizing space waste.

For example, given a set of n items, the size of each item is s 1, 2, 7, 5, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

Classic method:

1. Proximity adaptation algorithm (Next Fit): check whether the current item is suitable for the current box. If appropriate, put the item in the box, otherwise open a new box.

Let's look at an example: the items are 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6, and the box size is all 1.

Packing solution based on proximity adaptation algorithm (M = total number of boxes = 6).

two。 First matching method (First Fit): browse the boxes sequentially, place new items in the first box, and then enable the new boxes until they can't fit.

Let's look at an example: the items are 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6, and the size of the box is 1.

A packing solution based on the first matching method (M = total number of boxes = 5).

3. Optimal matching method (Best Fit): browse the boxes in order and put each new item in the most suitable box. If it does not fit, create a new box.

Let's look at an example: the items are 0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6, and the size of the box is 1.

Packing solution based on optimal matching method (M = total number of boxes = 5).

The output of this method is the same as that of the first matching method, but the advantage of this method is that it is faster than FFD, that is, the time complexity is O (nlogn).

Natural methods:

If we know the size of all items in advance, the natural solution is to sort them first from largest to smallest, and then apply the following heuristics:

First matching decreasing method

Optimal matching decreasing method

Assuming the same examples 0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1, the sort is 0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1.

Optimization method (M = total number of boxes = 4).

At this point, the study of "what is an approximate algorithm" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.