Chans algoritmi - Chans algorithm - Wikipedia

Chan algoritmi uchun 2 o'lchovli demo. Shunga qaramay, algoritm ballarni x-koordinatasi bilan emas, balki o'zboshimchalik bilan ajratishini unutmang.

Yilda hisoblash geometriyasi, Chan algoritmi,[1] nomi bilan nomlangan Timoti M. Chan, optimal hisoblanadi chiqishga sezgir algoritm hisoblash qavariq korpus to'plamning ning nuqtalar, 2 yoki 3 o'lchovli bo'shliqda. Algoritm oladi vaqt, qayerda chiqishning tepaliklari soni (qavariq korpus). Planar holatda algoritm an-ni birlashtiradi algoritm (Grem skaneri, masalan) bilan Jarvis yurishi (), optimalni olish uchun vaqt. Chan algoritmi e'tiborga loyiq, chunki u juda sodda Kirkpatrik - Zaydel algoritmi va u tabiiy ravishda 3 o'lchovli bo'shliqqa tarqaladi. Ushbu paradigma[2] mustaqil ravishda doktorlik dissertatsiyasida Frank Nilsen tomonidan ishlab chiqilgan. tezis.[3]

Algoritm

Umumiy nuqtai

Algoritmning bitta o'tish parametrini talab qiladi bu 0 va orasida (to'plamimiz punktlari soni) ). Ideal holda, lekin , chiqish qavariq korpusidagi tepalar soni boshida ma'lum emas. Ortib borayotgan qiymatlari bilan bir nechta o'tish amalga oshiriladi, keyin qachon tugaydi (parametr tanlash bo'yicha pastga qarang ).

Algoritm o'zboshimchalik bilan ballar to'plamini ajratishdan boshlanadi ichiga pastki to'plamlar ko'pi bilan har biri ochko; e'tibor bering .

Har bir kichik to'plam uchun , u konveks qobig'ini hisoblab chiqadi, , yordamida algoritm (masalan, Grem skaneri ), qaerda pastki qismdagi ballar soni. U erda bo'lgani kabi kichik guruhlari har bir ochko, bu bosqich davom etadi vaqt.

Ikkinchi bosqichda, Jarvisning yurishi oldindan hisoblangan (mini) qavariq korpuslardan foydalangan holda bajariladi, . Jarvisning yurish algoritmining har bir qadamida bizda bir nuqta bor qavariq korpusda (boshida, nuqta bo'lishi mumkin eng past y koordinatali, bu esa konveks tanasida bo'lishi kafolatlangan ) va nuqta topish kerak ning boshqa barcha nuqtalari chiziqning o'ng tomonida [tushuntirish kerak ], qaerda yozuv shunchaki keyingi nuqta degani, ya'ni , funktsiyasi sifatida aniqlanadi va . To'plamning qavariq tanasi , , ma'lum va ko'pi bilan o'z ichiga oladi hisoblash uchun imkon beradigan punktlar (soat yo'nalishi bo'yicha yoki soat yo'nalishi bo'yicha teskari tartibda berilgan) yilda vaqt o'tishi bilan ikkilik qidirish[Qanaqasiga? ]. Demak, hisoblash hamma uchun pastki to'plamlarni amalga oshirish mumkin vaqt. Keyin, biz aniqlay olamiz odatda Jarvisning yurishida ishlatiladigan usuldan foydalanadi, lekin faqat fikrlarni hisobga olgan holda butun to'plam o'rniga (ya'ni mini konveks korpusidagi nuqtalar) . Ushbu fikrlar uchun Jarvisning yurishining bitta takrorlanishi bu barcha kichik guruhlar uchun hisoblash bilan taqqoslaganda ahamiyatsiz. Jarvisning yurishi jarayon takrorlangandan so'ng yakunlanadi marta (chunki Jarvis marshining ishi bo'yicha, eng ko'pi bilan uning tashqi tsiklining takrorlanishi, qaerda ning qavariq tanasida joylashgan nuqta soni , biz konveks korpusni topdik), shuning uchun ikkinchi bosqich davom etadi ga teng bo'lgan vaqt vaqt, agar ga yaqin (tanlash uchun strategiya tavsifiga quyida qarang shunday bo'lsa).

Yuqorida tavsiflangan ikkita fazani ishga tushirish orqali ballar hisobga olinadi vaqt.

Parametrni tanlash

Agar uchun ixtiyoriy qiymat tanlansa , shunday bo'lishi mumkin . Bunday holda, keyin ikkinchi bosqichdagi qadamlar, biz to'xtatamiz Jarvisning yurishi chunki uni oxirigacha ishlatish juda ko'p vaqt talab qilishi kerak edi vaqt sarflangan va konveks qobig'i hisoblanmagan.

G'oyasi ortib boruvchi qiymatlar bilan algoritmning bir nechta o'tishini amalga oshirishdir ; har bir o'tish tugaydi (muvaffaqiyatli yoki muvaffaqiyatsiz) vaqt. Agar paslar orasida juda sekin ko'payadi, takrorlanish soni ko'p bo'lishi mumkin; boshqa tomondan, agar u juda tez ko'tarilsa, birinchi uchun algoritm muvaffaqiyatli tugatilganidan ancha kattaroq bo'lishi mumkin va murakkablikni keltirib chiqaradi .

Kvadratchalar strategiyasi

Mumkin bo'lgan strategiyalardan biri kvadrat ning qiymati har bir iteratsiyada maksimal qiymatgacha (singleton to'plamlaridagi bo'limga mos keladi).[4] Takrorlashda 2 qiymatidan boshlab , tanlangan. Shunday bo'lgan taqdirda, algoritm bir marta tugaganligini hisobga olsak, takrorlashlar amalga oshiriladi

asosda olingan logaritma bilan , va algoritmning umumiy ishlash vaqti

Uch o'lchovda

Ushbu konstruktsiyani 3 o'lchovli ish uchun umumlashtirish uchun Grem skanerlash o'rniga Preparata va Hong tomonidan 3 o'lchovli konveks korpusini hisoblash algoritmidan foydalanish kerak va Jarvisning yurishining 3 o'lchovli versiyasidan foydalanish kerak. Vaqtning murakkabligi saqlanib qoladi .[1]

Psevdokod

Quyidagi psevdokodda qavslar orasidagi va kursivdagi matn izohlar mavjud. Quyidagi psevdokodni to'liq tushunish uchun o'quvchiga allaqachon tanish bo'lishi tavsiya etiladi Grem skaneri va Jarvis yurishi qavariq korpusni hisoblash algoritmlari, , bir qator to'plamlar,.

Kiritish: O'rnatish bilan ochkolar.
Chiqish: O'rnatish bilan qavariq tanasi .
(Bir nuqtani tanlang unda bo'lish kafolatlangan : masalan, eng past koordinatali nuqta.)
(Ushbu operatsiyani bajarish kerak vaqt: masalan, biz shunchaki takrorlashimiz mumkin .)
( ushbu Chan algoritmining Jarvis marsh qismida ishlatiladi,
shuning uchun ikkinchi fikrni hisoblash uchun, , ning konveks korpusida .)
(Eslatma: bu emas bir nuqta .)
(Qo'shimcha ma'lumot uchun Chan algoritmining tegishli qismiga yaqin sharhlarni ko'ring.)
(Eslatma: , oxirgi konveks qobig'idagi ochkolar soni , bo'ladi emas ma'lum.)
(Bularning qiymatini aniqlash uchun zarur bo'lgan takrorlashlar , bu taxminiy hisoblanadi .)
( ning Channing qavariq korpusini topish algoritmi uchun talab qilinadi .)
(Aniqrog'i, biz xohlaymiz , juda ko'p keraksiz takrorlashni bajarmaslik uchun
va shuning uchun ushbu Chan algoritmining vaqt murakkabligi .)
(Yuqorida ushbu maqolada aytib o'tilganidek, biz ko'pi bilan strategiyadan foydalanamiz topish uchun takrorlash talab qilinadi .)
(Izoh: final ga teng bo'lmasligi mumkin , lekin u hech qachon undan kichik emas va undan katta .)
(Shunga qaramay, bu Channing algoritmi bir marta to'xtaydi eng tashqi tsiklning takrorlanishi amalga oshiriladi,
ya'ni, hatto , bajarilmaydi eng tashqi tsiklning takrorlanishi.)
(Qo'shimcha ma'lumot olish uchun quyidagi algoritmning Jarvis mart qismiga qarang, qaerda agar qaytarilsa .)
uchun qil
(Parametrni o'rnating joriy takrorlash uchun. Ushbu maqolada yuqorida aytib o'tilganidek, "kvadratchalar sxemasi" dan foydalanamiz.
Boshqa sxemalar ham mavjud: masalan, "ikki baravar oshirish sxemasi", qaerda , uchun .
Agar biz "ikkilamchi sxema" dan foydalansak, natijada ushbu Chan algoritmining vaqt murakkabligi .)
(Ning qavariq qobig'ining nuqtalarini saqlash uchun bo'sh ro'yxatni (yoki qatorni) boshlang , ular topilganidek.)
(O'zboshimchalik bilan bo'lingan ballar to'plami ichiga taxminan pastki qismlar har bir element.)
(Barchaning konveks qobig'ini hisoblang ochkolar to'plamlari, .)
(Bunga .. Vaqt ketadi vaqt.)
Agar , keyin vaqtning murakkabligi .)
uchun qil
(Ichki to'plamning konveks qobig'ini hisoblang , , oladi Graham skanerlash, yordamida oladi vaqt.)
( nuqtalar to'plamining qavariq tanasi .)
(Shu nuqtada, konveks qobiqlari navbati bilan ballar to'plamlari hisoblab chiqilgan.)
(Endi, a dan foydalaning o'zgartirilgan versiya ning Jarvis yurishi ning konveks korpusini hisoblash algoritmi .)
(Jarvis yurishi vaqt, qayerda bu kirish nuqtalarining soni va qavariq tanadagi nuqta soni.)
(Jarvis yurishi an chiqishga sezgir algoritm, uning ishlash muddati konveks qobig'ining o'lchamiga bog'liq, .)
(Amalda bu Jarvis marshining ijro etishini anglatadi uning tashqi tsiklining takrorlanishi.
Ushbu takrorlashlarning har birida u maksimal darajada bajariladi uning ichki tsiklining takrorlanishi.)
(Biz xohlaymiz , shuning uchun biz ko'proq narsani bajarishni xohlamaymiz quyidagi tashqi tsikldagi takrorlash.)
(Agar bizning oqimimiz bo'lsa dan kichikroq , ya'ni , qavariq tanasi topilmadi.)
(Jarvis marshining ushbu o'zgartirilgan versiyasida biz qabul qiladigan ichki tsikl ichida operatsiyani bajaramiz vaqt.
Shunday qilib, ushbu o'zgartirilgan versiyaning umumiy vaqt murakkabligi
Agar , keyin vaqtning murakkabligi .)
uchun qil
(Izoh: bu erda, qavariq tanadagi nuqta allaqachon ma'lum, ya'ni .)
(Ushbu ichki qismida uchun pastadir, konveks qobig'ida bo'lishi mumkin bo'lgan keyingi fikrlar , , hisoblab chiqilgan.)
(Ularning har biri mumkin bo'lgan keyingi fikrlar boshqacha :
anavi, ning konveks qobig'ida mumkin bo'lgan keyingi nuqta bu konveks qobig'ining bir qismi .)
(Eslatma: bog'liq : ya'ni har bir iteratsiya uchun , bizda ... bor konveks qobig'ida bo'lishi mumkin bo'lgan keyingi fikrlar .)
(Izoh: har bir takrorlashda , orasida faqat bitta nuqta ning konveks korpusiga qo'shiladi .)
uchun qil
( fikrni topadi shunday qilib burchak maksimal darajaga ko'tarilgan[nega? ],
qayerda - bu vektorlar orasidagi burchak va . Bunday ichida saqlanadi .)
(Burchaklarni to'g'ridan-to'g'ri hisoblash kerak emas: the orientatsiya testi foydalanish mumkin[Qanaqasiga? ].)
( amalga oshirilishi mumkin vaqt[Qanaqasiga? ].)
(Izoh: takrorlashda , va ma'lum va bu konveks qobig'idagi nuqta :
bu holda, bu nuqta eng past koordinatali.)
(Nuqtani tanlang bu burchakni maksimal darajada oshiradi [nega? ] qavariq korpusidagi navbatdagi nuqta bo'lish .)
(Jarvis marsh konveks tanasida keyingi tanlangan nuqta tugaganda, , boshlang'ich nuqta, .)
agar
(Qavariq tanasini qaytaring o'z ichiga oladi ball.)
(Izoh: albatta qaytishga hojat yo'q bu tengdir .)
qaytish
boshqa
(Agar keyin bo'lsa bir nuqtani takrorlash shunday topilmadi , keyin .)
(Biz uchun yuqori qiymat bilan qayta boshlashimiz kerak .)

Amalga oshirish

Channing maqolasida algoritmning amaliy ko'rsatkichlarini yaxshilashi mumkin bo'lgan bir nechta takliflar mavjud, masalan:

  • Pastki to'plamlarning konveks qobig'ini hisoblashda, konveks tanasida bo'lmagan nuqtalarni keyingi qatllarda ko'rib chiqilishidan olib tashlang.
  • Kattaroq nuqta to'plamlarining konveks qobig'ini noldan hisoblash o'rniga, ilgari hisoblangan konveks tanalarini birlashtirish orqali olish mumkin.
  • Yuqoridagi g'oya bilan algoritmning ustun qiymati oldindan qayta ishlashga, ya'ni guruhlarning konveks qobig'ini hisoblashga to'g'ri keladi. Ushbu xarajatlarni kamaytirish uchun biz avvalgi iteratsiyadan hisoblangan korpuslarni qayta ishlatishni va guruh kattalashgan sari ularni birlashtirishni ko'rib chiqamiz.

Kengaytmalar

Channing qog'ozida ba'zi bir boshqa muammolar mavjud bo'lib, ularning ma'lum algoritmlari uning texnikasi yordamida optimal chiqishga sezgir bo'lishi mumkin, masalan:

  • Pastki konvertni hisoblash to'plamning ning cheksiz chegaraning pastki chegarasi sifatida belgilangan chiziqli segmentlar trapezoid chorrahalar tomonidan hosil qilingan.
  • Xershberger[5] berdi tezlashtirilishi mumkin bo'lgan algoritm , bu erda h - konvertdagi qirralarning soni
  • Yuqori o'lchamdagi qavariq tanachalar uchun chiqishga sezgir algoritmlarni tuzish. Guruhlash nuqtalari va samarali ma'lumotlar tuzilmalaridan foydalangan holda, h polinom tartibida bo'lish sharti bilan murakkablikka erishish mumkin .

Shuningdek qarang

Adabiyotlar