Судалгааны ажил нь манай сургалтын хамгийн сонирхолтой хэсэг байж магадгүй юм. Их сургуульд байхдаа сонгосон чиглэлээрээ өөрийгөө сорих санаа. Жишээлбэл, програм хангамжийн инженерчлэл, машин сургалтын чиглэлээр суралцдаг оюутнууд ихэвчлэн компаниудад судалгаа хийхээр явдаг (гол төлөв JetBrains эсвэл Yandex, гэхдээ зөвхөн биш).
Энэ нийтлэлд би компьютерийн шинжлэх ухааны чиглэлээр өөрийн төслийн талаар ярих болно. Ажлынхаа нэг хэсэг болгон би хамгийн алдартай NP-хүнд асуудлуудын нэгийг шийдвэрлэх арга барилыг судалж, хэрэгжүүлсэн. оройг хамарсан асуудал.
Өнөө үед NP-хүнд асуудлуудад сонирхолтой арга барил маш хурдан хөгжиж байна - параметржүүлсэн алгоритмууд. Би таныг хурдасгах, параметржүүлсэн энгийн алгоритмуудыг хэлж, надад маш их тусалсан нэг хүчирхэг аргыг тайлбарлахыг хичээх болно. Би PACE Challenge тэмцээнд үр дүнгээ танилцуулсан: нээлттэй туршилтын үр дүнгээс харахад миний шийдэл 1-р байранд орсон бөгөөд эцсийн үр дүн XNUMX-р сарын XNUMX-нд тодорхой болно.
Миний тухай
Намайг Василий Алферов гэдэг, би одоо Санкт-Петербург хотын Үндэсний судалгааны их сургуулийн Эдийн засгийн дээд сургуульд гурав дахь жилээ төгсөж байна. Би Москвагийн 179-р сургуульд суралцаж, компьютерийн ухааны олимпиадад амжилттай оролцож байхдаа сургуулийнхаа алгоритмыг сонирхож эхэлсэн.
Параметржсэн алгоритмын хязгаарлагдмал тооны мэргэжилтнүүд бааранд ордог ...
Номоос авсан жишээ
Та жижиг хотод баарны хамгаалалтын ажилтан байна гэж төсөөлөөд үз дээ. Баасан гараг бүр хотын тал хувь нь танай бааранд амарч ирдэг бөгөөд энэ нь танд маш их бэрхшээл учруулдаг: хэрүүл маргаан гарахаас урьдчилан сэргийлэхийн тулд хэрүүлтэй үйлчлүүлэгчдийг баарнаас хөөх хэрэгтэй. Эцсийн эцэст та залхаж, урьдчилан сэргийлэх арга хэмжээ авахаар шийддэг.
Танай хот жижиг тул ямар хос үйлчлүүлэгчид хамтдаа бааранд орвол зодолдох магадлалтайг та сайн мэднэ. Танд жагсаалт байна уу n өнөө орой бааранд ирэх хүмүүс. Та хотын зарим хүмүүсийг бааранд оруулахгүй байхаар шийдэж, хэн нэгэнтэй зодолдохгүй. Үүний зэрэгцээ таны дарга нар ашиг алдахыг хүсэхгүй бөгөөд хэрэв та үүнээс илүүг зөвшөөрөхгүй бол сэтгэл дундуур байх болно. k хүмүүс.
Харамсалтай нь таны өмнө тулгарч буй асуудал бол БЦГ-ын хувьд хэцүү асуудал юм. Та түүнийг мэддэг байж магадгүй , эсвэл оройг хамарсан асуудал. Ийм асуудлуудын хувьд ерөнхий тохиолдолд хүлээн зөвшөөрөгдсөн хугацаанд ажиллах алгоритмууд байдаггүй. Нарийвчлан хэлэхэд, батлагдаагүй, нэлээд хүчтэй таамаглал ETH (Exponential Time Hypothesis) нь энэ асуудлыг цаг хугацаанд нь шийдвэрлэх боломжгүй гэж хэлдэг. , өөрөөр хэлбэл, та бүрэн хайлтаас илүү сайн зүйлийг бодож чадахгүй. Жишээлбэл, хэн нэгэн танай бааранд ирэх гэж байна гэж бодъё n = 1000 Хүн. Дараа нь бүрэн хайлт хийх болно ойролцоогоор байгаа сонголтууд - галзуу хэмжээ. Аз болоход танай удирдлага танд хязгаарлалт өгсөн k = 10, тиймээс давтах шаардлагатай хослолуудын тоо хамаагүй бага байна: арван элементийн дэд олонлогийн тоо нь . Энэ нь илүү сайн, гэхдээ хүчирхэг кластерт ч гэсэн нэг өдрийн дотор тооцогдохгүй.
Бааранд зочилсон хүмүүсийн хоорондын харилцаа хурцадсан энэ нөхцөлд хэрүүл маргаан гарах магадлалыг арилгахын тулд Боб, Даниел, Федор нарыг оруулахгүй байх хэрэгтэй. Ард нь хоёр л үлдэх шийдэл байхгүй.
Энэ нь бууж өгөх цаг болсон гэсэн үг үү? Бусад сонголтуудыг авч үзье. Жишээлбэл, та маш олон хүнтэй тулалдах магадлалтай хүмүүсийг л оруулж болохгүй. Хэн нэгэнтэй ядаж тэмцэж чадах юм бол k+1 өөр хүн байвал та түүнийг дотогш оруулах боломжгүй - эс тэгвээс та бүгдийг оруулахгүй байх ёстой k+1 түүний тулалдаж чадах хотын иргэд, энэ нь удирдлагыг бухимдуулах нь гарцаагүй.
Та энэ зарчмын дагуу чадах бүхнээ хаях болтугай. Дараа нь бусад бүх хүмүүс үүнээс илүүгүй тэмцэж чадна k хүмүүс. Тэднийг хаях k Хүн, та үүнээс өөр юу ч урьдчилан сэргийлж чадахгүй зөрчилдөөн. Энэ нь хэрэв илүү байгаа бол гэсэн үг юм Хэрэв хүн дор хаяж нэг зөрчилдөөнд оролцсон бол та бүгдийг нь урьдчилан сэргийлэх боломжгүй. Мэдээжийн хэрэг, та зөрчилдөөнгүй хүмүүсийг оруулах нь гарцаагүй тул та хоёр зуун хүнээс арав хүртэлх хэмжээтэй бүх дэд бүлгүүдийг давах хэрэгтэй. Ойролцоогоор байдаг , мөн энэ тооны үйлдлийг кластер дээр аль хэдийн ангилж болно.
Хэрэв та зөрчилдөөнгүй хүмүүсийг аюулгүйгээр авч чадвал зөвхөн нэг мөргөлдөөнд оролцсон хүмүүсийг яах вэ? Уг нь өрсөлдөгчийнхөө хаалгыг хааснаар тэднийг бас оруулж болно. Үнэхээр хэрэв Алис зөвхөн Бобтой зөрчилдөж байгаа бол бид Алисыг энэ хоёроос салгавал бид алдахгүй: Боб өөр зөрчилдөөнтэй байж магадгүй, гэхдээ Алисад тийм зүйл байхгүй. Тэгээд ч бид хоёрыг дотогш оруулахгүй байх нь утгагүй юм. Ийм үйлдлүүдийн дараа өөр зүйл үлдэхгүй шийдэгдээгүй хувь тавилантай зочид: бидэнд зөвхөн байна зөрчилдөөн, тус бүр хоёр оролцогчтой, тус бүр дор хаяж хоёр оролцогчтой. Тиймээс цэгцлэх л үлдлээ зөөврийн компьютер дээр хагас өдрийн турш хялбархан авч үзэх боломжтой сонголтууд.
Үнэн хэрэгтээ, энгийн үндэслэлээр та илүү сонирхолтой нөхцөл байдалд хүрч чадна. Бид бүх маргааныг шийдвэрлэх ёстой гэдгийг анхаарна уу, өөрөөр хэлбэл зөрчилдөж буй хос бүрээс дор хаяж нэг хүнийг оруулахгүй байх ёстой. Дараах алгоритмыг авч үзье: нэг оролцогчийг хасаад үлдсэн хэсгээс нь рекурсив байдлаар эхлүүлж, дараа нь нөгөөг нь хасаад мөн рекурсив байдлаар эхлүүлдэг аливаа зөрчилдөөнийг ав. Бид алхам тутамд хэн нэгнийг хаядаг тул ийм алгоритмын рекурсын мод нь гүний хоёртын мод юм. k, нийтдээ алгоритм нь ажилладаг хаана n оройн тоо, ба m - хавирганы тоо. Бидний жишээн дээр энэ нь зөвхөн зөөврийн компьютер дээр төдийгүй гар утсан дээр ч секундын дотор тооцоолж болох арван сая орчим юм.
Дээрх жишээ бол жишээ юм параметржүүлсэн алгоритм. Параметржсэн алгоритмууд нь цаг хугацаанд нь ажилладаг алгоритмууд юм f(k) поли(n)хаана p - олон гишүүнт, f нь дурын тооцоолж болох функц бөгөөд k - зарим параметр нь асуудлын хэмжээнээс хамаагүй бага байх магадлалтай.
Энэ алгоритмын өмнөх бүх үндэслэл нь жишээг өгдөг цөмжилт параметржүүлсэн алгоритм үүсгэх ерөнхий аргуудын нэг юм. Цөмжилт гэдэг нь асуудлын хэмжээг параметрийн функцээр хязгаарлагдмал утга болгон багасгах явдал юм. Үүний үр дүнд үүссэн асуудлыг ихэвчлэн цөм гэж нэрлэдэг. Тиймээс оройнуудын зэрэгтэй холбоотой энгийн үндэслэлээр бид хариултын хэмжээгээр параметржүүлсэн Vertex Cover бодлогын квадрат цөмийг олж авсан. Та энэ ажилд зориулж сонгож болох өөр тохиргоонууд байдаг (жишээ нь, Vertex Cover Above LP гэх мэт), гэхдээ энэ бол бидний хэлэлцэх тохиргоо юм.
Pace Challenge
Өрсөлдөөн (The Parameterized Algorithms and Computational Experiments Challenge) нь 2015 онд параметржүүлсэн алгоритмууд болон тооцооллын асуудлыг шийдвэрлэхэд практикт хэрэглэгдэж буй арга барилуудын хоорондын холбоог тогтоох зорилгоор төрсөн. Эхний гурван тэмцээн нь графикийн модны өргөнийг олоход зориулагдсан.), Штайнер модыг хайж байна () болон мөчлөгийг тасалдаг оройнуудын багцыг хайх (). Энэ жил таны хүч сорьж болох асуудлын нэг бол дээр дурдсан оройн бүрхэвчийн асуудал байв.
Тэмцээн жил бүр алдартай болж байна. Урьдчилсан мэдээлэлд итгэж байгаа бол энэ жил дан ганц оройг хамарсан асуудлыг шийдэх тэмцээнд 24 баг оролцсон. Тэмцээн хэдэн цаг, бүр долоо хоног биш, хэдэн сар үргэлжилдэг гэдгийг тэмдэглэх нь зүйтэй. Багууд уран зохиол судалж, өөрийн гэсэн анхны санаа гаргаж, түүнийгээ хэрэгжүүлэхийг хичээх боломжтой. Нэг ёсондоо энэ уралдаан бол судалгааны ажил. Хамгийн үр дүнтэй шийдлүүдийн санааг гаргаж, ялагчдыг шалгаруулж, хуралтай хамтатган зохион байгуулна. (Параметржүүлсэн ба нарийн тооцооллын олон улсын симпозиум) Европ дахь хамгийн том жилийн алгоритмын уулзалтын нэг хэсэг болгон . Тэмцээний талаарх дэлгэрэнгүй мэдээллийг эндээс авах боломжтой , өмнөх жилүүдийн үр дүн худлаа .
Шийдлийн диаграм
Оройг хамарсан асуудлыг шийдэхийн тулд параметржүүлсэн алгоритмуудыг ашиглахыг оролдсон. Эдгээр нь ихэвчлэн хоёр хэсгээс бүрддэг: хялбаршуулах дүрмүүд (энэ нь цөм болгоход хамгийн тохиромжтой) ба хуваах дүрэм. Хялбаршуулах дүрмүүд нь олон гишүүнт хугацаанд оролтыг урьдчилан боловсруулах явдал юм. Ийм дүрмийг хэрэгжүүлэх зорилго нь асуудлыг ижил төстэй жижиг асуудал болгон багасгах явдал юм. Хялбаршуулах дүрмүүд нь алгоритмын хамгийн үнэтэй хэсэг бөгөөд энэ хэсгийг ашиглах нь нийт ажиллах хугацааг бий болгодог. энгийн олон гишүүнт цагийн оронд. Манай тохиолдолд хуваах дүрмүүд нь орой бүрийн хувьд та үүнийг эсвэл түүний хөршийн аль нэгийг нь хариулт болгон авах шаардлагатай байдаг.
Ерөнхий схем нь: бид хялбаршуулах дүрмийг хэрэглэж, дараа нь зарим оройг сонгож, хоёр рекурсив дуудлага хийдэг: эхний үед бид үүнийг хариу үйлдэл болгон авдаг, нөгөөд нь бид түүний бүх хөршүүдийг авдаг. Үүнийг бид энэ оройн дагуу хуваах (салбарлах) гэж нэрлэдэг.
Дараагийн догол мөрөнд энэ схемд яг нэг нэмэлтийг оруулах болно.
Дүрмийг хуваах (brunching) санаанууд
Хагалах оройг хэрхэн сонгох талаар ярилцъя.
Гол санаа нь алгоритмын утгаараа маш их шуналтай: дээд зэргийн оройг авч, түүний дагуу хувацгаая. Яагаад илүү дээр юм шиг санагдаж байна вэ? Учир нь рекурсив дуудлагын хоёр дахь салбар дээр бид ийм байдлаар маш олон оройг арилгах болно. Та жижиг график үлдсэн гэдэгт найдаж болно, бид үүн дээр хурдан ажиллах боломжтой.
Энэхүү арга нь аль хэдийн хэлэлцсэн цөм тогтоох энгийн аргуудын хамт өөрийгөө сайн харуулж, хэдэн мянган оройн хэмжээтэй зарим тестийг шийддэг. Гэхдээ жишээлбэл, куб графикт (өөрөөр хэлбэл орой бүрийн зэрэг нь гурван байдаг график) тохиромжгүй.
Нэлээд энгийн санаан дээр үндэслэсэн өөр нэг санаа бий: хэрэв график салгагдсан бол түүний холбогдсон бүрэлдэхүүн хэсгүүдийн асуудлыг бие даан шийдэж, хариултуудыг төгсгөлд нь нэгтгэж болно. Дашрамд хэлэхэд энэ бол схемийн жижиг амласан өөрчлөлт бөгөөд энэ нь шийдлийг ихээхэн хурдасгах болно: өмнө нь энэ тохиолдолд бид бүрэлдэхүүн хэсгүүдийн хариуг тооцоолохын тулд тухайн үеийн бүтээгдэхүүн дээр ажилладаг байсан бол одоо бид ажиллаж байна. нийлбэр. Мөн салаалах ажлыг хурдасгахын тулд та холбогдсон графикийг салгагдсан график болгон хувиргах хэрэгтэй.
Үүнийг хэрхэн хийх вэ? Хэрэв график дээр үе мөчний цэг байгаа бол та түүнтэй тэмцэх хэрэгтэй. Артикуляцийн цэг нь графикийг арилгахад холболтоо алддаг орой юм. График дахь бүх уулзвар цэгүүдийг шугаман цагийн сонгодог алгоритм ашиглан олж болно. Энэ арга нь салаажилтыг ихээхэн хурдасгадаг.
Сонгосон оройн аль нэгийг арилгахад график нь холбогдсон бүрэлдэхүүн хэсгүүдэд хуваагдана.
Бид үүнийг хийх болно, гэхдээ бид илүү ихийг хүсч байна. Жишээлбэл, графикаас жижиг оройн зүслэгүүдийг хайж, оройнуудын дагуу хуваах хэрэгтэй. Миний мэдэх хамгийн бага дэлхийн оройн зүсэлтийг олох хамгийн үр дүнтэй арга бол шоо цагт баригдсан Гомори-Ху модыг ашиглах явдал юм. PACE Challenge-д графикийн ердийн хэмжээ нь хэдэн мянган оройтой байдаг. Ийм нөхцөлд рекурсын модны орой бүрт хэдэн тэрбум үйлдлүүд хийх шаардлагатай болдог. Хуваарилагдсан хугацаанд асуудлыг шийдэх нь ердөө л боломжгүй юм.
Шийдлийг оновчтой болгохыг хичээцгээе. Хос оройн хоорондох хамгийн бага оройг хамгийн их урсгалыг бий болгох ямар ч алгоритмаар олж болно. Та үүнийг ийм сүлжээнд оруулах боломжтой , практик дээр энэ нь маш хурдан ажилладаг. Ашиглалтын хугацааны тооцоог онолын хувьд батлах боломжтой гэж би хардаж байна , энэ нь аль хэдийн нэлээд хүлээн зөвшөөрөгдсөн.
Би хэд хэдэн удаа санамсаргүй оройнуудын хоорондох зүсэлтийг хайж, хамгийн тэнцвэртэй оройг авахыг оролдсон. Харамсалтай нь энэ нь нээлттэй PACE Challenge тестийн үр дүнд муу үр дүнд хүрсэн. Би үүнийг хамгийн дээд зэрэглэлийн оройг хуваах алгоритмтай харьцуулж, тэдгээрийг буух гүнд хязгаарлалттайгаар ажиллуулсан. Ийм аргаар зүсэлт олох гэж оролдсон алгоритм нь том графикуудыг үлдээсэн. Энэ нь зүсэлт нь маш тэнцвэргүй болсонтой холбоотой юм: 5-10 оройг арилгасны дараа зөвхөн 15-20-ыг нь салгах боломжтой болсон.
Онолын хувьд хамгийн хурдан алгоритмуудын тухай нийтлэлүүд нь хуваах оройг сонгоход илүү дэвшилтэт арга техникийг ашигладаг болохыг тэмдэглэх нь зүйтэй. Ийм техник нь маш нарийн төвөгтэй хэрэгжилттэй бөгөөд ихэвчлэн цаг хугацаа, санах ойн хувьд гүйцэтгэл муутай байдаг. Би дадлага хийхэд тохиромжтой зүйлийг тодорхойлж чадаагүй.
Хялбаршуулах дүрмийг хэрхэн хэрэглэх вэ
Бидэнд цөм болгох санаанууд аль хэдийн бий. Би танд сануулъя:
- Хэрэв тусгаарлагдсан орой байвал устгана уу.
- Хэрэв 1-р зэргийн орой байвал түүнийг зайлуулж, хөршийг нь хариуд нь аваарай.
- Хэрэв доод тал нь градусын орой байвал k+1, буцааж авах.
Эхний хоёрт бүх зүйл тодорхой, гурав дахь нь нэг заль мэх байна. Хэрэв баарны тухай комик асуудалд бид дээд хязгаарыг өгсөн k, дараа нь PACE Challenge-д та хамгийн бага хэмжээтэй оройн тагийг олох хэрэгтэй. Энэ нь хайлтын асуудлыг шийдвэрийн асуудал болгон хувиргах ердийн хэлбэр бөгөөд ихэвчлэн хоёр төрлийн асуудлын хооронд ямар ч ялгаа байдаггүй. Практик дээр бид оройг хамарсан асуудлын шийдлийг бичиж байгаа бол ялгаа гарч болзошгүй. Жишээлбэл, гурав дахь цэгийн адил.
Хэрэгжилтийн талаас нь авч үзвэл хоёр арга зам байна. Эхний аргыг давталттай гүнзгийрүүлэх гэж нэрлэдэг. Энэ нь дараах байдалтай байна: бид хариултыг доороос нь боломжийн хязгаарлалтаар эхлүүлж, дараа нь энэ хязгаарлалтыг дээрх хариултын хязгаарлалт болгон ашиглан алгоритмаа ажиллуулж, рекурсын хувьд энэ хязгаарлалтаас доогуур орохгүй. Хэрэв бид ямар нэг хариулт олсон бол энэ нь оновчтой байх нь баталгаатай, эс тэгвээс бид энэ хязгаарыг нэгээр нэмэгдүүлж, дахин эхлүүлж болно.
Өөр нэг арга бол одоогийн оновчтой хариултыг хадгалах ба жижиг хариулт хайх, олдсон үед энэ параметрийг өөрчлөх явдал юм k хайлт хийхдээ шаардлагагүй мөчрүүдийг таслах зорилгоор.
Шөнийн хэд хэдэн туршилт хийсний дараа би эдгээр хоёр аргыг хослуулан шийдсэн: эхлээд хайлтын гүнд ямар нэгэн хязгаарлалт тавьж алгоритмаа ажиллуулж (үндсэн шийдэлтэй харьцуулахад маш бага хугацаа шаардагдахаар сонгосон) хамгийн сайн аргыг ашигладаг. шийдэл нь хариултын дээд хязгаар гэж олддог - өөрөөр хэлбэл ижил зүйл k.
2-р зэргийн орой
Бид 0 ба 1 градусын оройг авч үзсэн. Үүнийг 2-р зэргийн оройгоор хийж болох боловч энэ нь графикаас илүү төвөгтэй үйлдлүүдийг хийх шаардлагатай болно.
Үүнийг тайлбарлахын тулд бид оройнуудыг ямар нэгэн байдлаар тодорхойлох хэрэгтэй. 2 зэрэгтэй оройг орой гэж нэрлэе v, мөн түүний хөршүүд - оройнууд x и y. Дараа нь бид хоёр хэрэг гарна.
- Хэзээ x и y - хөршүүд. Дараа нь та хариулж болно x и yболон v устгах. Үнэн хэрэгтээ энэ гурвалжингаас дор хаяж хоёр оройг авах шаардлагатай бөгөөд хэрэв бид үүнийг авбал алдахгүй нь гарцаагүй. x и y: тэд өөр хөрштэй байх магадлалтай, мөн v Тэд энд байхгүй.
- Хэзээ x и y - хөрш биш. Дараа нь бүх гурван оройг нэг болгон нааж болно гэж заасан. Гол санаа нь энэ тохиолдолд оновчтой хариулт байгаа бөгөөд бид аль нэгийг нь авдаг v, эсвэл хоёр орой x и y. Түүнээс гадна, эхний тохиолдолд бид бүх хөршүүдийг хариуд нь авах ёстой x и y, гэхдээ хоёрдугаарт энэ нь шаардлагагүй юм. Энэ нь хариуд нь наасан оройг авахгүй байх, авах үед яг таарч байна. Хоёр тохиолдолд ийм үйлдлийн хариу нэгээр буурдаг гэдгийг тэмдэглэх нь зүйтэй.
Шугаман шугаман цагт энэ аргыг үнэн зөв хэрэгжүүлэхэд нэлээд хэцүү гэдгийг тэмдэглэх нь зүйтэй. Оройнуудыг наах нь нарийн төвөгтэй ажиллагаа бөгөөд та хөршүүдийн жагсаалтыг хуулах хэрэгтэй. Хэрэв үүнийг хайхрамжгүй хийвэл та асимптотын хувьд оновчтой бус ажиллах хугацаатай болно (жишээлбэл, наалт бүрийн дараа олон ирмэгийг хуулж авбал). Би 2-р зэрэглэлийн оройгоос бүх замыг хайж олох, ийм оройнуудын мөчлөг эсвэл нэгээс бусад бүх оройнуудын мөчлөг гэх мэт олон онцгой тохиолдлуудад дүн шинжилгээ хийхээр шийдсэн.
Нэмж дурдахад, энэ үйлдлийг буцаах боломжтой байх шаардлагатай бөгөөд ингэснээр рекурсиас буцаж ирэхэд бид графикийг анхны хэлбэрт оруулах болно. Үүнийг баталгаажуулахын тулд би нэгтгэсэн оройнуудын захын жагсаалтыг цэвэрлээгүй бөгөөд дараа нь аль ирмэгүүд хаашаа явах ёстойг л мэдэж байсан. Графикийн энэхүү хэрэгжилт нь нарийвчлал шаарддаг боловч энэ нь шударга шугаман цагийг өгдөг. Хэдэн арван мянган ирмэг бүхий графикуудын хувьд энэ нь процессорын кэшэд багтдаг бөгөөд энэ нь хурдны хувьд ихээхэн давуу тал өгдөг.
Шугаман цөм
Эцэст нь цөмийн хамгийн сонирхолтой хэсэг.
Эхлэхийн тулд хоёр талт графикуудын хамгийн бага оройн бүрхэвчийг ашиглан олж болно гэдгийг санаарай . Үүнийг хийхийн тулд та алгоритмыг ашиглах хэрэгтэй хамгийн их тохирохыг олохын тулд, дараа нь теоремыг ашиглана .
Шугаман цөмийн санаа нь: эхлээд орой бүрийн оронд графикийг хуваана. v хоёр оргилыг нэмье и , ирмэг бүрийн оронд у - v хоёр хавирга нэмье и . Үүссэн график нь хоёр талт байх болно. Үүний хамгийн бага оройн бүрхэвчийг олцгооё. Анхны графикийн зарим орой хоёр удаа, зарим нь нэг удаа, зарим нь хэзээ ч хүрэхгүй. Немхаузер-Троттер теоремд энэ тохиолдолд нэг ч удаа цохигдоогүй оройг арилгаж, хоёр удаа цохисон оройг буцааж авах боломжтой гэж заасан байдаг. Түүгээр ч барахгүй үлдсэн оройнуудын (нэг удаа цохисон) та дор хаяж талыг нь хариулт болгон авах хэрэгтэй гэж тэр хэлэв.
Бид үүнээс илүүг үлдээж сурсан 2k оргилууд Үнэн хэрэгтээ, хэрэв үлдсэн хариулт нь бүх оройнуудын дор хаяж тал нь байвал нийт оройнуудаас илүү орой байхгүй болно. 2k.
Энд би бага зэрэг урагшлах боломжтой болсон. Ийм байдлаар бүтээгдсэн цөм нь бид хоёр талт график дээр ямар төрлийн хамгийн бага оройн бүрхэвч авсанаас хамаарах нь ойлгомжтой. Үлдсэн оройн тоо хамгийн бага байхын тулд би нэгийг авахыг хүсч байна. Өмнө нь тэд үүнийг зөвхөн цаг хугацаанд нь хийж чаддаг байсан . Би тэр үед энэ алгоритмын хэрэгжилтийг бодож олсон , ингэснээр энэ цөмийг салбарлах үе шат бүрт хэдэн зуун мянган оройн графикаас хайж болно.
үр дүн
Дадлагаас харахад миний шийдэл хэдэн зуун орой, хэдэн мянган ирмэгийн туршилтанд сайн ажилладаг. Ийм туршилтаар хагас цагийн дараа шийдлийг олно гэж найдаж болно. Зөвшөөрөгдөх хугацаанд хариултыг олох магадлал, зарчмын хувьд, график нь хангалттай олон тооны оройн өндөр зэрэгтэй, жишээлбэл, 10 ба түүнээс дээш зэрэгтэй байвал нэмэгддэг.
Уралдаанд оролцохын тулд шийдлийг илгээх шаардлагатай байв . Тэнд өгсөн мэдээллээс харахад , нээлттэй тестийн миний шийдэл хорин хүнээс гуравт ордог, хоёр дахь нь том зөрүүтэй. Үнэнийг хэлэхэд, өрсөлдөөнд шийдлүүдийг хэрхэн үнэлэх нь тодорхойгүй байна: жишээлбэл, миний шийдэл дөрөвдүгээрт орсон шийдлээс цөөн тестийг давдаг, гэхдээ тэнцсэн тохиолдолд илүү хурдан ажилладаг.
Хаалттай шинжилгээний хариу долдугаар сарын XNUMX-нд гарна.
Эх сурвалж: www.habr.com