Увядзенне

---

Абмежаванне праграмавання ўзнікаюць тэхналогіі праграмнага забеспячэння для дэкларатыўнага апісанні і эфектыўнага вырашэння вялікіх, асабліва комбинаторных, праблемы, асабліва ў галіне планавання і складання раскладаў.

Крыху гісторыі ...
Абмежаванні ў апошні час з'явіліся як вобласць даследаванняў, якая аб'ядноўвае навукоўцаў з ліку палёў, у тым ліку штучны інтэлект, Мовы праграмавання, знакавых вылічэнняў і вылічальнай логікі. Абмежаванне сеткі і задавальненне праблемы абмежаванні былі вывучаныя ў вобласці штучнага інтэлекту, пачынаючы з сямідзесятых гадоў. Сістэматычнае выкарыстанне абмежаванняў у праграмаванні пачалася ў васьмідзесятых гадах. У абмежаванне праграмавання працэсу праграмавання складаецца з пакалення патрабаванняў (абмежаванняў) і рашэнне гэтых патрабаванняў, спецыялізаваныя решатель.

... і некаторыя дадатку.
Абмежаванне праграмавання паспяхова прымяняецца ў многіх галінах. Апошнія ўключаюць прыкладання камп'ютэрнай графікі (каб выказаць геаметрычнай узгодненасці ў выпадку аналізу сцэны), апрацоўкі натуральнай мовы (будаўніцтва эфектыўных аналізатараў), сістэм баз дадзеных (для забеспячэння і / або аднаўлення ўзгодненасці дадзеных), даследаванне аперацый праблемы (напрыклад, задачы аптымізацыі ), малекулярнай біялогіі (секвенирования ДНК), бізнес-дадаткі (опцыя гандаль), электратэхнікі (для пошуку няспраўнасцяў), разлік ланцуга (для разліку раскладкі) і інш

Сучасныя даследаванні ў гэтай вобласці мае справу з рознымі фундаментальных пытаннях, з аспектах ажыццяўлення, і новыя прыкладання абмежаванне праграмавання.

Што такое абмежаванне?
Абмежаванне проста лагічнай сувязі паміж некалькімі невядомымі (або зменных), кожны з якіх прымае значэнне ў гэтай галіне. Абмежаванне такім чынам абмяжоўвае магчымыя значэння зменных, якія можна ўзяць, ён уяўляе сабой некаторую частковую інфармацыю аб зменных, якія ўяўляюць цікавасць. Напрыклад, "круг у квадрат" ставіцца двух аб'ектаў без сапраўды паказаўшы свае пазіцыі, гэта значыць іх каардынаты. Цяпер можна рухацца квадратнай або круг, і ён ці яна ўсё яшчэ ў стане падтрымліваць сувязь паміж гэтымі двума аб'ектамі. Акрамя таго, можна хочаце дадаць іншы аб'ект, скажам, трыкутнік, і ўвесці іншае абмежаванне, скажам, "квадрат злева ад трохвугольніка". Ад карыстальніка (чалавека) кропкі гледжання, усё застаецца абсалютна празрыстай.

Абмежаванні натуральна карыстацца побач цікавых уласцівасцяў:

• абмежаванні могуць паказаць частковую інфармацыю, т. е. абмежаванні не павінны адназначна ўказаць значэння зменных,
• абмежаванні ненаправленный, як правіла, абмежаванне на (скажам) двух зменных X, Y могуць быць выкарыстаны для атрымліваем абмежаванне на X дадзена абмежаванне на Y, і наадварот.
• абмежаванні носяць дэкларатыўны характар, т. е. паказаць, якія адносіны павінны праводзіць без ўказанні вылічальнай працэдуры для забеспячэння гэтых адносін,
• абмежаванні з'яўляюцца адытыўная, т. е. парадку ўвядзення абмежаванняў не мае значэння, усё, што мае значэнне ў канцы, што сумесна абмежаванняў, па сутнасці,
• абмежаванні рэдка незалежныя, typicaly абмежаванняў ў абмежаванні долі зменных краме.

Абмежаванні натуральна ўзнікаюць ў многіх галінах чалавечай дзейнасці. Тры кута трыкутніка суму да 180 градусаў, сума токаў плавае ў вузле павінна быць роўная нулю, становішча скролерам ў акне пракруткі павінна адлюстроўваць бачную частка базавага дакумента, гэта толькі некаторыя прыклады абмежаванняў, якія з'яўляюцца ў рэальным свеце. Такім чынам, абмежаванні прыроднага асяроддзя для людзей, каб выказаць праблемы ў многіх галінах.

