Жақындық алгоритмдерін талдаудың үстемдік талдауы

Кіріспе

Доминациялық талдау – 1997 жылы Гловер мен Пуннен енгізген, жақындастыру алгоритмінің өнімділігін бағалау тәсілі. Классикалық жақындастыру қатынасының талдауынан айырмашылығы, бұл есептелген шешімнің сандық сапасын ең оңтайлы шешіммен салыстырады, ал доминациялық талдау барлық мүмкін шешімдердің реттелген тізіміндегі есептелген шешімнің орнын қарастырады. Осы талдау стилінде алгоритмнің доминанттық саны немесе үстемдік саны K деп айтылады, егер алгоритмнің нәтижесі ең жақсы болатын K түрлі шешімдер жиынтығы болса. Доминациялық талдауды доминация коэффициентін пайдалану арқылы да көрсетуге болады, бұл берілген шешімнен нашар емес шешім кеңістігінің үлесін білдіреді; бұл сан әрқашан [0,1] аралығында болады, ал үлкен сандар жақсы шешімдерді көрсетеді. Доминациялық талдау көбінесе мүмкін шешімдердің жалпы саны белгілі және дәл шешім табу қиын мәселелерге қолданылады. Мысалы, саяхатшы мәселесінде n қаласы бар мәселе мысалы үшін (n-1)! мүмкін шешім бар. Егер алгоритмнің доминанттық саны (n-1)!-ге жақын немесе эквивалентті түрде доминация коэффициенті 1-ге жақын екені көрсетілсе, онда оны доминанттық саны төмен алгоритмге қарағанда артық деп санауға болады. Егер мәселенің шешім кеңістігінен кездейсоқ үлгілерді тиімді табу мүмкін болса, мысалы саяхатшы мәселесінде, онда кездейсоқ алгоритм үшін жоғары ықтималдықпен жоғары доминация коэффициенті бар шешімді табу оңай: жай ғана үлгілер жиынтығын құрастырып, олардың ішіндегі ең жақсы шешімді таңдаңыз. (Мысалы, Орлин мен Шармаға қараңыз.) Мұнда сипатталған доминанттық санды графтың доминанттық санымен шатастыруға болмайды, ол графтың ең кіші доминанттық жиынтығындағы төбелердің санын білдіреді. Соңғы уақытта эвристиканың тиімділігін бағалау үшін доминациялық талдау қолданылатын мақалалар саны артып келеді. Бұл талдау түрі классикалық жақындастыру қатынасын талдау дәстүрімен бәсекелес ретінде қарастырылуы мүмкін. Екі өлшем де бір-бірін толықтыратын болып саналады.

Domination analysis of an approximation algorithm is a way to estimate its performance, introduced by Glover and Punnen in 1997. Unlike the classical approximation ratio analysis, which compares the numerical quality of a calculated solution with that of an optimal solution, domination analysis involves examining the rank of the calculated solution in the sorted order of all possible solutions. In this style of analysis, an algorithm is said to have dominance number or domination number K, if there exists a subset of K different solutions to the problem among which the algorithm's output is the best. Domination analysis can also be expressed using a domination ratio, which is the fraction of the solution space that is no better than the given solution; this number always lies within the interval [0,1], with larger numbers indicating better solutions. Domination analysis is most commonly applied to problems for which the total number of possible solutions is known and for which exact solution is difficult. For instance, in the Traveling salesman problem, there are (n 1)! possible solutions for a problem instance with n cities. If an algorithm can be shown to have dominance number close to (n 1)!, or equivalently to have domination ratio close to 1, then it can be taken as preferable to an algorithm with lower dominance number. If it is possible to efficiently find random samples of a problem's solution space, as it is in the Traveling salesman problem, then it is straightforward for a randomized algorithm to find a solution that with high probability has high domination ratio: simply construct a set of samples and select the best solution from among them. (See, e. g., Orlin and Sharma.) The dominance number described here should not be confused with the domination number of a graph, which refers to the number of vertices in the smallest dominating set of the graph. Recently, a growing number of articles in which domination analysis has been applied to assess the performance of heuristics has appeared. This kind of analysis may be seen as competing with the classical approximation ratio analysis tradition. The two measures may also be viewed as complementary.

Белгілі нәтижелер

Бұл бөлімде белгілі нәтижелердің техникалық сараптамасы келтірілген.

Басты бет

Жақындастырылмайтындық. Егер ε > 0 болса, және P=NP болмаса, Vertex Cover үшін доминациялық саны 3^((n n^ε)/3) шамасынан артық болатын полиномиалды алгоритм жоқ.

Қапшық

Жақындастырылмайтындық. Егер ε > 0 болса, P=NP болмаған жағдайда, Knapsack үшін оның доминация саны 2^(n n^ε) шамасынан артық болатын полиномиалдық алгоритм жоқ.