Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Толық полиномиалдық уақытқа жуықтау схемасы (FPTAS) – функциялық есептерді, әсіресе оптимизациялау есептерін шамамен шешуге арналған алгоритм. FPTAS есептің бір мысалын және ε > 0 параметрін кіріс ретінде қабылдайды. Ол нәтиже ретінде дұрыс мәннен кеміндегі еселік және дұрыс мәннен көп емес еселік мәнді қайтарады. Оптимизациялау есептері контекстінде дұрыс мән – оптималды шешімнің мәні ретінде түсініледі, және FPTAS жарамды шешімді (және тек шешімнің мәнін емес) беруі керек деп көбінесе айтылады. Мән беру және сол мәнмен шешім табу, егер есеп өзін-өзі кешіру қабілетіне ие болса, эквивалентті. FPTAS-тың орындалу уақыты есеп көлеміне және 1/ε-ға полиномиалды. Бұл жалпы полиномиалдық уақытқа жуықтау схемасынан (PTAS) өзгеше. Жалпы PTAS-тың орындалу уақыты әрбір нақты ε үшін есеп көлемі бойынша полиномиалды, бірақ 1/ε бойынша экспоненциалды болуы мүмкін. FPTAS термині FPTAS-ы бар есептер класын білдіру үшін де қолданылуы мүмкін. FPTAS – PTAS-тың ішкі жиыны, және егер P = NP болмаса, ол қатаң ішкі жиын болып табылады.
A fully polynomial time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least times the correct value, and at most times the correct value. In the context of optimization problems, the correct value is understood to be the value of the optimal solution, and it is often implied that an FPTAS should produce a valid solution (and not just the value of the solution). Returning a value and finding a solution with that value are equivalent assuming that the problem possesses self reducibility. Importantly, the run time of an FPTAS is polynomial in the problem size and in 1/ε. This is in contrast to a general polynomial time approximation scheme (PTAS). The run time of a general PTAS is polynomial in the problem size for each specific ε, but might be exponential in 1/ε. The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.
Басқа күрделілік сыныптарымен байланыс
FPTAS-тағы барлық мәселелер стандартты параметрлеуге қатысты шешілуге жарамды. Полиномдық шектелген мақсаттық функциясы бар кез келген күшті NP-қиын оптимизациялық проблема P=NP болмаса FPTAS-қа ие болмайды. Дегенмен, керісінше дұрыс емес: мысалы, егер P, NP-ге тең болмаса, екі шектеуі бар рюкзак күшті NP-қиын болмаса да, ең жақсы мақсаттық функция полиномдық шектелген жағдайда да FPTAS-қа ие емес.
All problems in FPTAS are fixed parameter tractable with respect to the standard parameterization. Any strongly NP hard optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP. However, the converse fails: e. g. if P does not equal NP, knapsack with two constraints is not strongly NP hard, but has no FPTAS even when the optimal objective is polynomially bounded.
Динамикалық бағдарламаны FPTAS-қа түрлендіру
Вёгингер нақты бір динамикалық бағдарламаларды FPTAS-қа түрлендірудің жалпы жоспасын ұсынды.
Woeginger presented a general scheme for converting a certain class of dynamic programs to an FPTAS.
Үлгі емес
Жоғарыда көрсетілген нәтижелердің жалпылығына қарамастан, оны қолдануға болмайтын жағдайлар бар. 1. Толық кешігу мәселесінде 1||, Лоулердің динамикалық бағдарламалау түзілімі ескі күй кеңістігіндегі барлық күйлерді B рет жаңартуды қажет етеді, мұнда B X (максималды кіріс мөлшері) шамасында болады. Экономикалық партия көлемін анықтау үшін қолданылатын динамикалық бағдарлама үшін де осы жағдай орынды. Бұл жағдайларда F-дегі өту функцияларының саны B-ге тең, ал ол log(X) бойынша экспоненциалды болып келеді, сондықтан екінші техникалық талап бұзылады. Күйді қысқару әдісі тиімді емес, бірақ FPTAS құру үшін басқа әдіс – кіріс дөңгелектеу – қолданылды. 2. Дисперсияны азайту мәселесінде 1||, мақсаттық функция , бұл 2-ші талапты бұзады, сондықтан теорема қолданылмайды. Бірақ FPTAS құру үшін басқа техникалар қолданылды.
Despite the generality of the above result, there are cases in which it cannot be used. 1. In the total tardiness problem 1||, the dynamic programming formulation of Lawler requires to update all states in the old state space some B times, where B is of the order of X (the maximum input size). The same is true for a DP for economic lot sizing. In these cases, the number of transition functions in F is B, which is exponential in the log(X), so the second technical condition is violated. The state trimming technique is not useful, but another technique input rounding has been used to design an FPTAS. 2. In the variance minimization problem 1||, the objective function is , which violates Condition 2, so the theorem cannot be used. But different techniques have been used to design an FPTAS.
Нақты сандарды шамалау үшін FPTAS
FPTAS-тың пайдалы болуы мүмкін проблемалардың тағы бір түрі – нақты сандарға жуық рационалдық сандарды табу. Мысалы, шексіз қатардың сомасын қарастырайық. Бұл сан иррационалды. Оны рационалды санмен жуықтау үшін, біз алғашқы k мүшенің қосындысын есептейміз, мұнда k – шекті сан. Дәлелдеуге болады, жуықтау қателігі шамамен тең. Демек, ε қателігіне жету үшін шамамен мүше керек, сондықтан бұл FPTAS болып табылады. Атап айтқанда, осы соманы тек O(log(ε)) мүшесі қажет болатын басқа сома арқылы да көрсетуге болады, сондықтан сома ε кодтау ұзындығы бойынша көпмүшелік уақытта жуықталуы мүмкін.
A different kind of problems in which FPTAS may be useful is finding rational numbers that approximate some real numbers. For example, consider the infinite series The sum is an irrational number. To approximate it by a rational number, we can compute the sum of the first k elements, for some finite k. One can show that the error in approximation is about Therefore, to get an error of ε, we need about elements, so this is an FPTAS. Note that this particular sum can be represented by another sum in which only O(log(ε)) elements are needed, so the sum can actually be approximated in polynomial time in the encoding length of ε.