Кіріспе
Компьютерлік ғылымдағы шешім проблемасы – компьютерлік ғылымдағы шешім проблемасы. Оның ең жалпы тұжырымдамасы бойынша, бүтін сандардың көп жиынтығы және мақсатты сома бар, ал мәселе бүтін сандардың кез келген кіші жиынтығының сомасы дәл мақсатты сомаға тең болатынын анықтау болып табылады. Мәселе NP қиын деп танымал. Оның үстіне, оның кейбір шектеулі нұсқалары да NP толық, мысалы: Оны 3 өлшемді сәйкестендіруден (3DM) азайту арқылы дәлелдеуге болады: Бізге 3DM мысалы берілген, онда төбелер жиынтығы W, X, Y. Әр жиынның n төбесі бар. m қабырға бар, мұнда әр қабырғада W, X, Y-дің әрқайсысынан дәл бір төбе бар. L := ceiling(log2(m+1)) деп белгілейік, сондықтан L қабырғалар санын көрсетуге қажетті биттер санынан үлкен. Біз m оң бүтін санмен SSP-нің бір данасын құрастырамыз. Бүтін сандар олардың екілік көрсетілімімен сипатталады. Әрбір кіріс бүтін санын 3nL биттермен көрсетуге болады, олар L биттен тұратын 3n аймаққа бөлінеді. Әрбір аймақ бір төбеге сәйкес келеді. 3DM мысалындағы әр қабырға (w,x,y) үшін SSP мысалында дәл үш бит "1" болып табылатын бүтін сан бар: w, x және y төбелерінің аймақтарындағы ең кіші маңызды биттер. Мысалы, егер n=10 және L=3, және W=(0, ..., 9), X=(10, ..., 19), Y=(20, ..., 29), онда (0, 10, 20) қабырғасы (20+230+260) санымен көрсетіледі. SSP мысалындағы мақсатты T сомасы әр аймақтың ең кіші маңызды битіне "1" қосылған бүтін санға тең болады, яғни (20+21+...+23n-1). Егер 3DM мысалында толық сәйкестік болса, онда SSP мысалындағы сәйкес бүтін сандарды қосу дәл T-ны береді. Керісінше, егер SSP мысалында толық T сомасы бар кіші жиын болса, онда аймақтар жеткілікті үлкен болғандықтан, бір аймақтан екіншісіне "көшу" болмайды, сондықтан сома 3DM мысалындағы толық сәйкестікке сәйкес болуы керек. Келесі нұсқалар да NP қиын деп танылады:
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target sum , and the question is to decide whether any subset of the integers sum to precisely The problem is known to be NP hard. Moreover, some restricted variants of it are NP complete too, for example: It can also be proved by reduction from 3 dimensional matching (3DM):
We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has n vertices. There are m edges, where each edge contains exactly one vertex from each of W, X, Y. Denote L := ceiling(log2(m+1)), so that L is larger than the number of bits required to represent the number of edges. We construct an instance of SSP with m positive integers. The integers are described by their binary representation. Each input integer can be represented by 3nL bits, divided into 3n zones of L bits. Each zone corresponds to a vertex. For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least significant bits in the zones of the vertices w, x, and y. For example, if n=10 and L=3, and W=(0, ,9), X=(10, ,19), Y=(20, ,29), then the edge (0, 10, 20) is represented by the number (20+230+260). The target sum T in the SSP instance is set to an integer with "1" in the least significant bit of every zone, that is, (20+21+ +23n 1). If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T.
Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance. The following variants are also known to be NP hard:
The input integers can be both positive and negative, and the target sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Given a solution to the SubsetSumPositive instance, adding the −T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the −T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance. The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem. The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is #P complete.
Кіріс бүтін сандары оң және теріс болуы мүмкін, ал мақсатты сома T = 0. Мұны оң бүтін сандар бар нұсқадан азайту арқылы дәлелдеуге болады. Бұл нұсқаны SubsetSumPositive және ағымдағы нұсқаны SubsetSumZero деп белгілейік. SubsetSumPositive (S, T) мысалын келтіре отырып, SubsetSumZero мысалын -T мәні бар бір элементті қосу арқылы құрастырыңыз. SubsetSumPositive мысалының шешімі берілген кезде, -T қосу SubsetSumZero мысалының шешімін береді. Керісінше, SubsetSumZero мысалының шешімі берілген болса, онда -T болуы керек (себебі S-дегі барлық бүтін сандар оң), сондықтан нөлдің сомасын алу үшін, ол +T сомасы бар S-дің кіші жиынтығын қамтуы керек, бұл SubsetSumPositive мысалының шешімі. Кіріс бүтін сандары оң, ал T = sum(S)/2. Бұл жалпы нұсқадан азайту арқылы дәлелденуі мүмкін; бөлім проблемасын қараңыз. Мақсатты сомаға қосылатын кіші жиынтықтардың санын санауды сұрайтын ұқсас есептеу мәселесі #SSP, #P толық.
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target sum , and the question is to decide whether any subset of the integers sum to precisely The problem is known to be NP hard. Moreover, some restricted variants of it are NP complete too, for example: It can also be proved by reduction from 3 dimensional matching (3DM):
We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has n vertices. There are m edges, where each edge contains exactly one vertex from each of W, X, Y. Denote L := ceiling(log2(m+1)), so that L is larger than the number of bits required to represent the number of edges. We construct an instance of SSP with m positive integers. The integers are described by their binary representation. Each input integer can be represented by 3nL bits, divided into 3n zones of L bits. Each zone corresponds to a vertex. For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least significant bits in the zones of the vertices w, x, and y. For example, if n=10 and L=3, and W=(0, ,9), X=(10, ,19), Y=(20, ,29), then the edge (0, 10, 20) is represented by the number (20+230+260). The target sum T in the SSP instance is set to an integer with "1" in the least significant bit of every zone, that is, (20+21+ +23n 1). If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T.
Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance. The following variants are also known to be NP hard:
The input integers can be both positive and negative, and the target sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Given a solution to the SubsetSumPositive instance, adding the −T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the −T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance. The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem. The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is #P complete.
Экспоненциалдық уақыт алгоритмдері
SSP-ді n-ге қатысты экспоненциалды уақытта шешудің бірнеше тәсілі бар.
Қосылу/шығару
Ең қарапайым алгоритм – n санның барлық ішкі жиынтықтарын қарап шығу және әрқайсысы үшін ішкі жиынтықтың дұрыс санға тең болатынын тексеру. Орындалу уақыты шамамен , себебі ішкі жиынтықтар бар, ал әрбір ішкі жиынтықты тексеру үшін ең көп дегенде n элементті қосу қажет. Алгоритмді бинарлық ағаштың тереңдікке бірінші іздеу арқылы жүзеге асыруға болады: ағаштың әрбір деңгейі кіріс санына сәйкес келеді; сол тармақ – санды жиынтықтан шығаруға, ал оң тармақ – санды қосуға сәйкес келеді (содан бері «қосу-алып тастау» атауы пайда болды). Қажетті жад: Орындалу уақытын бірнеше эвристикалар арқылы жақсартуға болады: жылдамырақ экспоненциалдық уақыт алгоритмі жарияланды, ол уақытында жұмыс істейді, бірақ әлдеқайда көп жадты қажет етеді. Алгоритм n элементті кездейсоқ түрде әрқайсысынан элементтен тұратын екі жиынтыққа бөледі. Осы екі жиынтықтың әрқайсысы үшін ол элементтерінің барлық мүмкін ішкі жиынтықтарының қосындыларының тізімін сақтайды. Осы екі тізімнің әрқайсысы содан кейін сұрыпталады. Тіпті ең жылдам салыстыру сұрыптау алгоритмін қолданғанда, мысалы, Mergesort бұл қадамға уақыт қажет болар еді. Дегенмен, элемент үшін қосындылардың сұрыпталған тізімі болғанда, тізімді екі сұрыпталған тізімге дейін кеңейтуге болады. Бірінші массивтегі ағымдағы элемент пен екінші массивтегі ағымдағы элементтің қосындысы T-дан жоғары болса, алгоритм бірінші массивтегі келесі элементке көшеді. Егер ол T-дан төмен болса, алгоритм екінші массивтегі келесі элементке көшеді. Егер T-ға тең болатын екі элемент табылса, ол тоқтатылады. (Екі элементтің қосындысы мәселесі «екінің қосындысы» деп белгілі.)
Шропель мен Шамир
1981 жылы Шропель мен Шамир Хоровиц пен Санхи негізінде ұқсас орындалу уақытын, бірақ әлдеқайда аз орынды қажет ететін алгоритм ұсынды. Олар n/2 элементінің барлық кіші жиынтықтарын алдын ала жасау мен сақтаудың орнына, элементтерді әрқайсысы n/4 элементтен тұратын 4 жиынтыққа бөледі және min үйірмесін пайдаланып n/2 элементті жұптардың кіші жиынтықтарын динамикалық түрде жасайды. Бұл жоғарыда аталған уақыт және орын күрделілігін қамтамасыз етеді, себебі мұны ұзақтығы k болатын 4 тізімде және орын бойынша орындауға болады. Олар сондай-ақ кеңістікті пайдаланып уақытында бұрынғы алгоритмдердің бәрінен де жылдам жұмыс істейтін ықтималдық алгоритмін ұсынды. Ол тек шешімді табу мәселесін шешеді, берілген сомаға шешімнің жоқтығын дәлелдей алмайды және T-ге ең жақын кіші жиынның сомасын қайтармайды. Howgrave Graham және Joux әдістері кейіннен кеңейтілді, нәтижесінде уақыт күрделілігі .
Due to space requirements, the HS algorithm is practical for up to about 50 integers, and the SS algorithm is practical for up to 100 integers. presented a probabilistic algorithm that runs faster than all previous ones in time using space It solves only the decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to T.
The techniques of Howgrave Graham and Joux were subsequently extended bringing the time complexity to .
Көптік уақытпен жуықтау алгоритмдері
Барлық кірістер оң деп есептейік. SSP үшін жуықтама алгоритмі S жиынының T-дан аспайтын және оптималдық соманың r еселенгенінен кем емес кіші жиынтығын табуға бағытталған, мұнда r – (0,1) аралығындағы жуықтама коэффициенті болып табылатын сан.