Цю статтю треба для відповідності Вікіпедії. (липень 2017) |
Ідея перевірки локальної сумісності лягла в основу швидкого методу , який є значно потужнішим порівняно з . Стани локальної сумісності є властивостями (CSP). Перевірка локальної сумісності забезпечується розширенням методу . Найвідомішими сумісностями є: сумісність дуг, сумісність вузла і сумісність шляху.
Положення
Розповсюдження обмеження (constraint propagation) — це загальна назва методів розповсюдження на інші змінні наслідків застосування деякого обмеження до однієї змінної; в даному випадку необхідно розповсюдити обмеження з WA і Q на NT і SA, а потім — на обмеження між NT і SA, щоб виявити зазначену несумісність. До того ж бажано, щоб така операція виконувалася швидко: немає сенсу обмежувати таким чином обсяг пошуку, якщо буде витрачатися більше часу на поширення обмежень, ніж на виконання простого пошуку.
Локальна сумісність (K-сумісність)
Строгіші форми розповсюдження обмеження можна визначити за допомогою поняття k-сумісності. Задача CSP є k-сумісною, якщо для будь-якої множини k-1 змінних і для будь-якого сумісного присвоювання значень цим змінним будь-якій k-й змінній завжди можна присвоїти деяке сумісне значення. Наприклад, 1-сумісність означає, що сумісною є кожна окрема змінна сама по собі, це поняття називають також сумісністю вузла. Далі, 2-сумісність — те саме, що й сумісність дуги, а 3-сумісність означає, що будь-яка пара суміжних змінних завжди може бути доповнена третьою сусідньою змінною; це поняття іменується також сумісністю шляху.
Будь-який граф називається строго k-сумісним, якщо він є k-сумісним, а також (к-1)-сумісним, (к-2)-сумісним, … і т. д. аж до 1-сумісного. Тепер припустимо, що є деяка задача CSP з вузлами n, яка зроблена строго n-сумісною (тобто строго k-сумісною для k=n). Тоді це завдання можна вирішити без повернень. Для цього спочатку можна вибрати сумісне значення для x1. В такому випадку існує гарантія, що вдасться обрати значення для х2, оскільки граф є 2-сумісним, для х3, оскільки він — 3-сумісний, і т. д. Для кожної змінної xi необхідно виконати пошук тільки серед d значень в її області визначення, щоб знайти значення, сумісний з x1 .., xi-1. Це означає, що гарантується перебування рішення за час O(nd). Безумовно, за таку можливість також доводиться платити: будь-який алгоритм забезпечення n-сумісності в найгіршому випадку повинен вимагати часу, експоненційно залежного від n.
Сумісність дуг
Ідея перевірки сумісності дуг лягла в основу швидкого методу розповсюдження обмежень. У цьому випадку термін дуга позначає орієнтоване ребро в графі обмежень, таке як дуга від SA до NSW. Якщо розглядаються поточні області визначення SA і NSW, то дуга є сумісною, якщо для кожного значення х змінної SA існує деяке значення у змінної NSW, сумісний із х. У третьому рядку на рис. 3 поточними областями визначення SA і NSW є {blue} і (red, blue) відповідно. При SA = blue існує сумісне присвоювання для NSW, а саме NSW = red, тому дуга від SA до NSW сумісна. З іншого боку, зворотна дуга від NSW до SA несумісна, оскільки стосовно присвоєння NSW = blue не існує сумісного присвоювання для SA. Цю дугу можна зробити сумісною, видаливши значення blue з області визначення NSW.
На тому ж етапі в процесі пошуку перевірку сумісності дуг можна також застосувати до дуги від SA до NT Третій рядок таблиці, наведеної на рис. 3, показує, що обидві змінні мають область визначення {blue}. Результатом стає те, що значення blue повинно бути видалено з області визначення SA, після чого ця область визначення залишається порожньою. Таким чином, застосування перевірки сумісності дуг привело до раннього виявлення несумісності.
Перевірку сумісності дуг можна використовувати або як етап перед початком процесу пошуку, або як етап розповсюдження обмеження (аналогічно попередній перевірці) після кожного присвоювання під час пошуку. (Останній алгоритм іноді називають MAC, скорочено позначаючи метод підтримки сумісності дуг — .) І в тому і в іншому випадку процес перевірки необхідно виконувати повторно, до тих пір, поки не перестануть виявлятися будь-які несумісності. Це пов'язано з тим, що при видаленні (з метою усунення деякої несумісності дуг) будь-якого значення з області визначення деякої змінної може з'явитися нова несумісність дуг в тих дугах, які вказують на цю змінну. У повному алгоритмі перевірки сумісності дуг, АС-3, використовується черга для відстеження дуг, які повинні бути перевірені на несумісність (лістинг 1). Кожна дуга (xi, xj) по черзі «знімається з порядку денного» і перевіряється; якщо з області визначення xi необхідно видалити будь-які значення, то кожна дуга (Хk, xi), яка вказує на xi, повинна бути повторно вставлена в чергу для перевірки. Складність перевірки сумісності дуг можна проаналізувати наступним чином: будь-яка бінарна задача CSP має щонайбільше O(n2) дуг; кожна дуга (xk, xi) може бути «внесена до порядку денного» тільки d раз, оскільки область визначення xi має щонайбільше d значень, доступних для видалення; перевірка сумісності будь дуги може бути виконана за час O(d2), тому в найгіршому випадку витрати часу становлять O(n2d3). Хоча такий метод є значно дорожчим у порівнянні з попередньою перевіркою, всі ці додаткові витрати зазвичай окупаються
Алгоритм перевірки сумісності дуг АС-3
function АС-3 (csp) returns визначення завдання CSP, можливо, зі скороченими областями визначення змінних inputs: csp, бінарна задача CSP зі змінними {Xi, Х2, ..., Хп} local variables: queue, чергу, складається з дуг, яка спочатку включає всі дуги з визначення завдання csp while черга queue не пуста do (Xi, Xj) ← Remove-First (gueue) if Remove-Inconsistent-Values (Xi, Xj) then for each Xk in Neighbors [Xi] do додати (Xk, Xi) до черги queue function Remove-Inconsistent-Values(Xi, Xj) returns Значення true тоді й тільки тоді, коли відбулося видалення деякого значення removed ← false for each х in Domain [Xi] do if жодне із значень у в області визначення Domain [Xj] не дозволяє використовувати (х, у) для задоволення обмеження, встановленого між Xi і Xj then видалити х з області визначення Domain [Xi] removed <— true return removed
Після застосування алгоритму АС-3 або кожна дуга є сумісною, або деяка змінна має порожню область визначення, вказуючи на те, що цю задачу CSP неможливо зробити сумісною по дугах (і тому дана не може бути вирішена). Позначення «АС-3» запропоновано розробником даного алгоритму, оскільки це — третя версія, представлена в його статті
Сумісність шляху
Сумісність шляху схожа на сумісність дуг, але передбачає пари змінних замість однієї. Пара змінних є шляхо-сумісною до третьої, якщо кожна сумісність пари може бути розширена на іншу змінну при тому що обмеження для двох змінних залишаються виконуваними. Формально xi і xj є шляхо-сумісні до x_k, якщо для кожної пари значень (a, b), що задовольняє подвійному обмеженню між xi і xj, існує значення с в області xk таке, що (a, c) і (b, c) задовольняє обмеження між xi і xk і між xj і xk, відповідно.
Форма розповсюдження обмежень, що забезпечує сумісність шляху працює шляхом видалення деяких застосувань, що виконуються з обмежень. Дійсно, сумісність шляху може бути забезпечена шляхом видалення з двійкового обмеження всіх оцінок, які не можуть бути поширені на інший змінні. Що стосується сумісності дуги, то подібне видалення, можливо, призведе до розгляду двійкового обмеження кілька разів.
Форма розповсюдження обмежень, що забезпечує сумісність шляху може ввести нові обмеження. Коли дві змінні не пов'язані між собою двійковим обмеженням, вони віртуально пов'язані обмеженням що дозволяє будь-яку кількість значень. Однак, деякі пари значень можуть бути видалені з розповсюдження обмежень. В результаті обмеження більше не задовольняє всі пари значень. Таким чином, це вже не віртуальний, тривіальні обмеження.
Застосування
Всі форми локальної сумісності можуть бути забезпечені за допомогою розповсюдження обмежень, яке може зменшити області змінних і наборів застосувань, що задовольнить обмеження і може ввести нові обмеження. Кожного разу, коли розповсюдження обмежень створює порожню область або нездійсненні обмеження, вихідна задача нездійсненна. Таким чином, всі форми локальної сумісності можуть бути використані для визначення здійсненності. Точніше, вони можуть бути використані як неповні алгоритми нездійсненності, так як вони можуть довести, що проблема є нездійсненною, але в цілому не в змозі довести, що завдання здійсненне. Такі алгоритми апроксимації можуть бути використані алгоритмами пошуку (, , , etc.), як евристики для повідомлення чи може часткове рішення бути розширенн, щоб задовольнити всі обмеження без подальшого його аналізу.
Навіть якщо розповсюдження обмежень не створює порожню область або нездійсненне обмеження, проте воно може зменшити області або підсилити обмеження. В цьому випадку, область пошуку задачі зменшується, таким чином, зменшуючи кількість пошуку необхідного для вирішення проблеми.
Локальна сумісність доводить здійснимість в деяких обмежених випадках (див. Складність задоволення обмежень). Це той випадок, для деякого особливого роду проблем і/або для деяких видів локальної сумісності. Наприклад, забезпечення узгодженості сумісності дуг на бінарних ациклічних задачах дозволяє сказати, чи є задача здійснимою.
Література
- Stuart, Russell; Peter Norvig (2004). . Prentice Hall. ISBN . Архів оригіналу за 7 листопада 2017. Процитовано 15 березня 2012.
- Lecoutre, Christophe (2009). . ISTE/Wiley. ISBN . Архів оригіналу за 7 листопада 2017. Процитовано 15 березня 2012.
На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до . |
Ця стаття потребує додаткових для поліпшення її . (січень 2016) |
Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cyu stattyu treba vikifikuvati dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit dodavannyam dorechnih vnutrishnih posilan abo vdoskonalennyam rozmitki statti lipen 2017 Ideya perevirki lokalnoyi sumisnosti lyagla v osnovu shvidkogo metodu yakij ye znachno potuzhnishim porivnyano z Stani lokalnoyi sumisnosti ye vlastivostyami CSP Perevirka lokalnoyi sumisnosti zabezpechuyetsya rozshirennyam metodu Najvidomishimi sumisnostyami ye sumisnist dug sumisnist vuzla i sumisnist shlyahu PolozhennyaRozpovsyudzhennya obmezhennya constraint propagation ce zagalna nazva metodiv rozpovsyudzhennya na inshi zminni naslidkiv zastosuvannya deyakogo obmezhennya do odniyeyi zminnoyi v danomu vipadku neobhidno rozpovsyuditi obmezhennya z WA i Q na NT i SA a potim na obmezhennya mizh NT i SA shob viyaviti zaznachenu nesumisnist Do togo zh bazhano shob taka operaciya vikonuvalasya shvidko nemaye sensu obmezhuvati takim chinom obsyag poshuku yaksho bude vitrachatisya bilshe chasu na poshirennya obmezhen nizh na vikonannya prostogo poshuku Lokalna sumisnist K sumisnist Strogishi formi rozpovsyudzhennya obmezhennya mozhna viznachiti za dopomogoyu ponyattya k sumisnosti Zadacha CSP ye k sumisnoyu yaksho dlya bud yakoyi mnozhini k 1 zminnih i dlya bud yakogo sumisnogo prisvoyuvannya znachen cim zminnim bud yakij k j zminnij zavzhdi mozhna prisvoyiti deyake sumisne znachennya Napriklad 1 sumisnist oznachaye sho sumisnoyu ye kozhna okrema zminna sama po sobi ce ponyattya nazivayut takozh sumisnistyu vuzla Dali 2 sumisnist te same sho j sumisnist dugi a 3 sumisnist oznachaye sho bud yaka para sumizhnih zminnih zavzhdi mozhe buti dopovnena tretoyu susidnoyu zminnoyu ce ponyattya imenuyetsya takozh sumisnistyu shlyahu Bud yakij graf nazivayetsya strogo k sumisnim yaksho vin ye k sumisnim a takozh k 1 sumisnim k 2 sumisnim i t d azh do 1 sumisnogo Teper pripustimo sho ye deyaka zadacha CSP z vuzlami n yaka zroblena strogo n sumisnoyu tobto strogo k sumisnoyu dlya k n Todi ce zavdannya mozhna virishiti bez povernen Dlya cogo spochatku mozhna vibrati sumisne znachennya dlya x1 V takomu vipadku isnuye garantiya sho vdastsya obrati znachennya dlya h2 oskilki graf ye 2 sumisnim dlya h3 oskilki vin 3 sumisnij i t d Dlya kozhnoyi zminnoyi xi neobhidno vikonati poshuk tilki sered d znachen v yiyi oblasti viznachennya shob znajti znachennya sumisnij z x1 xi 1 Ce oznachaye sho garantuyetsya perebuvannya rishennya za chas O nd Bezumovno za taku mozhlivist takozh dovoditsya platiti bud yakij algoritm zabezpechennya n sumisnosti v najgirshomu vipadku povinen vimagati chasu eksponencijno zalezhnogo vid n Sumisnist dug Ideya perevirki sumisnosti dug lyagla v osnovu shvidkogo metodu rozpovsyudzhennya obmezhen U comu vipadku termin duga poznachaye oriyentovane rebro v grafi obmezhen take yak duga vid SA do NSW Yaksho rozglyadayutsya potochni oblasti viznachennya SA i NSW to duga ye sumisnoyu yaksho dlya kozhnogo znachennya h zminnoyi SA isnuye deyake znachennya u zminnoyi NSW sumisnij iz h U tretomu ryadku na ris 3 potochnimi oblastyami viznachennya SA i NSW ye blue i red blue vidpovidno Pri SA blue isnuye sumisne prisvoyuvannya dlya NSW a same NSW red tomu duga vid SA do NSW sumisna Z inshogo boku zvorotna duga vid NSW do SA nesumisna oskilki stosovno prisvoyennya NSW blue ne isnuye sumisnogo prisvoyuvannya dlya SA Cyu dugu mozhna zrobiti sumisnoyu vidalivshi znachennya blue z oblasti viznachennya NSW Na tomu zh etapi v procesi poshuku perevirku sumisnosti dug mozhna takozh zastosuvati do dugi vid SA do NT Tretij ryadok tablici navedenoyi na ris 3 pokazuye sho obidvi zminni mayut oblast viznachennya blue Rezultatom staye te sho znachennya blue povinno buti vidaleno z oblasti viznachennya SA pislya chogo cya oblast viznachennya zalishayetsya porozhnoyu Takim chinom zastosuvannya perevirki sumisnosti dug privelo do rannogo viyavlennya nesumisnosti Perevirku sumisnosti dug mozhna vikoristovuvati abo yak etap pered pochatkom procesu poshuku abo yak etap rozpovsyudzhennya obmezhennya analogichno poperednij perevirci pislya kozhnogo prisvoyuvannya pid chas poshuku Ostannij algoritm inodi nazivayut MAC skorocheno poznachayuchi metod pidtrimki sumisnosti dug I v tomu i v inshomu vipadku proces perevirki neobhidno vikonuvati povtorno do tih pir poki ne perestanut viyavlyatisya bud yaki nesumisnosti Ce pov yazano z tim sho pri vidalenni z metoyu usunennya deyakoyi nesumisnosti dug bud yakogo znachennya z oblasti viznachennya deyakoyi zminnoyi mozhe z yavitisya nova nesumisnist dug v tih dugah yaki vkazuyut na cyu zminnu U povnomu algoritmi perevirki sumisnosti dug AS 3 vikoristovuyetsya cherga dlya vidstezhennya dug yaki povinni buti perevireni na nesumisnist listing 1 Kozhna duga xi xj po cherzi znimayetsya z poryadku dennogo i pereviryayetsya yaksho z oblasti viznachennya xi neobhidno vidaliti bud yaki znachennya to kozhna duga Hk xi yaka vkazuye na xi povinna buti povtorno vstavlena v chergu dlya perevirki Skladnist perevirki sumisnosti dug mozhna proanalizuvati nastupnim chinom bud yaka binarna zadacha CSP maye shonajbilshe O n2 dug kozhna duga xk xi mozhe buti vnesena do poryadku dennogo tilki d raz oskilki oblast viznachennya xi maye shonajbilshe d znachen dostupnih dlya vidalennya perevirka sumisnosti bud dugi mozhe buti vikonana za chas O d2 tomu v najgirshomu vipadku vitrati chasu stanovlyat O n2d3 Hocha takij metod ye znachno dorozhchim u porivnyanni z poperednoyu perevirkoyu vsi ci dodatkovi vitrati zazvichaj okupayutsya Algoritm perevirki sumisnosti dug AS 3 function AS 3 csp returns viznachennya zavdannya CSP mozhlivo zi skorochenimi oblastyami viznachennya zminnih inputs csp binarna zadacha CSP zi zminnimi Xi H2 Hp local variables queue chergu skladayetsya z dug yaka spochatku vklyuchaye vsi dugi z viznachennya zavdannya csp while cherga queue ne pusta do Xi Xj Remove First gueue if Remove Inconsistent Values Xi Xj then for each Xk in Neighbors Xi do dodati Xk Xi do chergi queue function Remove Inconsistent Values Xi Xj returns Znachennya true todi j tilki todi koli vidbulosya vidalennya deyakogo znachennya removed false for each h in Domain Xi do if zhodne iz znachen u v oblasti viznachennya Domain Xj ne dozvolyaye vikoristovuvati h u dlya zadovolennya obmezhennya vstanovlenogo mizh Xi i Xj then vidaliti h z oblasti viznachennya Domain Xi removed lt true return removed Pislya zastosuvannya algoritmu AS 3 abo kozhna duga ye sumisnoyu abo deyaka zminna maye porozhnyu oblast viznachennya vkazuyuchi na te sho cyu zadachu CSP nemozhlivo zrobiti sumisnoyu po dugah i tomu dana ne mozhe buti virishena Poznachennya AS 3 zaproponovano rozrobnikom danogo algoritmu oskilki ce tretya versiya predstavlena v jogo statti Sumisnist shlyahu x1 i x2 ne sumisni shlyahom do h3 Voni mozhut buti zrobleni sumisni shlyahom yaksho vidaliti sini znachennya z R12 Sumisnist shlyahu shozha na sumisnist dug ale peredbachaye pari zminnih zamist odniyeyi Para zminnih ye shlyaho sumisnoyu do tretoyi yaksho kozhna sumisnist pari mozhe buti rozshirena na inshu zminnu pri tomu sho obmezhennya dlya dvoh zminnih zalishayutsya vikonuvanimi Formalno xi i xj ye shlyaho sumisni do x k yaksho dlya kozhnoyi pari znachen a b sho zadovolnyaye podvijnomu obmezhennyu mizh xi i xj isnuye znachennya s v oblasti xk take sho a c i b c zadovolnyaye obmezhennya mizh xi i xk i mizh xj i xk vidpovidno Forma rozpovsyudzhennya obmezhen sho zabezpechuye sumisnist shlyahu pracyuye shlyahom vidalennya deyakih zastosuvan sho vikonuyutsya z obmezhen Dijsno sumisnist shlyahu mozhe buti zabezpechena shlyahom vidalennya z dvijkovogo obmezhennya vsih ocinok yaki ne mozhut buti poshireni na inshij zminni Sho stosuyetsya sumisnosti dugi to podibne vidalennya mozhlivo prizvede do rozglyadu dvijkovogo obmezhennya kilka raziv Dvi zminni bez obmezhennya pripuskayutsya obmezhenimi virtualnim obmezhennyam sho dozvolyaye bud yaku kilkist par znachen predstavlenih sinimi dugami na comu malyunku Dlya zabezpechennya sumisnoti shlyahu x1 ta x2 z x3 pribirayemo dugu zverhu Znachennya x1 and x2 bilshe ne ye vilnimi bo pov yazani novim aktualnim obmezhennyam Forma rozpovsyudzhennya obmezhen sho zabezpechuye sumisnist shlyahu mozhe vvesti novi obmezhennya Koli dvi zminni ne pov yazani mizh soboyu dvijkovim obmezhennyam voni virtualno pov yazani obmezhennyam sho dozvolyaye bud yaku kilkist znachen Odnak deyaki pari znachen mozhut buti vidaleni z rozpovsyudzhennya obmezhen V rezultati obmezhennya bilshe ne zadovolnyaye vsi pari znachen Takim chinom ce vzhe ne virtualnij trivialni obmezhennya ZastosuvannyaVsi formi lokalnoyi sumisnosti mozhut buti zabezpecheni za dopomogoyu rozpovsyudzhennya obmezhen yake mozhe zmenshiti oblasti zminnih i naboriv zastosuvan sho zadovolnit obmezhennya i mozhe vvesti novi obmezhennya Kozhnogo razu koli rozpovsyudzhennya obmezhen stvoryuye porozhnyu oblast abo nezdijsnenni obmezhennya vihidna zadacha nezdijsnenna Takim chinom vsi formi lokalnoyi sumisnosti mozhut buti vikoristani dlya viznachennya zdijsnennosti Tochnishe voni mozhut buti vikoristani yak nepovni algoritmi nezdijsnennosti tak yak voni mozhut dovesti sho problema ye nezdijsnennoyu ale v cilomu ne v zmozi dovesti sho zavdannya zdijsnenne Taki algoritmi aproksimaciyi mozhut buti vikoristani algoritmami poshuku etc yak evristiki dlya povidomlennya chi mozhe chastkove rishennya buti rozshirenn shob zadovolniti vsi obmezhennya bez podalshogo jogo analizu Navit yaksho rozpovsyudzhennya obmezhen ne stvoryuye porozhnyu oblast abo nezdijsnenne obmezhennya prote vono mozhe zmenshiti oblasti abo pidsiliti obmezhennya V comu vipadku oblast poshuku zadachi zmenshuyetsya takim chinom zmenshuyuchi kilkist poshuku neobhidnogo dlya virishennya problemi Lokalna sumisnist dovodit zdijsnimist v deyakih obmezhenih vipadkah div Skladnist zadovolennya obmezhen Ce toj vipadok dlya deyakogo osoblivogo rodu problem i abo dlya deyakih vidiv lokalnoyi sumisnosti Napriklad zabezpechennya uzgodzhenosti sumisnosti dug na binarnih aciklichnih zadachah dozvolyaye skazati chi ye zadacha zdijsnimoyu LiteraturaStuart Russell Peter Norvig 2004 Prentice Hall ISBN 3 8273 7089 2 Arhiv originalu za 7 listopada 2017 Procitovano 15 bereznya 2012 Lecoutre Christophe 2009 ISTE Wiley ISBN 978 1 84821 106 3 Arhiv originalu za 7 listopada 2017 Procitovano 15 bereznya 2012 Na cyu stattyu ne posilayutsya inshi statti Vikipediyi Bud laska rozstavte posilannya vidpovidno do prijnyatih rekomendacij Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno sichen 2016 Ce nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi