Sharof rashidov nomidagi samarqand davlat universiteti amaliy matematika yo

2.1 Ko’ptarmoqli algoritm
Da virtual bo'shliqlarni qidirish algoritmlari ishlatiladi cheklovni qondirish muammosi, bu erda aniq matematikani qondiradigan ba'zi bir o'zgaruvchilarga qiymat belgilash to'plamini topish maqsad qilingan tenglamalar va tengsizliklar / tengliklar. Bundan tashqari, agar maqsad o'zgaruvchan topshiriqni topish bo'lsa, ular ishlatiladi maksimal darajaga ko'tarish yoki kamaytirish ushbu o'zgaruvchilarning ma'lum bir funktsiyasi. Ushbu muammolar algoritmlari asosiyni o'z ichiga oladi qo'pol kuch bilan qidirish ("naif" yoki "ma'lumotsiz" qidiruv deb ham ataladi) va turli xil evristika bu bo'shliqning tuzilishi to'g'risida qisman bilimlardan foydalanishga harakat qiladigan, masalan, chiziqli bo'shashish, cheklovlarni yaratish va cheklovlarni ko'paytirish.
Muhim subklass quyidagilardir mahalliy qidiruv qidiruv maydonining elementlarini tepaliklar grafika, ish uchun qo'llaniladigan evristika to'plami bilan aniqlangan qirralar bilan; va bo'shliqni skanerlash, masalan, eng tik tushish yoki eng yaxshisi mezon yoki a stoxastik qidiruv. Ushbu toifaga umumiy turlarning xilma-xilligi kiradi metaevistik kabi usullar simulyatsiya qilingan tavlanish, tabu qidirish, A guruhlari va genetik dasturlash, bu o'zboshimchalik bilan evristikani o'ziga xos usullar bilan birlashtiradi.
Ushbu sinf shuningdek turli xillarni o'z ichiga oladi daraxtlarni qidirish algoritmlari, elementlarni a ning tepalari sifatida ko'rib chiqadigan daraxt va ushbu daraxtni maxsus tartibda aylanib o'ting. Ikkinchisining misollari kabi to'liq usullarni o'z ichiga oladi birinchi chuqurlikdagi qidiruv va kenglik bo'yicha birinchi qidiruv, shuningdek, turli xil evristikaga asoslangan daraxtlarni kesishni qidirish kabi usullar orqaga qaytish va filial va bog'langan. Umumiy metaheuristikadan farqli o'laroq, eng yaxshi holatda faqat ehtimollik ma'noda ishlaydi, ushbu daraxtlarni qidirish usullarining ko'pchiligiga, agar etarli vaqt berilsa, aniq yoki maqbul echimni topishga kafolat beriladi. Bu "to'liqlik ".
Yana bir muhim kichik sinf bu algoritmlardan iborat o'yin daraxti kabi bir nechta o'yinchi o'yinlari shaxmat yoki tavla, uning tugunlari mavjud vaziyatdan kelib chiqishi mumkin bo'lgan barcha mumkin bo'lgan o'yin vaziyatlaridan iborat. Ushbu muammolardan maqsad raqib (lar) ning barcha mumkin bo'lgan harakatlarini hisobga olgan holda g'alaba qozonish uchun eng yaxshi imkoniyatni ta'minlaydigan harakatni topishdir. Shunga o'xshash muammolar, odamlar yoki mashinalar ketma-ket qarorlar qabul qilishlari kerak bo'lganda yuzaga keladi, natijada ularning natijalari umuman boshqalarga bo'ysunmaydi, masalan robot ko'rsatma yoki marketing, moliyaviy, yoki harbiy strategiyani rejalashtirish. Bunday muammo - kombinatorial qidiruv - doirasida keng o'rganilgan sun'iy intellekt. Ushbu sinf uchun algoritmlarga misollar minimaks algoritmi, alfa-beta Azizillo, va A * algoritmi va uning variantlari.
Berilgan strukturaning pastki tuzilmalari uchun
"Kombinatorial qidirish" nomi odatda ma'lum bir pastki tuzilmani qidiradigan algoritmlar uchun ishlatiladi alohida tuzilish, masalan, grafik, a mag'lubiyat, cheklangan guruh, va hokazo. Atama kombinatorial optimallashtirish odatda maqsad ba'zi parametrlarning maksimal (yoki minimal) qiymatiga ega bo'lgan pastki tuzilmani topish bo'lsa ishlatiladi. (Sub-tuzilma odatda kompyuterda cheklovlarga ega bo'lgan butun sonli o'zgaruvchilar to'plami bilan namoyish etilganligi sababli, bu muammolarni cheklash qondirish yoki diskret optimallashtirishning maxsus hollari sifatida ko'rish mumkin; ammo ular odatda mavhumroq sharoitda tuzilgan va echilgan ichki vakillik aniq ko'rsatilmagan.)
Muhim va keng o'rganilgan subklass quyidagilardir grafik algoritmlari, jumladan grafani kesib o'tish algoritmlari, berilgan grafada aniq pastki tuzilmalarni topish uchun - masalan subgrafalar, yo'llar, sxemalar va boshqalar. Bunga misollar kiradi Dijkstra algoritmi, Kruskal algoritmi, eng yaqin qo'shni algoritmi va Primning algoritmi.
Ushbu toifadagi yana bir muhim subklass quyidagilardir qatorlarni qidirish algoritmlari, bu satrlar ichidagi naqshlarni qidiradi. Ikkita taniqli misollar Boyer-Mur va Knuth-Morris-Pratt algoritmlari ga asoslangan bir nechta algoritmlar daraxt qo'shimchasi ma'lumotlar tuzilishi.
Maksimal funktsiyani qidiring
1953 yilda amerikalik statistik Jek Kifer o'ylab topilgan Fibonachchini qidirish unimodal funktsiyani maksimalini topish uchun ishlatilishi mumkin va kompyuter fanida ko'plab boshqa dasturlarga ega.
Kvant kompyuterlari uchun
Uchun mo'ljallangan qidirish usullari ham mavjud kvantli kompyuterlar, kabi Grover algoritmi, nazariy jihatdan ma'lumotlar tuzilmalari yoki evristikaning yordamisiz ham chiziqli yoki qo'pol kuch bilan qidirishdan ko'ra tezroq.
Virtual qidirish joylari uchun
Shuningdek qarang: Hal qiluvchi
Da virtual bo'shliqlarni qidirish algoritmlari ishlatiladi cheklovni qondirish muammosi, bu erda aniq matematikani qondiradigan ba'zi bir o'zgaruvchilarga qiymat belgilash to'plamini topish maqsad qilingan tenglamalar va tengsizliklar / tengliklar. Bundan tashqari, agar maqsad o'zgaruvchan topshiriqni topish bo'lsa, ular ishlatiladi maksimal darajaga ko'tarish yoki kamaytirish ushbu o'zgaruvchilarning ma'lum bir funktsiyasi. Ushbu muammolar algoritmlari asosiyni o'z ichiga oladi qo'pol kuch bilan qidirish ("naif" yoki "ma'lumotsiz" qidiruv deb ham ataladi) va turli xil evristika bu bo'shliqning tuzilishi to'g'risida qisman bilimlardan foydalanishga harakat qiladigan, masalan, chiziqli bo'shashish, cheklovlarni yaratish va cheklovlarni ko'paytirish.
Muhim subklass quyidagilardir mahalliy qidiruv qidiruv maydonining elementlarini tepaliklar grafika, ish uchun qo'llaniladigan evristika to'plami bilan aniqlangan qirralar bilan; va bo'shliqni skanerlash, masalan, eng tik tushish yoki eng yaxshisi mezon yoki a stoxastik qidiruv. Ushbu toifaga umumiy turlarning xilma-xilligi kiradi metaevistik kabi usullar simulyatsiya qilingan tavlanish, tabu qidirish, A guruhlari va genetik dasturlash, bu o'zboshimchalik bilan evristikani o'ziga xos usullar bilan birlashtiradi.
Ushbu sinf shuningdek turli xillarni o'z ichiga oladi daraxtlarni qidirish algoritmlari, elementlarni a ning tepalari sifatida ko'rib chiqadigan daraxt va ushbu daraxtni maxsus tartibda aylanib o'ting. Ikkinchisining misollari kabi to'liq usullarni o'z ichiga oladi birinchi chuqurlikdagi qidiruv va kenglik bo'yicha birinchi qidiruv, shuningdek, turli xil evristikaga asoslangan daraxtlarni kesishni qidirish kabi usullar orqaga qaytish va filial va bog'langan. Umumiy metaheuristikadan farqli o'laroq, eng yaxshi holatda faqat ehtimollik ma'noda ishlaydi, ushbu daraxtlarni qidirish usullarining ko'pchiligiga, agar etarli vaqt berilsa, aniq yoki maqbul echimni topishga kafolat beriladi. Bu "to'liqlik ".
Yana bir muhim kichik sinf bu algoritmlardan iborat o'yin daraxti kabi bir nechta o'yinchi o'yinlari shaxmat yoki tavla, uning tugunlari mavjud vaziyatdan kelib chiqishi mumkin bo'lgan barcha mumkin bo'lgan o'yin vaziyatlaridan iborat. Ushbu muammolardan maqsad raqib (lar) ning barcha mumkin bo'lgan harakatlarini hisobga olgan holda g'alaba qozonish uchun eng yaxshi imkoniyatni ta'minlaydigan harakatni topishdir. Shunga o'xshash muammolar, odamlar yoki mashinalar ketma-ket qarorlar qabul qilishlari kerak bo'lganda yuzaga keladi, natijada ularning natijalari umuman boshqalarga bo'ysunmaydi, masalan robot ko'rsatma yoki marketing, moliyaviy, yoki harbiy strategiyani rejalashtirish. Bunday muammo - kombinatorial qidiruv - doirasida keng o'rganilgan sun'iy intellekt. Ushbu sinf uchun algoritmlarga misollar minimaks algoritmi, alfa-beta Azizillo, va A * algoritmi va uning variantlari.
Berilgan strukturaning pastki tuzilmalari uchun
"Kombinatorial qidirish" nomi odatda ma'lum bir pastki tuzilmani qidiradigan algoritmlar uchun ishlatiladi alohida tuzilish, masalan, grafik, a mag'lubiyat, cheklangan guruh, va hokazo. Atama kombinatorial optimallashtirish odatda maqsad ba'zi parametrlarning maksimal (yoki minimal) qiymatiga ega bo'lgan pastki tuzilmani topish bo'lsa ishlatiladi. (Sub-tuzilma odatda kompyuterda cheklovlarga ega bo'lgan butun sonli o'zgaruvchilar to'plami bilan namoyish etilganligi sababli, bu muammolarni cheklash qondirish yoki diskret optimallashtirishning maxsus hollari sifatida ko'rish mumkin; ammo ular odatda mavhumroq sharoitda tuzilgan va echilgan ichki vakillik aniq ko'rsatilmagan.)
Muhim va keng o'rganilgan subklass quyidagilardir grafik algoritmlari, jumladan grafani kesib o'tish algoritmlari, berilgan grafada aniq pastki tuzilmalarni topish uchun - masalan subgrafalar, yo'llar, sxemalar va boshqalar. Bunga misollar kiradi Dijkstra algoritmi, Kruskal algoritmi, eng yaqin qo'shni algoritmi va Primning algoritmi.
Ushbu toifadagi yana bir muhim subklass quyidagilardir qatorlarni qidirish algoritmlari, bu satrlar ichidagi naqshlarni qidiradi. Ikkita taniqli misollar Boyer-Mur va Knuth-Morris-Pratt algoritmlari ga asoslangan bir nechta algoritmlar daraxt qo'shimchasi ma'lumotlar tuzilishi.
Maksimal funktsiyani qidiring
1953 yilda amerikalik statistik Jek Kifer o'ylab topilgan Fibonachchini qidirish unimodal funktsiyani maksimalini topish uchun ishlatilishi mumkin va kompyuter fanida ko'plab boshqa dasturlarga ega.
Qayta ishlab chiqarish inqirozi
Tavsiya etuvchi tizimlar sohasiga ta'sir ko'rsatdi replikatsiya inqirozi shuningdek. Eng yaxshi konferentsiyalarda (SIGIR, KDD, WWW, RecSys) nashr etilgan top-k tavsiya muammosiga chuqur o'rganish yoki asabiy usullarni qo'llagan nashrlarni tahlil qilish shuni ko'rsatdiki, o'rtacha 40% dan kam maqolalar mualliflari tomonidan takrorlanadi. o'qish, ba'zi konferentsiyalarda 14% kam. Umuman olganda, tadqiqotda 18 ta maqola aniqlangan bo'lib, ulardan 7 tasi ko'paytirilishi mumkin va 6 tasi eskirgan moslashtirilgan bazaviy jadvallardan ustun bo'lishi mumkin.^[93] Xuddi shu guruhning yana bir maqolasi ketma-ketlikni biladigan tavsiya etuvchi tizimlar domenidagi metodlarni taqqoslaydi.^[94]Xuddi shu usullar to'plamini taqqoslash bo'yicha yaqinda olib borilgan ishlar sifat jihatidan juda boshqacha natijalarga erishdi^[95] asabiy usullar eng yaxshi ishlaydigan usullardan biri deb topildi, shuningdek, asabiy va chuqur o'rganish usullari keng sinovdan o'tgan sanoat sohasida keng qo'llaniladi.^[96][58][59]Qayta ishlab chiqarish mavzusi yangi emas, 2011 yilda, Ekstrand, Konstan va boshq. "Tavsiya etuvchilar tizimining tadqiqot natijalarini ko'paytirish va kengaytirish qiyin" deb baholagan va baholash "izchil ishlamaydi".^[97] Konstan va Adomavicius "Tavsiya etuvchi tizimlar tadqiqotlari hamjamiyati inqirozga yuz tutmoqda, chunki ko'plab ishlarda jamoaviy bilimga ozgina hissa qo'shadigan natijalar mavjud […] ko'pincha tadqiqotlarda [...] baholashning to'g'ri baholanmaganligi va shu sababli, mazmunli hissalarni taqdim etish. "^[98] Natijada, tavsiya etuvchi tizimlar bo'yicha ko'plab tadqiqotlar takrorlanmaydigan deb hisoblanishi mumkin.^[99] Demak, tavsiya etuvchi tizimlar operatorlari savolga javob berish uchun joriy tadqiqotlarda juda kam ko'rsatmalarni topadilar, bu esa tavsiya etuvchi tizimlarda qanday tavsiya etilgan yondashuvlar. Said & Bellogín ushbu sohada chop etilgan hujjatlarni o'rganib chiqdi, shuningdek, eng mashhur tavsiyalar bazalarini taqqosladi va natijada bir xil algoritmlar va ma'lumotlar to'plamlari ishlatilgan taqdirda ham katta nomuvofiqliklarni topdi.^[100] Ba'zi tadqiqotchilar tavsiyanomalar algoritmlari yoki stsenariylaridagi ozgina tafovutlar tavsiya etuvchi tizim samaradorligining kuchli o'zgarishiga olib kelganligini namoyish etishdi. Ular hozirgi vaziyatni yaxshilash uchun etti harakat zarur degan xulosaga kelishdi:^[99] "(1) boshqa tadqiqot sohalarini o'rganing va ulardan o'rganing, (2) takrorlanuvchanlik to'g'risida umumiy tushunchani toping, (3) takrorlanuvchanlikka ta'sir qiluvchi determinantlarni aniqlang va tushunasiz, (4) kengroq eksperimentlar o'tkazasiz (5) nashr etish amaliyotini zamonaviylashtirasiz, ( 6) tavsiyanomalarni ishlab chiqish va ulardan foydalanishni rivojlantirish va (7) tavsiya etuvchi tizimlarni tadqiq qilish bo'yicha eng yaxshi qo'llanmalarni yaratish. "

