Parametrik qidirish - Parametric search

Loyihalash va tahlil qilishda algoritmlar uchun kombinatorial optimallashtirish, parametrli qidirish tomonidan ixtiro qilingan texnikadir Nimrod Megiddo (1983 ) o'zgartirish uchun qaror algoritmi (ushbu optimallashtirish muammosi berilgan chegaradan yaxshiroq sifatli echimga egami?) ga optimallashtirish algoritmi (eng yaxshi echimni toping). U optimallash muammolarini hal qilish uchun tez-tez ishlatiladi hisoblash geometriyasi.

Texnik

Parametrik qidirishning asosiy g'oyasi - bu simulyatsiya sinov algoritmi bu raqamli parametrni kiritadi ${ displaystyle X}$ , go'yo u (noma'lum) optimal echim qiymati bilan ishlayotgandek ${ displaystyle X ^ {*}}$ uning kiritilishi sifatida. Ushbu test algoritmi o'zini tutishi kerak uzluksiz qachon ${ displaystyle X = X ^ {*}}$ va uning parametrlari bo'yicha ishlash ${ displaystyle X}$ faqat ning oddiy taqqoslashlari bilan ${ displaystyle X}$ boshqa hisoblangan qiymatlar bilan yoki past daraja belgisini sinab ko'rish orqali polinom funktsiyalari ning ${ displaystyle X}$ . Algoritmni simulyatsiya qilish uchun ushbu taqqoslash yoki testlarning har birini simulyatsiya qilish kerak, garchi ${ displaystyle X}$ simulyatsiya qilingan algoritm noma'lum.Har bir taqqoslashni simulyatsiya qilish uchun parametrli qidirish ikkinchi algoritmni qo'llaydi, a qaror algoritmi, bu kirish sifatida boshqa raqamli parametrni oladi ${ displaystyle Y}$ , va bu aniqlanadi ${ displaystyle Y}$ yuqorida, pastda yoki optimal echim qiymatiga teng ${ displaystyle X ^ {*}}$ .

Qaror algoritmining o'zi uzluksiz ravishda o'zini tutishi sababli ${ displaystyle X ^ {*}}$ , xuddi shu algoritm sinov algoritmi sifatida ham ishlatilishi mumkin. Biroq, ko'plab dasturlarda boshqa sinov algoritmlari qo'llaniladi (ko'pincha, taqqoslashni saralash algoritmlari). Parametrik qidirish texnikasining rivojlangan versiyalarida a parallel algoritm qaror algoritmi asoslarini sonini sezilarli darajada kamaytirish uchun test algoritmi sifatida va taqlid qilish kerak bo'lgan taqqoslashlarni guruhlarga bo'ling.

Ketma-ket test algoritmi

Parametrik qidirish texnikasining eng asosiy shaklida test algoritmi ham, qaror qabul qilish algoritmi ham ketma-ket (parallel bo'lmagan) algoritmlar, ehtimol bir-birlari bilan bir xil algoritmdir. Texnika test algoritmini bosqichma-bosqich simulyatsiya qiladi, chunki uning parametri sifatida (noma'lum) optimal echim qiymati berilganida ishlaydi ${ displaystyle X}$ . Har doim simulyatsiya sinov algoritmi uning parametrini taqqoslaydigan bosqichga yetganda ${ displaystyle X}$ boshqa raqamga ${ displaystyle Y}$ , bu qadamni raqamli taqqoslash orqali amalga oshira olmaydi, chunki u nimani bilmaydi ${ displaystyle X}$ bu. Buning o'rniga u qaror algoritmini parametr bilan chaqiradi ${ displaystyle Y}$ , va taqqoslash natijasini aniqlash uchun qaror algoritmi natijasidan foydalanadi. Shunday qilib, simulyatsiya vaqti sinov va qaror algoritmlari uchun vaqtlarning ko'payishiga tenglashadi. Sinov algoritmi optimal echim qiymatida uzluksiz harakat qiladi deb taxmin qilinganligi sababli, parametr qiymatlaridan biri bo'lmasa, uni aniq taqlid qilish mumkin emas ${ displaystyle Y}$ qaror qabul qilish algoritmiga o'tkazilishi, aslida optimal echim qiymatiga teng. Agar bu sodir bo'lsa, qaror algoritmi tenglikni aniqlay oladi va echimning eng maqbul qiymatini keyinchalik chiqishi uchun tejaydi, agar test algoritmi polinom belgisini bilishi kerak bo'lsa ${ displaystyle X}$ , buni yana o'tish orqali simulyatsiya qilish mumkin polinomning ildizlari echimning noma'lum qiymati ushbu ildizlardan biri ekanligini yoki yo'q bo'lsa, qaysi ikkita ildiz o'rtasida joylashganligini aniqlash uchun qaror algoritmiga.

Ikkalasi tomonidan ko'rib chiqilgan misol Megiddo (1983) va van Oostrum va Veltkamp (2002) toq sonli zarrachalar tizimiga taalluqli bo'lib, ularning barchasi bir chiziq bo'ylab har xil doimiy tezlikda o'ngga qarab harakatlanadi. Zarrachalarning medianasi ham to'g'ri harakatga ega bo'ladi, lekin doimiy tezlikka ega emas, balki qismli chiziqli, chunki har xil zarrachalar har xil vaqtda medianaga aylanadi. Dastlab zarralar va ularning medianasi chap tomonda joylashgan kelib chiqishi chiziqning natijasi, va oxir-oqibat ular va ularning medianlari kelib chiqishi o'ng tomonida bo'ladi. Muammo vaqtni hisoblashda ${ displaystyle t_ {0}}$ bunda medianing kelib chiqishi aniq yotadi.A chiziqli vaqt qaror algoritmini aniqlash oson: istalgan vaqt uchun ${ displaystyle t}$ , har bir zarrachaning vaqtdagi o'rnini hisoblash mumkin ${ displaystyle t}$ va kelib chiqishning har ikki tomonidagi zarralar sonini hisoblang. Agar chap tomonda o'ngga qaraganda ko'proq zarralar bo'lsa, unda ${ displaystyle t$ , va agar chap tomonga qaraganda o'ngda ko'proq zarralar bo'lsa, unda ${ displaystyle t> t_ {0}}$ . Ushbu qaror algoritmining har bir bosqichi kirish parametrini taqqoslaydi ${ displaystyle t}$ zarralardan biri kelib chiqishini kesib o'tgan vaqtgacha.

Ushbu qaror algoritmidan test algoritmi va parametrli qidiruvning qaror algoritmi sifatida foydalanish maqbul vaqtni topish algoritmiga olib keladi ${ displaystyle t_ {0}}$ kvadratik umumiy vaqt ichida. Parametr uchun qaror algoritmini taqlid qilish ${ displaystyle t_ {0}}$ , simulyatsiya har bir zarracha uchun uning kesishish vaqti oldin yoki keyin ekanligini aniqlashi kerak ${ displaystyle t_ {0}}$ va shuning uchun vaqt kelib chiqishi chap yoki o'ng tomonda bo'ladimi ${ displaystyle t_ {0}}$ . Bitta zarracha uchun bu savolga javob berish - zarrachaning o'tish vaqtini noma'lum optimal kesishish vaqti bilan taqqoslash ${ displaystyle t_ {0}}$ - Parametr bilan zarrachani kesib o'tish vaqti bilan bir xil qaror algoritmini ishga tushirish orqali amalga oshirish mumkin, shuning uchun simulyatsiya zarralarni kesib o'tish vaqtining har biri bo'yicha qaror algoritmini bajarishni tugatadi, ulardan biri eng maqbul o'tish vaqti bo'lishi kerak. qaror algoritmi bir marta chiziqli vaqtni oladi, shuning uchun uni har bir o'tish vaqtida alohida bajarish kvadratik vaqtni oladi.

Parallel sinov algoritmi

Sifatida Megiddo (1983) allaqachon kuzatilgan, simulyatsiya qilingan sinov algoritmini samarali bilan almashtirish orqali parametrli qidirish texnikasini sezilarli darajada tezlashtirish mumkin parallel algoritm, masalan parallel tasodifiy kirish mashinasi (PRAM) parallel hisoblash modeli, bu erda protsessorlar to'plami a da sinxronlikda ishlaydi umumiy xotira, barchasi turli xil xotira manzillarida bir xil operatsiyalar ketma-ketligini bajaradi. Agar test algoritmi PRAM algoritmidan foydalanilsa ${ displaystyle P}$ protsessorlar va vaqt talab etadi ${ displaystyle T}$ (anavi, ${ displaystyle T}$ har bir protsessor bitta operatsiyani bajaradigan qadamlar), so'ngra har bir qadam eng ko'p natijalarni aniqlash uchun qaror algoritmi yordamida taqlid qilinishi mumkin. ${ displaystyle P}$ raqamli taqqoslashlar. Baholashi kerak bo'lgan taqqoslashlar to'plamidan o'rtacha yoki o'rtacha qiymatni topib, ushbu yagona qiymatni qaror algoritmiga o'tkazib, qarorning bitta chaqirig'i bilan taqqoslashlarning yarmini yoki deyarli yarmini yo'q qilish mumkin. algoritm. Simulyatsiya talab qiladigan taqqoslashlar to'plamini shu tarzda bir necha marta ikki baravar qisqartirish orqali hech kim qolmaguncha natijalarni taqlid qilish mumkin. ${ displaystyle P}$ faqat raqamli taqqoslashlar ${ displaystyle O ( log P)}$ qaror algoritmiga chaqiradi. Shunday qilib, bu holda parametrik qidirish uchun umumiy vaqt bo'ladi ${ displaystyle O (PT)}$ (simulyatsiyaning o'zi uchun) ortiqcha vaqt ${ displaystyle O (T log P)}$ qaror algoritmiga chaqiradi (uchun ${ displaystyle T}$ taqqoslash partiyalari, olish ${ displaystyle O ( log P)}$ har bir partiyaga qo'ng'iroqlar). Ko'pincha, shu tarzda echilishi mumkin bo'lgan muammo uchun PRAM algoritmining vaqtni qayta ishlash mahsuloti ketma-ket qaror algoritmi uchun vaqt bilan taqqoslanadi va parallel vaqt polilogaritmik, faqat polylogarithmic factor tomonidan qaror algoritmidan sekinroq bo'lgan parametrik qidirish uchun umumiy vaqtga olib keladi.

Medianing kesishish vaqtini topish masalasi misolida ${ displaystyle n}$ harakatlanuvchi zarralar, ketma-ket sinov algoritmi parallel bilan almashtirilishi mumkin tartiblash algoritm parametri berilgan vaqtda zarrachalarning pozitsiyalarini saralaydigan, so'ngra median zarrachani aniqlash va joylashish belgisini topish uchun tartiblangan tartibdan foydalanadigan algoritm.Bu algoritm uchun eng yaxshi tanlov (nazariy tahliliga ko'ra, agar amalda emas) bu tarmoqni saralash ning Ajtai, Komlos va Szemeredi (1983 ). Bu raqam PRAM algoritmi sifatida talqin qilinishi mumkin ${ displaystyle P}$ protsessorlar kirish uzunligiga mutanosib ${ displaystyle n}$ , va parallel qadamlar soni logaritmik bo'ladi. Shunday qilib, ushbu algoritmni ketma-ket simulyatsiya qilish vaqt talab etadi ${ displaystyle O (n log n)}$ bilan birga simulyatsiya uchun ${ displaystyle O ( log n)}$ taqqoslash partiyalari, ularning har biri bilan ishlash mumkin ${ displaystyle O ( log n)}$ chiziqli vaqtdagi qaror algoritmiga qo'ng'iroq qiladi. Ushbu vaqt chegaralarini birlashtirish, beradi ${ displaystyle O (n log ^ {2} n)}$ parametrik qidirish uchun umumiy vaqt. Bu muammo uchun eng maqbul vaqt emas - xuddi shu muammoni medianing kesishish vaqti zarrachalarning kesishish vaqtining medianiga tengligini kuzatish orqali tezroq hal qilish mumkin - ammo xuddi shu uslub boshqa murakkab optimallashtirishda ham qo'llanilishi mumkin. muammolar va ko'p hollarda ushbu muammolar uchun eng tez ma'lum bo'lgan kuchli polinom algoritmini beradi.

AKS saralash tarmog'ini tahlil qilishda katta doimiy omillar kelib chiqqanligi sababli, ushbu algoritmni sinov algoritmi sifatida ishlatib parametrli qidirish amaliy emas. Buning o'rniga, van Oostrum va Veltkamp (2002) ning parallel shaklidan foydalanishni taklif eting tezkor (kirishni bir necha marta ikkita kichik guruhga ajratib, so'ngra har bir kichik to'plamni rekursiv ravishda saralash algoritmi). Ushbu algoritmda bo'lim bosqichi katta darajada parallel (har bir kirish elementi tanlangan pivot elementi bilan taqqoslanishi kerak) va ikkita rekursiv chaqiruv bir-biriga parallel ravishda amalga oshirilishi mumkin. Olingan parametrli algoritm .da sekinroq eng yomon holat AKS saralash tarmog'iga asoslangan algoritmdan ko'ra. Biroq van Oostrum va Veltkamp ilgari qaror qilingan algoritmlarning natijalari saqlanib qolinsa (faqat shu natijalar bilan hal qilinmagan taqqoslashlar qaror algoritmiga qo'shimcha qo'ng'iroqlarni keltirib chiqaradi) va taqlid qilingan test algoritmi tomonidan sinov qilingan taqqoslash qiymatlari etarlicha teng taqsimlanadi, keyin algoritm o'sib borishi bilan har bir qadamda hosil bo'lgan echilmagan taqqoslashlar soni kichik bo'ladi. Ushbu evristik tahlilga asoslanib va algoritmni amalga oshirish bilan o'tkazilgan eksperimental natijalarga ko'ra, ular tezkor kontsertga asoslangan parametrli qidirish algoritmi eng yomon tahlillardan ko'ra amaliyroq bo'lishini ta'kidlaydilar.

Sinxronlashtirilmagan tartiblash

Koul (1987) test algoritmi taqqoslash tartiblash algoritmi bo'lgan holatlar uchun (masalan, masalan) parametrli qidirish texnikasini yanada optimallashtirdi. AKS saralash tarmog'i va uning o'rnida ishlatilishi mumkin bo'lgan boshqa ba'zi bir saralash algoritmlari uchun Koul simulyatsiya qilingan protsessorlarni bir-biri bilan sinxronlashtirishni davom ettirish zarur emasligini kuzatadi: buning o'rniga ulardan ba'zilari saralash algoritmi orqali uzoqroq yurishga imkon berishi mumkin. boshqalar esa taqqoslash natijalari aniqlanishini kutishadi. Ushbu printsipga asoslanib, Koul saralash algoritmini simulyatsiyasini o'zgartiradi, shunda hammasi hal qilinmagan taqlid qilingan taqqoslashlar to'plamini saqlab qoladi, bu hammasi sinov algoritmining bir xil parallel vaqt qadamidan kelib chiqishi mumkin emas. Parametrik qidiruvning sinxronlashtirilgan parallel versiyasida bo'lgani kabi, o'rtacha taqqoslash qiymatini topish va ushbu qiymat bo'yicha qaror algoritmini chaqirish orqali ushbu taqqoslashlarning yarmini hal qilish mumkin. Keyinchalik, hal qilinmagan taqqoslashlar to'plami bo'sh bo'lgunga qadar ushbu yarmini qisqartirish protsedurasini takrorlash o'rniga, Cole echilgan taqqoslashlarni kutib turgan protsessorlarga, taqqoslash kerak bo'lgan boshqa taqqoslashgacha erishishga imkon beradi. test algoritmi saralanadigan parametrli qidiruv algoritmi, qaror algoritmiga qo'ng'iroqlarning faqat logaritmik soni yordamida bajarilishi mumkin. ${ displaystyle O ( log ^ {2} n)}$ Megiddoning parametrli qidirishning asl nusxasi tomonidan qilingan qo'ng'iroqlar. AKS saralash tarmog'idan foydalanish o'rniga, ushbu texnikani parallel ravishda birlashtirish ham mumkin birlashtirish algoritmi Koul (1988) Natijada kichikroq doimiy omillarga ega bo'lgan vaqt chegaralari paydo bo'ladi, ammo bu hali amaliy bo'lishi uchun etarli emas. Chegaralangan taqsimlangan hisoblash tarmog'ida hisoblash mumkin bo'lgan har qanday muammo uchun shunga o'xshash tezlikni olish mumkin daraja (AKS saralash tarmog'ida bo'lgani kabi) yoki Cole texnikasi bilan yoki bir nechta hisoblash yo'llarini simulyatsiya qilishning tegishli texnikasi bilan (Fernández-Baca 2001 yil ).

Goodrich va Pszona (2013) Koulning nazariy takomillashtirishini amaliy tezlashtirish bilan birlashtirish van Oostrum va Veltkamp (2002). Van Oostrum va Veltkamp singari parallel quicksort o'rniga, ular tomonidan ishlab chiqilgan quicksort versiyasi - boxsort Reyshuk (1985) unda bo'linish bosqichi kirishni tasodifiy ravishda ajratadi ${ displaystyle O ({ sqrt {n}})}$ faqat ikkita kichik muammo o'rniga kichikroq kichik muammolar. Koulning texnikasida bo'lgani kabi, ular ham sinxronlashtirilgan parametrli qidiruvdan foydalanadilar, bunda simulyatsiya qilingan parallel saralash algoritmining bajarilishining har bir alohida yo'nalishi boshqa taqqoslash natijasini aniqlash kerak bo'lgunga qadar davom etishiga ruxsat beriladi va bu erda hal qilinmagan taqqoslashlar soni ikkiga bo'linadi. o'rtacha taqqoslash qiymatini topish va shu qiymat bilan qaror algoritmini chaqirish orqali. Ular ko'rsatganidek, natijada olingan randomizatsiyalangan parametrik qidiruv algoritmi Coulning nazariy tahliliga mos keladigan katta ehtimollik bilan qaror qabul qilish algoritmiga faqat logaritmik sonli qo'ng'iroqlarni amalga oshiradi. Ushbu maqolaning kengaytirilgan versiyasi algoritmni amalga oshirish natijalari bo'yicha eksperimental natijalarni o'z ichiga oladi, bu esa ushbu usulning bir nechta tabiiy geometrik optimallashtirish muammolari bo'yicha ishlashning eng yaxshi sinxronlashtirilgan parametrik qidiruv dasturiga o'xshashligini ko'rsatadi (quicksort-ga asoslangan usul van Oostrum va Veltkamp): ba'zi muammolar bo'yicha biroz tezroq, ba'zilari esa biroz sekinroq. Biroq, qaror algoritmiga qo'ng'iroqlar soni sezilarli darajada kam, shuning uchun bu usul qaror algoritmi sekinroq bo'lgan joyda parametrli qidiruv dasturlarida katta foyda keltiradi.

Nuqtani kesib o'tishning o'rtacha vaqtini topish masalasida Coul algoritmi ham, Goodrich va Pszona algoritmi ham ish vaqtini oladi. ${ displaystyle O (n log n)}$ . Goodrich va Pszona misolida algoritm randomizatsiyalangan bo'lib, bu vaqtni katta ehtimollik bilan oladi.

Ikkilik qidiruv bilan taqqoslash

The ikkiga bo'linish usuli (ikkilik qidirish) qarorni optimallashtirishga aylantirish uchun ham ishlatilishi mumkin. Ushbu usulda an oraliq Qaror algoritmini uning o'rtacha qiymati bo'yicha chaqirish va qo'ng'iroq natijasiga qarab, medianing yuqorisida yoki pastida faqat yarim intervalni ushlab turish orqali intervalni bir necha bor qisqartiradi. Garchi bu usul faqat optimal echim qiymatiga raqamli yaqinlashuvni topishi mumkin bo'lsa-da, qaror algoritmini ushbu yaqinlashuv uchun aniqlik bitlari soniga mutanosib bo'lgan bir qator chaqiriqlarda amalga oshiradi. zaif polinom algoritmlar.

Buning o'rniga, qo'llanilganda, parametrik qidirish juda ko'p polinomli algoritmlarni topadi, ularning ishlash vaqti faqat kirish kattaligining funktsiyasi va raqamli aniqlikka bog'liq emas. Biroq, parametrik qidirish vaqt murakkabligining oshishiga olib keladi (qaror algoritmi bilan taqqoslaganda), logaritmikdan kattaroq bo'lishi mumkin. Parametrik qidirishga asoslangan algoritmlar kuchsiz polinom emas, kuchli bo'lgani uchun nazariy nuqtai nazardan qoniqarli. Amalda, ikkilik qidiruv tez va tez-tez amalga oshirilishi ancha sodda, shuning uchun algoritm muhandisligi parametrik qidiruvni amaliy qilish uchun harakatlar zarur. Shunga qaramay, van Oostrum va Veltkamp (2002) "oddiy ikkilik-qidiruv yondashuvi ko'pincha parametrik qidirishni amaliy almashtirish sifatida ilgari surilgan bo'lsa-da, u bizning [parametrli qidiruv] algoritmimizdan ustunroq" deb ular amalga oshirgan tajribaviy taqqoslashlarda yozing.

Ilovalar

The Theil-Sen taxminchi ga solishtirganda oddiy chiziqli regressiya

Parametrik qidirish optimallashtirish muammolari uchun samarali algoritmlarni ishlab chiqishda qo'llanilgan, xususan hisoblash geometriyasi (Agarval, Sharir va Toledo 1994 yil Ular quyidagilarni o'z ichiga oladi:

A markaziy nuqta a-da o'rnatilgan nuqta Evklid fazosi har qanday nuqta shunday yarim bo'sh joy markaziy nuqtani o'z ichiga olgan kirish nuqtalarining doimiy qismini ham o'z ichiga oladi. Uchun ${ displaystyle d}$ - o'lchovli bo'shliqlar, erishish mumkin bo'lgan optimal fraktsiya har doim kamida bo'ladi ${ displaystyle 1 / (d + 1)}$ . Ikki o'lchovli markaziy nuqtalarni qurish uchun parametr-qidiruvga asoslangan algoritmlar keyinchalik takomillashtirildi chiziqli vaqt boshqa algoritmik usullardan foydalanish. Biroq, bu takomillashtirish yuqori o'lchamlarga taalluqli emas. Uch o'lchovda parametrlarni qidirish markaz nuqtalarini o'z vaqtida topish uchun ishlatilishi mumkin ${ displaystyle O (n ^ {2} log ^ {4} n)}$ (Koul 1987 yil ).
Parametrik qidiruv an uchun asos sifatida ishlatilishi mumkin ${ displaystyle O (n log n)}$ uchun vaqt algoritmi Theil-Sen taxminchi, usul ishonchli statistika chiziqni sezgir bo'lmagan nuqtalar to'plamiga moslashtirish uchun chetga chiquvchilar dan oddiy chiziqli regressiya (Koul va boshq. 1989 yil ).
Yilda kompyuter grafikasi, nurli tortishish muammo (ma'lum bir ko'rish chizig'i yoki yorug'lik nurlari bilan kesishgan sahnadagi birinchi ob'ektni aniqlash) oddiyroq muammo uchun parametrli qidiruvni ma'lumotlar tuzilishi bilan birlashtirib, to'siqlarning biron bir to'plami berilganini to'sib qo'yadimi-yo'qligini sinab ko'rish orqali hal qilinishi mumkin. ray (Agarwal & Matoušek 1993 yil ).
The eng katta tayoq muammosi butunlay berilgan ichida joylashgan eng uzun chiziq segmentini topishni o'z ichiga oladi ko'pburchak. Buni o'z vaqtida hal qilish mumkin ${ displaystyle O (n ^ {8/5 + epsilon})}$ , uchun ${ displaystyle n}$ - ko'p qirrali va har qanday ${ displaystyle epsilon> 0}$ , parametrik qidiruvga asoslangan algoritmdan foydalanib (Agarval, Sharir va Toledo 1994 yil ).
The halqa berilgan nuqta to'plamini o'z ichiga olgan va eng kichik kenglikka ega bo'lgan (ichki va tashqi radiuslar orasidagi farq) o'lchov sifatida ishlatilishi mumkin. yumaloqlik nuqta to'plami. Shunga qaramay, bu muammoni o'z vaqtida hal qilish mumkin ${ displaystyle O (n ^ {8/5 + epsilon})}$ , uchun ${ displaystyle n}$ - ko'p qirrali va har qanday ${ displaystyle epsilon> 0}$ , parametrik qidiruvga asoslangan algoritmdan foydalanib (Agarval, Sharir va Toledo 1994 yil ).
The Hausdorff masofasi o'rtasida tarjima qiladi masofani minimallashtirish uchun tarjima qilingan ikkita ko'pburchakning vaqtini parametrik qidirish yordamida topish mumkin ${ displaystyle O ((mn) ^ {2} log ^ {3} mn)}$ , qayerda ${ displaystyle m}$ va ${ displaystyle n}$ ko'pburchaklar tomonlarining sonlari (Agarval, Sharir va Toledo 1994 yil ).
The Frechet masofasi ikkitasi o'rtasida ko'pburchak zanjirlar parametrli qidiruv yordamida o'z vaqtida hisoblash mumkin ${ displaystyle O (mn log mn)}$ , qayerda ${ displaystyle m}$ va ${ displaystyle n}$ egri chiziqlar soni (Alt va Godau 1995 yil ).
Uchun ${ displaystyle n}$ Evklid tekisligidagi, doimiy tezlikda harakatlanadigan nuqtalar, nuqtalar eng kichikini olish vaqtidir diametri (va o'sha paytdagi diametrni) Koulning texnikasini vaqt bo'yicha o'zgarishi yordamida topish mumkin ${ displaystyle O (n log ^ {2} n)}$ . Parametrli qidiruv, shuningdek, harakatlanuvchi nuqtalar to'plamining ba'zi bir o'lchovlari minimal qiymatini olish vaqtini topishda boshqa shunga o'xshash muammolar uchun ham, o'lchamlari, shu jumladan o'lchovlar uchun ham ishlatilishi mumkin. minimal yopiq to'p yoki ning vazni maksimal daraxt daraxti (Fernández-Baca 2001 yil ).

Adabiyotlar

Agarval, Pankaj K.; Matushek, Jiři (1993), "Rayni tortishish va parametrli qidirish", Hisoblash bo'yicha SIAM jurnali, 22 (4): 794–806, CiteSeerX 10.1.1.298.6047, doi:10.1137/0222051, JANOB 1227762
Agarval, Pankaj K.; Sharir, Micha; Toledo, Sivan (1994), "Geometrik optimallashtirishda parametrli qidiruvning qo'llanilishi", Algoritmlar jurnali, 17 (3): 292–318, doi:10.1006 / jagm.1994.1038, JANOB 1300253, S2CID 380722.
Ajtai, M.; Komlos, J.; Szemeredi, E. (1983), "An $O (n jurnal n)$ tarmoqni saralash ", Hisoblash nazariyasi bo'yicha 15-ACM simpoziumi materiallari (STOC '83), 1-9 betlar, doi:10.1145/800061.808726, ISBN 0-89791-099-0, S2CID 15311122.
Alt, Helmut; Godau, Maykl (1995), "Ikkita ko'pburchak egri chiziqlar orasidagi masofani hisoblash" (PDF), Xalqaro hisoblash geometriyasi va ilovalari jurnali, 5 (1–2): 75–91, doi:10.1142 / S0218195995000064, JANOB 1331177.
Koul, Richard (1987), "Tezroq saralash algoritmlarini olish uchun saralash tarmoqlarini sekinlashtirish", ACM jurnali, 34 (1): 200–208, doi:10.1145/7531.7537, JANOB 0882669, S2CID 2301419.
Koul, Richard (1988), "Parallel merge sort", Hisoblash bo'yicha SIAM jurnali, 17 (4): 770–785, doi:10.1137/0217049, JANOB 0953293, S2CID 2416667.
Koul, Richard; Salowe, Jeffri S.; Shtayger, V. L.; Szemeredi, Endre (1989), "Nishab tanlash uchun optimal vaqt algoritmi", Hisoblash bo'yicha SIAM jurnali, 18 (4): 792–810, doi:10.1137/0218055, JANOB 1004799.
Fernández-Baca, D. (2001), "Lineer bo'lmagan parametrik qidiruv to'g'risida", Algoritmika, 30 (1): 1–11, doi:10.1007 / s00453-001-0001-2, JANOB 1816864, S2CID 20320912.
Gudrix, Maykl T.; Pszona, Pavel (2013), "Koulning parametrik qidirish texnikasi amaliy bo'ldi" (PDF), Proc. Hisoblash geometriyasi bo'yicha 25-konferentsiya (CCCG 2013), arXiv:1306.3000, Bibcode:2013arXiv1306.3000G.
Megiddo, Nimrod (1983), "Ketma-ket algoritmlarni loyihalashda parallel hisoblash algoritmlarini qo'llash", ACM jurnali, 30 (4): 852–865, doi:10.1145/2157.322410, JANOB 0819134, S2CID 2212007.
Reischuk, Ryudiger (1985), "Saralash va tanlashning ehtimollik parallel algoritmlari", Hisoblash bo'yicha SIAM jurnali, 14 (2): 396–409, doi:10.1137/0214030, JANOB 0784745.
van Oostrum, René; Veltkamp, Remco C. (2002), "Parametrik izlash amaliy bo'ldi", Hisoblash geometriyasi bo'yicha o'n sakkizinchi yillik simpozium materiallari (SoCG '02), Nyu-York, NY, AQSh: ACM, 1-9 betlar, doi:10.1145/513400.513401, hdl:1874/18869, ISBN 1-58113-504-1, S2CID 1551019.