Екі жақты проблема - Constraint satisfaction dual problem

The қос мәселе а-ны қайта құру болып табылады шектеулерді қанағаттандыру проблемасы бастапқы мәселенің әр шектеуін айнымалы ретінде білдіру. Қос проблемалар тек қана қамтиды екілік шектеулер, сондықтан шешіледі алгоритмдер осындай проблемаларға сәйкес жасалған. The графиктерге қосылу және ағаштарға қосылыңыз шектеулі қанағаттандыру проблемасы болып табылады графиктер оның қос мәселесін немесе кейбір қосымша шектеулерді алып тастайтын қос есептерден алынған проблеманы білдіреді.

Қос мәселе

Шектеуді қанағаттандыру мәселесінің қосарлы мәселесінде бастапқы есептің әр шектеуі үшін айнымалы болады. Оның домендері мен шектеулері бастапқы проблемаға баламалылықты қамтамасыз ету үшін салынған. Атап айтқанда, қос есептің айнымалысының домені тиісті түпнұсқалық шектеуді қанағаттандыратын әр кортеж үшін бір элементтен тұрады. Осылайша, екі айнымалы, егер тиісті түпнұсқалық шектеу тиісті кортежді қанағаттандырса ғана мән қабылдай алады.

Екі есептің шектеулері екі үйлесімді айнымалыларға сәйкес келмейтін екі кортежге сәйкес келетін мәндерді алуға тыйым салады. Бұл шектеулер болмаса, бір қос айнымалы кортежге сәйкес мәнді қабылдай алады ${displaystyle x = 1, y = 2}$ ал басқа екі айнымалы мән сәйкес келетін мәнді алады ${displaystyle y = 3, z = 1}$, басқа мәнді тағайындайды ${displaystyle y}$.

Жалпы алғанда, қос проблеманың шектеулері екі шектеумен бөлінетін барлық айнымалылар үшін бірдей мәндерді қолданады. Егер екі қос айнымалылар кейбір айнымалыларды бөлуге арналған шектеулерге сәйкес келсе, қос есепте олардың арасындағы шектеулер бар, олар барлық ортақ айнымалылардың теңдігін қамтамасыз етеді.

	Қос айнымалылар - бұл бастапқы есептің шектеулері.
	Әрбір қос айнымалының домені - сәйкес бастапқы шектеу кортеждерінің жиынтығы.
	Қос шектеулер екі айнымалыны (бастапқы шектеулер) бастапқы айнымалылардың тең мәндерін қамтитын мәндерге (түпнұсқа кортеждер) ие болуға мәжбүр етеді. Бұл мысалда бастапқы шектеулер ${displaystyle C_ {1}}$ және ${displaystyle C_ {2}}$ айнымалыны бөлісу ${displaystyle y}$. Қос есепте айнымалылар ${displaystyle C_ {1}}$ және ${displaystyle C_ {2}}$ мәндерге ие болуға рұқсат етіледі ${displaystyle (1,2)}$ және ${displaystyle (2,1)}$ өйткені бұл құндылықтар келіседі ${displaystyle y = 2}$.

Қос есепте барлық шектеулер екілік сипатта болады. Олардың барлығы бір немесе бірнеше бастапқы айнымалыларды келісу үшін кортеждер болып табылатын екі мәнді қолданады.

The қос сызба - бұл қосарланған есепте айнымалылардың қалай шектелетінін бейнелеу. Дәлірек айтсақ, қосарланған графикте әрбір екі айнымалыға арналған түйін және олардың арасындағы барлық шектеулерге арналған шеті бар. Сонымен қатар, екі айнымалының арасындағы жиек осы екі қос айнымалының арасында тең орындалатын бастапқы айнымалылармен белгіленеді.

Қос графикті бастапқы проблемадан тікелей құруға болады: оның құрамында әр шектеу үшін шың, ал айнымалылармен бөлісетін әрбір екі шектеулер арасындағы шегі бар; мұндай жиек осы ортақ айнымалылармен белгіленеді.

Қос граф. Екі шектеу арасындағы шекара олардың ортақ айнымалыларының теңдігін қамтамасыз ететін қос шектеуге сәйкес келеді. Мысалы, белгіленген шеті ${displaystyle x, y}$ арасында ${displaystyle C_ {1}}$ және ${displaystyle C_ {2}}$ қос проблеманың арасындағы шектеу бар екенін көрсетеді ${displaystyle C_ {1}}$ және ${displaystyle C_ {2}}$, және бұл шектеу сәйкес келетін мәндерді (кортеждерді) күшейтеді ${displaystyle x}$ және ${displaystyle y}$.

Графиктерді қосып, ағаштарды біріктіріңіз

Қосарланған графикада кейбір шектеулер қажет емес болуы мүмкін. Шынында да, қос шектеулер бастапқы айнымалылардың теңдігін қамтамасыз етеді, ал кейбір шектеулер теңдіктің транзитивтілігіне байланысты артық болуы мүмкін. Мысалы, егер ${displaystyle C_ {2}}$ және ${displaystyle C_ {1}}$ белгілері бар жиекпен біріктіріледі ${displaystyle y}$, және солай ${displaystyle C_ {1}}$ және ${displaystyle C_ {3}}$, теңдігі ${displaystyle y}$ барлық үш айнымалыға кепілдік берілген. Нәтижесінде арасындағы екі жақты шектеу ${displaystyle C_ {2}}$ және ${displaystyle C_ {3}}$ теңдігін қамтамасыз ету ${displaystyle y}$ қажет емес, егер бар болса, оны алып тастауға болады.