Tarkibga asoslangan filtrlash

Tavsiya etuvchi tizimlarni loyihalashda yana bir keng tarqalgan yondashuv tarkibga asoslangan filtrlash. Tarkibga asoslangan filtrlash usullari ob'ekt tavsifiga va foydalanuvchi afzal ko'rgan profiliga asoslanadi.^[43][44] Ushbu usullar foydalanuvchi uchun emas, balki ma'lumotlar (ism, joy, tavsif va boshqalar) bo'yicha ma'lum ma'lumotlar mavjud bo'lgan holatlarga mos keladi. Tarkibga asoslangan tavsiyanomalar tavsiyanomani foydalanuvchiga xos tasniflash muammosi sifatida ko'rib chiqadi va ob'ektning xususiyatlariga qarab foydalanuvchiga yoqishi va yoqmasligi uchun tasniflagichni o'rganadi.
Ushbu tizimda elementlarni tavsiflash uchun kalit so'zlardan foydalaniladi va a foydalanuvchi profili foydalanuvchi yoqadigan narsaning turini ko'rsatish uchun qurilgan. Boshqacha qilib aytadigan bo'lsak, ushbu algoritmlar foydalanuvchi o'tmishda yoqqan yoki hozirgi paytda tekshiradigan narsalarga o'xshash narsalarni tavsiya qilishga harakat qiladi. Ushbu vaqtinchalik profilni yaratish uchun foydalanuvchi tizimga kirish mexanizmiga ishonmaydi. Xususan, nomzodning turli xil narsalari foydalanuvchi tomonidan ilgari baholangan narsalar bilan taqqoslanadi va eng yaxshi mos keladigan narsalar tavsiya etiladi. Ushbu yondashuvning ildizi kelib chiqadi ma'lumot olish va axborotni filtrlash tadqiqot.
Yaratish uchun foydalanuvchi profili, tizim asosan ikki turdagi ma'lumotlarga e'tibor beradi:
1. Foydalanuvchi afzal ko'rgan model.
2. Foydalanuvchining tavsiya etuvchi tizim bilan o'zaro aloqalari tarixi.
Asosan, ushbu usullar tizimdagi elementni tavsiflovchi element profilini (ya'ni, alohida atributlar va xususiyatlar to'plamini) ishlatadi. Tizimdagi elementlarning xususiyatlarini mavhumlashtirish uchun elementni taqdim etish algoritmi qo'llaniladi. Keng tarqalgan algoritm bu tf – idf vakillik (shuningdek, vektor makonining vakili deb ataladi).^[45] Tizim elementlarning og'irlik vektori asosida foydalanuvchilarning tarkibiga asoslangan profilini yaratadi. Og'irliklar foydalanuvchi uchun har bir xususiyatning muhimligini bildiradi va turli xil texnikalar yordamida alohida baholangan tarkib vektorlaridan hisoblanishi mumkin. Oddiy yondashuvlar nominal element vektorining o'rtacha qiymatlaridan foydalanadi, boshqa murakkab usullar esa mashinani o'rganish usullaridan foydalanadi Bayes tasniflagichlari, klaster tahlili, qaror daraxtlari va sun'iy neyron tarmoqlari foydalanuvchiga buyumni yoqtirish ehtimolini taxmin qilish uchun.^[46]