Такім чынам, што ж праграмавання справу з абмежаваннем?
Абмежаванне праграмавання даследаванні вылічальных сістэм, заснаваных на абмежаваннях. Ідэя абмежаванні праграмавання для вырашэння праблемы, заявіўшы, абмежаванні (умовы, уласцівасці), якія павінны быць задаволеныя рашэннем.

Праца ў гэтай вобласці можна прасачыць назад да даследаванняў у вобласці штучнага інтэлекту і камп'ютэрнай графікі ў шасцідзесятых і сямідзесятых гадоў. Толькі ў апошняе дзесяцігоддзе, аднак, паўстала ўсведамленне таго, што гэтыя ідэі служаць асновай для магутнага падыходу да праграмавання, мадэлявання і вырашэння праблем і, што розныя намаганні, каб выкарыстоўваць гэтыя ідэі могуць быць аб'яднаны ў агульную канцэптуальную і практычную аснову, праграмаванне ў абмежаваннях.

У цяперашні час можна бачыць дзве галіны Праграмаванне даследаванні абмежаванні, якія выцякаюць з розных баз і, такім чынам, выкарыстоўваць розныя падыходы да рашэння цяжкасцяў.

Задавальнення абмежаванняў
Задавальнення абмежаванняў паўсталі з даследаванняў у вобласці штучнага інтэлекту (комбинаторных задач, пошук) і камп'ютэрнай графікі (SketchPad сістэмы, выказаўшы геаметрычнай узгодненасці ў выпадку аналізу сцэны).

Задавальненне абмежаванняў задачы (CSP) з'яўляецца праблемай, дзе даецца:

• канчатковае мноства зменных,
• функцыя, якая адлюстроўвае кожную зменную ў канчатковай вобласці,
• канчатковае мноства абмежаванняў.

Кожнае абмежаванне абмяжоўвае спалучэнне значэнняў, што набор зменных можа прымаць адначасова. Рашэнне CSP з'яўляецца прызначэнне кожнай зменнай значэнне з сваёй вобласці, якая адпавядае ўсім абмежаванням. Задача складаецца ў тым, каб знайсці адно рашэнне або ўсе рашэнні.

Такім чынам, CSP з'яўляецца комбинаторная задача, якая можа быць вырашана шляхам пошуку. Там існуе трывіяльны алгарытм, які вырашае такія праблемы або лічыць, што няма рашэння. Гэты алгарытм генеруе ўсе магчымыя камбінацыі значэнняў, а затым яна правярае, ці з'яўляецца гэтая камбінацыя значэнняў задавальняе ўсім абмежаванням або няма (і, такім чынам, гэты алгарытм называецца стварэння і тэсціравання). Ясна, што гэты алгарытм займае шмат часу, каб працаваць так даследаванні ў галіне задавальнення абмежаванняў засяродзіцца на пошуку алгарытму рашэння праблемы больш эфектыўна, па меншай меры для дадзенага падмноства праблем.

Абмежаванне рашэння
Абмежаванне Рашэнне адрозніваецца ад задавальнення абмежаванняў пры выкарыстанні велічынь з бясконцай вобласці. Акрамя таго, асобныя абмежаванні з'яўляюцца больш складанымі, напрыклад, нелінейныя роўнасці. Такім чынам, абмежаванне алгарытмаў рашэння выкарыстоўвае алгебраічных і лікавыя метады замест камбінацый і пошук. Аднак, існуе падыход, які discretizes бясконцай вобласці ў канчатковае лік кампанент, а затым прымяняе метады задавальнення абмежаванняў.

Вы сказалі практычнага прымянення?
Гэты падраздзел прысвечаны тых, хто хоча чытачоў, якія хочуць, каб убачыць некаторыя прыклады практычнага прымянення тэхналогіі абмежаванні па-першае, перш чым акунуцца ў тэму.

Некаторыя карпарацыі, якія выкарыстоўваюць перавагі тэхналогіі абмежаванні: British Airways, SAS, Swissair, французскі чыгуначнага ўлады SNCF, Ганконг міжнародны тэрміналы, Michelin, Dassault і г.д.

• галаваломкі (на самай справе не практычнага прымянення, але яны весела)
  • N-каралевы
  • Zebra (пяць дома галаваломкі)
  • крыжаванка
  • cryptoarithmetics (SEND + больш = грошы)
  • натхняльнік
• размалёўкі графа
• аналізу і сінтэзу аналагавых схем
• Аналіз гандлёвых варыянт
• раскрою
• Секвенирования ДНК
• планаванне
• хімічных гіпатэтычных разваг
• Размяшчэнне склада
• лячэнне планавання лесу
• Аэрапорт лічыльнік размеркавання (Cathay Pacific Airways Ltd)
• Экіпаж рэестраў задачы (італьянская чыгуначная кампанія)
• а Планаванне дзейнасці (Сага нафты як)