Теңдігінен бастап ${displaystyle y}$ арасындағы екі шектеу қойылады ${displaystyle C_ {2}}$ және ${displaystyle C_ {3}}$ тастауға болады.

Қосымша графиктен кейбір артық шеттерін алып тастау арқылы алынған график а деп аталады графикке қосылу. Егер ол ағаш болса, оны а деп атайды ағашқа қосыл. Қос есепті біріктіру графигінен шешуге болады, өйткені барлық жойылған шеттер қажет емес. Өз кезегінде, егер ациклдік шектеулерді қанағаттандыру проблемаларына арналған алгоритмдерді қолдана отырып, егер біріктіру графы ағаш болса, мәселені тиімді шешуге болады.

Қосылу ағашын табу, егер бар болса, келесі қасиеттерді пайдалану арқылы жүзеге асырылуы мүмкін: егер қос графикада біріктіру ағашы болса, онда ең үлкен салмақ ағаштар егер сызықтар айнымалылар санымен өлшенетін болса, сызбаның барлығы біріктірілген ағаштар болып табылады. Егер бар болса, біріктіру ағашын табудың алгоритмі келесідей жүреді. Бірінші қадамда шеттерге салмақ беріледі: егер екі түйін ортақ шектеулерді білдірсе ${displaystyle n}$ айнымалылар, оларды біріктіретін шеге салмақ беріледі ${displaystyle n}$. Екінші қадамда ең үлкен салмақты ағаш ізделеді. Біреуі табылғаннан кейін, ол айнымалылардың қажетті теңдігін орындай ма, жоқ па тексеріледі. Егер бұл жағдай болса, онда бұл таралған ағаш - бұл біріктірілген ағаш.

Шектеуді қанағаттандыру проблемасының біріктіру ағашы бар-жоғын анықтайтын тағы бір әдіс қос графиктен гөрі, есептің бастапқы сызбасын қолданады. The бастапқы график шектеулерді қанағаттандыру проблемасының түйіндері проблемалық айнымалылар болатын және шеттері бірдей шектеулі екі айнымалының болуын білдіретін график. Мәселе үшін біріктіру ағашы келесі жағдайда болады:

1. бастапқы график аккорд;
2. әрқайсысының айнымалылары максималды клик бастапқы графиктің шектеу аумағы және керісінше; бұл қасиет деп аталады сәйкестік.

Өз кезегінде аккордальды a көмегімен тексеруге болады максималды тапсырыс айнымалылар. Мұндай тапсырысты, егер жоғарыдағы екі шарт орындалса, мәселенің түйіскен ағашын табу үшін де қолдануға болады. Тапсырысқа сәйкес шектеулерді олардың ең үлкен айнымалысы бойынша ретке келтіру, біріктіру ағашын шығарудың алгоритмі соңғыдан бірінші шектеуге дейін жүреді; әр қадамда, шектеу онымен айнымалылардың максималды санын бөлуге мүмкіндік береді, ол реттіліктің алдында тұрған шектеулер арасында.

Кеңейтімдер

Барлық шектеулерді қанағаттандыру проблемаларының біріккен ағашы болмайды. Алайда, түйісу ағашын алу үшін проблемаларды өзгертуге болады. Ағаштар кластері - проблемаларды бірлескен ағашқа ие болатындай етіп өзгертудің нақты әдісі. Бұл шектеулерді біріктіру арқылы жүзеге асырылады, бұл әдетте проблеманың көлемін арттырады; алайда, туындайтын мәселені шешу оңай, өйткені бұл барлық ағаштарға арналған.

Ыдырау әдістері біріктірілген ағаш кластерлерін айнымалыларды топтастыру арқылы жалпылау, алынған есепте біріктіру ағашы болады. Ыдырау әдістері ағашты мәселелермен тікелей байланыстырады; осы ағаштың түйіндері бастапқы проблеманың айнымалыларымен және / немесе шектеулерімен байланысты. Осы ағашқа негізделген шектеулерді біріктіру арқылы біріккен ағашы бар проблема туындауы мүмкін және бұл біріктіру ағашы ыдырау ағашынан оңай шығады. Сонымен қатар, екілік ациклдік мәселені тікелей ыдырау ағашынан құрастыруға болады.

Әдебиеттер тізімі

• Дечтер, Рина (2003). Шектеуді өңдеу. Морган Кауфман. ISBN  978-1-55860-890-0
• Дауни, Род; M. Fellows (1997). Параметрленген күрделілік. Спрингер. ISBN  978-0-387-94883-6
• Джордж Готтлоб; Никола Леоне; Франческо Скарчелло (2001). «Гипертрездің ыдырауы: сауалнама». MFCS 2001. 37-57 бет.^{[өлі сілтеме ]}

Сондай-ақ қараңыз

• Жасырын түрлендіру