什么是固定参数易处理性？为什么是它有用吗？ [英] What is fixed-parameter tractability? Why is it useful?
问题描述
有些问题是NP难也固定参数可解或FPT。维基百科描述了一个问题，因为固定参数可解，如果有一个算法，解决它在时间t（K）＆middot; | x | O（1）
这是什么意思？为什么这个概念有用吗？
首先，假设P＆NE下;的NP，没有多项式时间，精确的算法为任何NP难题。虽然我们不知道是否P = NP或P＆NE; NP，我们没有任何NP难问题的任何多项式算法。
背后的固定参数易处理的想法是把一个NP难的问题，这是我们不知道任何多项式算法，并尝试将复杂分离成两部分 - 某条依赖纯粹的输入的大小，以及一些片依赖于某些参数的问题。
作为一个例子，考虑 0/1背包问题。在这个问题中，你既然有相关的权重和值，以及，你可以从事一些最大重量W N对象的列表。现在的问题是确定的值，你可以随身携带的最高金额。这个问题是NP难的，这意味着没有多项式时间的算法，解决它。蛮力方法考虑的项目，这对于大的n非常缓慢的所有可能的子集，需要一段时间围绕O（2 N ）。然而，它能够解决在时间为O（NW），其中n是元件的数量和W是重量的可携带的量这种问题。如果你看一下运行O（NW），你会发现，它分为两个部分：一个组件，它是线性元素的数量（n个部分）和一个组件，它是线性的权重（在W的一部分）。如果W被固定的任何恒定的，则该算法的运行时间将是为O（n），它是线性时间，即使在一般的问题是NP难题。这意味着，如果我们把W¯¯作为问题某些可调参数，此参数的任何固定值，则问题最终在多项式时间运行（这是在复杂性理论意义上的易处理。）
作为另一实例，考虑寻找在图形长，简单路径的问题。这个问题也是NP难，和天真的算法发现在一个简单的图形长度为k的路径，需要时间为O（n /（N - k）的！），这对于大型ķ最终被superexponential。但是，使用颜色编码的技术，它可以解决这个问题的时间为O（（2E）< SUP> K N 3 log n）的，其中k是该路径的长度来查找和n是在输入图中节点的数目。请注意，此运行时也有两个组分：一种成分是在在输入图形节点的数目的多项式（在n 3 日志N部分），以及一个组件是指数在k-（所述（ 2E） K 的一部分）。这意味着对于任何k的固定值，有一个多项式时间算法查找图中的长度为k的路径;运行时会为O（n 3 log n）的。
在这两种情况下，我们可以采取一个问题，我们有一个指数时间的解决方案（或更糟），并找到一个新的解决方案，其运行时间是在n次一些多项式一些额外的参数的一些疯狂的前瞻性功能。在背包问题的情况下，该参数是重量我们可以进行的最大数量;在寻找长路径的情况下，该参数是路径的长度来找到。一般来说，一个问题称为固定参数可解如果有一些算法用于解决两个量来定义该问题：n，则输入的大小，和k，某些参数，其中运行时是
O（P（N）＆middot; F（K））
其中p（n）是一些多项式函数和f（k）是在k中任意的功能。直观地，这意味着该问题的复杂多项式鳞用正（意味着由于只有问题尺寸增大，运行时将很好地缩放），但是可以扩展任意严重与参数k。此分离出的固有硬度等问题的，问题的硬的部分是归咎于参数k，而该问题的容易的部分被充电到输入的大小。
一旦你有一个运行时，看起来像O（P（N）＆middot; F（K）），我们立即得到多项式算法解决问题的任何固定ķ。具体地，如果k是固定的，则f（k）是一些恒定，所以O（P（N）＆middot; F（k））的仅仅是O（P（N））。这是一个多项式时间的算法。因此，如果我们修正的参数，我们回来一些听话的算法来解决这个问题。这是长期的固定参数可解的起源。
（A注：固定参数可追踪性的维基百科的定义说，该算法应该有运行F（K）＆middot; | x | O（1）在这里，| x |指。 ，输入，我已经叫ñ这里的大小这意味着维基百科的定义是相同的话说，运行时间为f（K）＆middot; N O（1）正如<一个HREF =http://stackoverflow.com/questions/19506562/why-does-no1-mean-polynomial-time>在这个早期的答案，N O（1）办法一些多项式在N，等这个定义最终被等同于一个我在这里给定的）。
固定参数易处理性有一个问题，巨大的实际意义。这是常见的遭遇是NP难的问题。如果发现的问题，即是固定的，易于处理的参数和参数是低，它可以是显著更有效地使用固定参数可解算法使用比正常的蛮力算法。上述查找中的曲线图的长路径的颜色编码的例子，例如，已被用于大计算生物学成功找到在酵母细胞测序的途径，以及0/1背包的解决方案是经常使用因为W的共同价值足够低，它是实际的。
希望这有助于！
Some problems that are NP-hard are also fixed-parameter tractable, or FPT. Wikipedia describes a problem as fixed-parameter tractable if there's an algorithm that solves it in time f(k) · |x|O(1).
What does this mean? Why is this concept useful?
To begin with, under the assumption that P ≠ NP, there are no polynomial-time, exact algorithms for any NP-hard problem. Although we don't know whether P = NP or P ≠ NP, we don't have any polynomial-time algorithms for any NP-hard problems.
The idea behind fixed-parameter tractability is to take an NP-hard problem, which we don't know any polynomial-time algorithms for, and to try to separate out the complexity into two pieces - some piece that depends purely on the size of the input, and some piece that depends on some "parameter" to the problem.
As an example, consider the 0/1 knapsack problem. In this problem, you're given a list of n objects that have associated weights and values, along with some maximum weight W that you're allowed to carry. The question is to determine the maximum amount of value that you can carry. This problem is NP-hard, meaning that there's no polynomial-time algorithm that solves it. A brute-force method will take time around O(2n) by considering all possible subsets of the items, which is extremely slow for large n. However, it is possible to solve this problem in time O(nW), where n is the number of elements and W is the amount of weight you can carry. If you look at the runtime O(nW), you'll notice that it's split into two parts: a component that's linear in the number of elements (the n part) and a component that's linear in the weight (the W part). If W is any fixed constant, then the runtime of this algorithm will be O(n), which is linear-time, even though the problem in general is NP-hard. This means that if we treat W as some tunable "parameter" of the problem, for any fixed value of this parameter, the problem ends up running in polynomial time (which is "tractable," in the complexity theory sense of the word.)
As another example, consider the problem of finding long, simple paths in a graph. This problem is also NP-hard, and the naive algorithm for finding simple paths of length k in a graph takes time O(n! / (n - k)!), which for large k ends up being superexponential. However, using the technique of color-coding, it's possible to solve this problem in time O((2e)kn3 log n), where k is the length of the path to find and n is the number of nodes in the input graph. Notice that this runtime also has two "components:" one component that's a polynomial in the number of nodes in the input graph (the n3 log n part) and one component that's exponential in k (the (2e)k part). This means that for any fixed value of k, there's a polynomial-time algorithm for finding length-k paths in the graph; the runtime will be O(n3 log n).
In both of these cases, we can take a problem for which we have an exponential-time solution (or worse) and find a new solution whose runtime is some polynomial in n times some crazy-looking function of some extra "parameter." In the case of the knapsack problem, that parameter is the maximum amount of weight we can carry; in the case of finding long paths, the parameter is the length of the path to find. Generally speaking, a problem is called fixed-parameter tractable if there is some algorithm for solving the problem defined in terms of two quantities: n, the size of the input, and k, some "parameter," where the runtime is
O(p(n) · f(k))
Where p(n) is some polynomial function and f(k) is an arbitrary function in k. Intuitively, this means that the complexity of the problem scales polynomially with n (meaning that as only the problem size increases, the runtime will scale nicely), but can scale arbitrarily badly with the parameter k. This separates out the "inherent hardness" of the problem such that the "hard part" of the problem is blamed on the parameter k, while the "easy part" of the problem is charged to the size of the input.
Once you have a runtime that looks like O(p(n) · f(k)), we immediately get polynomial-time algorithms for solving the problem for any fixed k. Specifically, if k is fixed, then f(k) is some constant, so O(p(n) · f(k)) is just O(p(n)). This is a polynomial-time algorithm. Therefore, if we "fix" the parameter, we get back some "tractable" algorithm for solving the problem. This is the origin of the term fixed-parameter tractable.
(A note: Wikipedia's definition of fixed-parameter tractability says that the algorithm should have runtime f(k) · |x|O(1). Here, |x| refers to the size of the input, which I've called n here. This means that Wikipedia's definition is the same as saying that the runtime is f(k) · nO(1). As mentioned in this earlier answer, nO(1) means "some polynomial in n," and so this definition ends up being equivalent to the one I've given here).
Fixed-parameter tractability has enormous practical implications for a problem. It's common to encounter problems that are NP-hard. If you find a problem that's fixed-parameter tractable and the parameter is low, it can be significantly more efficient to use the fixed-parameter tractable algorithm than to use the normal brute-force algorithm. The color-coding example above for finding long paths in a graph, for example, has been used to great success in computational biology to find sequencing pathways in yeast cells, and the 0/1 knapsack solution is used frequently because common values of W are low enough for it to be practical.
Hope this helps!
这篇关于什么是固定参数易处理性？为什么是它有用吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
