Nazariy topshiriqlar To'la tanlov algoritmi

Nazariy topshiriqlar

1.To'la tanlov algoritmi

To'la tanlov (yoki brute force) algoritmini analiz qilishdan oldin algoritm dunyosida asosan 2 ta asosiy tushuncha juda muhim ahamiyatga egadir.

Misol tariqasida tushuntirshga harakat qilaman. Sizga savol qo’limda ma’lumot bor, ushbu ma’lumotni Toshkentdan Londonga yuborishim kerak bu holda qaysi yo’llar orqali yuborsam bo’ladi (masalan:Telegram, facebook, google drive, yandex disk). Siz aytishingiz mumkin ma’lumotni telegramdan yuborishimiz maqul deb chunki tez va qulay. Bu javob doim ham to’g’ri bo’lmaydi sababi siz javob berishdan oldin mendan so’rashingiz kerak edi. Ma’lumotning hajmi qancha deb. Mendagi ma’lumot hajmi 10Gb edi. Endi siz aytgan usul o’zini oqlamasligi mumkin sababi telegram orqali yuborilgan axborot (100Gb lik) tarmoq tezligi 25Mb/s bo’lganda ham yetib borish vaqti 8 soat 53 min 20s da yetib boradi. Eng optimal yo’l samolyotda ma’lumotni yuborsam maqsadga muvofiq bo’ladi.

Istalgan muammoni hal qilishda masala yechimining vaqt va xotiradan oladiga joy jihatlariga alohida e’tibor qaratiladi. Yuqoridagi masala agar ma’lumot telegram orqali yuborilsa biz vaqtdan yutqazar edi.

Algoritmlashda Time Complexity va Space complexity degan tushunchalar mavjud. Endi to’la tanlov algoritmi ni analiz qiklishga kirishsak

To'la tanlov (yoki brute force) algoritmi - matematik muammolarni hal qilish usuli. Har qanday variantni tugatib, echim topish usullari sinfiga tegishli. To'liq qidirishning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan echimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.

To'la tanlov (yoki brute force) algoritmi yuqoridagi vaqt va xotiradan oladigan joy ni deyarli hisobga olmaydi. Bu esa masala yechimini topadi lekin eng yomon holatlarda yechadi degani

NP (non-deterministic polynomial) sinfidagi har qanday muammoni to'liq izlash orqali hal qilish mumkin. Bu holda, har qanday aniq echimdan ob'ektiv funktsiyani hisoblash barcha mumkin bo'lgan echimlarning soniga qarab, ko'paytirilgan vaqt ichida amalga oshirilishi mumkin bo'lsa ham, to'liq qidiruv eksponensial vaqtni talab qilishi mumkin.

Misol tariqasida quyidagi savollarni nazariy jihatdan yechishga harakat qilamiz - bu sayohat qiluvchi sotuvchi muammosi (Traveling Salesman Problem TSP). Aytaylik, sotuvchi butun mamlakat bo'ylab 10 ta shaharga tashrif buyurishi kerak. Qat'iy belgilangan masofani minimallashtirish uchun qaysi shaharlarga borish kerakligini qanday aniqlash mumkin? To'la tanlov (yoki brute force) yechimi oddiygina har bir marshrut uchun umumiy masofani hisoblash va keyin eng qisqa yo'lni tanlashdir. Bu ayniqsa samarali emas, chunki aqlli algoritmlar yordamida ko'plab mumkin bo'lgan yo'nalishlarni yo'q qilish mumkin.

2. Algoritmni loyihalash

Saylovlar barcha shakl va o'lchamlarda bo'ladi. Buyuk Britaniyada bosh vazir rasman monarx tomonidan tayinlanadi, u odatda Jamoatlar palatasida eng ko'p o'rinni egallagan siyosiy partiya rahbarini tanlaydi. Amerika Qo'shma Shtatlari ko'p bosqichli Saylov Kollejidan foydalanadi, bunda fuqarolar har bir shtat Prezidentni saylaydigan saylovchilarni qanday ajratishi kerakligi to'g'risida ovoz beradi. Ehtimol saylovni eng oddiy yo'li "ko'plik ovozi" usuli orqali amalga oshiriladi (xuddi yurtimizdagidek). Ko'pchilik ovoz berishda har bir saylovchi bitta nomzodga ovoz beradi. Saylov oxirida qaysi biri eng ko'p ovoz to'plagan bo'lsa, u g'olib deb e'lon qilinadi.

Masala sharti quyidagicha

Sizga erkanda saylovdagi nomzodlar ismlari berilgan bo’ladi.

Ularning soni #define MAX 5 (const) bu doimiy (MAX ga teng) degan ma'noni anglatadi, bu dastur davomida ishlatilishi mumkin bo'lgan sintaksisdir. Bu erda bu saylovda qatnashishi mumkin bo'lgan nomzodlarning maksimal sonini anglatadi.

Keyin fayl nomzod deb nomlangan tuzilmani belgilaydi. Har bir nomzod ikkita maydonga ega: nomzodning ismini ko'rsatadigan satr va satrda berilgan ovozlar sonini bildiruvchi satr. Keyinchalik, fayl global nomzodlarni belgilaydi, bu erda har bir element o'zi nomzod.

Keyin dastur har bir saylovchiga ovoz berishda qatnashish imkoniyatini beradi int main() funktsiyasiga saylovda g'olibni (yoki g'oliblarni) bosib chiqarish uchun qo'ng'iroq qiladi.

Dastur kompilyatisya qilinganda oyndana quyidachi chiqsa maqsadga muvofiq bo’ladi.

./saylov – bu tuzilgan dasturning nomi ketida nomzodlar ismlari

Ovozlar_soni: 5 ovoz beradigan shaxslarning soni bizda 33 mln bo’lishi mumkin

Tuzmoqchi bo’lgan dasturimiz quyidagicha ishlashi kerak

./saylov Mirziyoyev Saidov Narimanov // dasturning cosole da ishlash jarayoni

Ovozlar_soni: 5

Ovoz: Narimanov

Ovoz: Saidov

Ovoz: Mirziyoyev

Ovoz: Mirziyoyev

Ovoz: Mirziyoyev

Mirziyoyev // g’alaba qozongan nomzod nomi

 

Dastur implementatsiyasi

#include

#include

#include

//Nomzodlarning maksimal soni

#define MAX 5

//Nomzodlarning ismi va ular to’plagan ovozlarini yozish uchun o’zgaruvchilar

typedef struct

{

string name;

int votes;

}

candidate;

// Nomzodlar massivi

candidate candidates[MAX];

// Nomzodlar soni

int candidate_count;

// Funksiya prototipi asl funksiya pastda yozilgan

bool vote(string name);

void print_winner(void);

int main(int argc, string argv[])

{

// Dastur ishga tushirilganda uning to’g’ri ishlashini tekshirish

if (argc < 2)

{

printf("To’g’ri qiymat kiriting: saylov [Nomzodlar...]\n");

return 1;

}

// Nomzodlar quyidagilar

candidate_count = argc - 1;

if (candidate_count > MAX)

{

printf("Saylovdagi mavjud nomzodlarnning umumiy soni %i\n", MAX);

return 2;

}

for (int i = 0; i < candidate_count; i++)

{

candidates[i].name = argv[i + 1];

candidates[i].votes = 0;

}

int voter_count = get_int("Ovozlarning umumiy soni: ");

// ovozlar bo’yicha yurib chiqish

for (int i = 0; i < voter_count; i++)

{

string name = get_string("Ovoz: ");

// Ovozni tekshirish

if (!vote(name))

{

printf("Noto’g’ri ovoz kiritfingiz.\n"); }

}

// Saylov g’olibi

print_winner(); }

// Berilgan ovoz bilan umumiy ovozlarni yangilash

bool vote(string name)

{

bool exist = false;

for (int i = 0; i < candidate_count; i++)

{

//Kiritilgan nomzodning ismi bazadagisi bilan solishtirish

if (strcmp(name, candidates[i].name) == 0)

{

candidates[i].votes += 1;

exist = true;

break; }

}

return exist;

}

void print_winner(void)

{

//o’zgaruvchilarga boshlang’ich qiymat berish

int most = 0;

string winner;

//Eng ko’p ovozni aniqlash

for (int y = 0; y < candidate_count; y++)

{

if(candidates[y].votes >= most )

{

most = candidates[y].votes;

winner = candidates[y].name;

}

}

printf("Nomzod %s %i ovoz bilan g’olib bo’ldi\n", winner , most);

}

 

Amaliy topshiriqlar

Men ushbu vazifa uchun Oldga yo‘naltirilgan qisman tanlov algoritmi (Алгоритм последовательно селекция в перед); ya’ni ushbu algoritmning ikkinchi nomi Genetik algoritm ni blok-sxemalar asosida implementatsiyani namoyish qilmoqchiman. Genetik algoritm birinchi navbatda evolyutsion algoritmdir, boshqacha aytganda, algoritmning asosiy xususiyati bu kesishish (birlashtirish). Siz osongina taxmin qilishingiz mumkin bo'lganidek, algoritm g'oyasi tabiatdan bilan olingan va unga "kombinatsiyani" tanlash orqali erishiladi.

Umuman olganda ushbu algoritm quyidagi 3ta bosqichda amalga oshiriladi

• Chatishtirish

• Tanlash (tanlash)

• Yangi avlodning shakllanishi

Agar natija bizni qoniqtirmasa, natijalar bizni qoniqtira boshlaguncha yoki quyidagi shartlardan biri paydo bo'lmaguncha ushbu amallar takrorlanadi:

• Avlodlar (tsikllar) soni oldindan tanlangan maksimal darajaga etadi

• Mutatsiya vaqti tugadi

Yuqoridagi bosqichlarni batafsil yoritishga harakat qilaman.

Yangi populyatsiyaning vujudga kelishi. (Создание новой популяции. ) Ushbu bosqichda boshlang'ich populyatsiya yaratiladi, ehtimol bu unchalik katta bo'lmaydi, lekin algoritm bu muammoni hal qilishi mumkin. Asosiysi shundaki, ular "format" ga mos keladi va "ko'paytirishga moslashadi".

Ko'paytirish. Xo'sh, barchasi odamlarga o'xshaydi, farzand ko'rish uchun ikkita ota-ona kerak. Asosiysi, avlod (bola) ularning xususiyatlarini ota-onadan meros qilib olishi mumkin edi. Bunday holda, nafaqat omon qolganlar, balki ko'payadilar (bu ibora ayniqsa bema'ni, lekin bizda hamma narsa sharsimon bo'shliqda bo'lganligi sababli hamma narsani qilish mumkin), aks holda bitta alfa erkak ajralib chiqadi, ularning genlari boshqalarga to'g'ri keladi, ammo bu biz uchun mutlaqo nomaqbuldir.

Mutatsiyalar. Mutatsiyalar ko'payish bilan o'xshashdir, mutantlardan ma'lum miqdordagi shaxslar tanlanadi va oldindan belgilangan operatsiyalarga muvofiq o'zgartiriladi.

Tanlash. Bu erda eng shirin boshlanadi, biz aholidan "oldinga boradiganlar" ni tanlashni boshlaymiz. Shu bilan birga, biz tanlanganimizdan so'ng, "omon qolganlar" ning ulushini parametr shaklida ko'rsatamiz. Afsuski, qolgan odamlar o'lishi kerak

Diofantin tenglamalarimning (Диофантовых уравнений) misolini ko'rib chiqamiz (butun sonlar ildizlari bilan tenglamalar).

Tenglama ko’rinishi

a+2b+3c+4d=30;

Ushbu tenglamaning ildizlari [1; 30] oraliqda yotganligini taxmin qilamiz va shuning uchun biz 5 ni olamiz

a, b, c, d tasodifiy qiymatlari. (30-ning chegarasi, masalani soddalashtirish uchun maxsus qabul qilinadi).

Shunday qilib, bizda birinchi avlod bor:

1. (1,28,15,3)

2. (14,9,2,4)

3. (13,5,7,3)

4. (23,8,16,19)

5. (9,13,5,2)

Omon qolish darajasini (коэффициенты выживаемости),hisoblash uchun biz har bir echimni ifodaga almashtiramiz. Olingan qiymatdan 30 gacha bo'lgan masofa kerakli qiymatga ega bo'ladi.

1. |114-30|=84

2. |54-30|=24

3. |56-30|=26

4. |163-30|=133

5. |58-30|=28

Kichikroq qiymatlar mos ravishda 30 ga yaqinroq, ular ko'proq istalgan. Aniqlanishicha, katta qiymatlar omon qolish darajasi past bo'ladi. Tizimni yaratish uchun har birini (xromosoma) tanlash ehtimolini hisoblaymiz. Ammo echim koeffitsientlarning teskari qiymatlari yig'indisini olish va shu asosda foizlarni hisoblashdir. (0.135266 bet - teskari koeffitsientlar yig'indisi)

• (1/84)/0.135266 = 8.80%

• (1/24)/0.135266 = 30.8%

• (1/26)/0.135266 = 28.4%

• (1/133)/0.135266 = 5.56%

• (1/28)/0.135266 = 26.4%

Keyinchalik, biz bitta bolaga ega bo'lgan beshta ota-onani tanlaymiz. Imkoniyatdan ozod bo'lish uchun biz besh marta beramiz, har safar ota-ona bo'lish imkoniyati bir xil bo'ladi va tirik qolish imkoniyatiga teng bo'ladi.

3-1, 5-2, 3-5, 2-5, 5-3

Yuqorida ta'kidlab o'tilganidek, avlod ota va onaning genlari haqida ma'lumotni o'z ichiga oladi. Bunga turli yo'llar bilan erishish mumkin, ammo bu holda "krossover" ishlatiladi. (| = ajratuvchi chiziq)

X.-otasi: a1 | b1, c1, d1 X.-onasi: a2 | b2, c2, d2 X.-avlodlari: a1, b2, c2, d2 yoki a2, b1, c1, d1

X.-otasi: a1, b1 | c1, d1 X.-onasi: a2, b2 | c2, d2 X.-avlodlari: a1, b1, c2, d2 yoki a2, b2, c1, d1

X.-otasi: a1, b1, c1 | d1 X.-onasi: a2, b2, c2 | d2 X.-avlodi: a1, b1, c1, d2 yoki a2, b2, c2, d1

Ma'lumotni naslga etkazishning ko'p usullari mavjud va o'zaro kelishib olish bu ko'pchilikning biridir. Ajratuvchining joylashuvi butunlay o'zboshimchalik bilan bo'lishi mumkin, shuningdek, ota yoki onasi chiziqning chap tomonida bo'ladi.

Endi avlodlar bilan ham shunday qilaylik:

Х.-otasi: (13 | 5,7,3) Х.-otasi: (1 | 28,15,3) Х.-avlodi: (13,28,15,3)

Х.-otasi: (9,13 | 5,2) Х.-otasi: (14,9 | 2,4) Х.-otasi: (9,13,2,4)

Х.-otasi: (13,5,7 | 3) Х.-otasi: (9,13,5 | 2) Х.-otasi: (13,5,7,2)

Х.-otasi: (14 | 9,2,4) Х.-otasi: (9 | 13,5,2) Х.-otasi: (14,13,5,2)

Х.-otasi: (13,5 | 7, 3) Х.-otasi: (9,13 | 5, 2) Х.-otasi: (13,5,5,2)

Endi biz avlodlarning yashash darajalarini hisoblaymiz.

(13,28,15,3) — |126-30|=96(9,13,2,4) — |57-30|=27

(13,5,7,2) — |57-30|=22

(14,13,5,2) — |63-30|=33

(13,5,5,2) — |46-30|=16

Afsuski, naslning o'rtacha moslashuvchanligi 38,8, ota-onalar uchun bu koeffitsient 59,4 edi. Ayni paytda mutatsiyani qo'llash maqsadga muvofiqdir, buning uchun biz bir yoki bir nechta qiymatlarni tasodifiy raqam bilan 1 dan 30 gacha o'zgartiramiz.

Omon qolish darajasi nolga teng kelmasa, algoritm ishlaydi. I.e. tenglamaga yechim hisoblanadi. Aholisi ko'p bo'lgan tizimlar (masalan, 5 o'rniga 50 ta) kerakli darajaga (0) tez va barqaror o'tishadi.

Ushbu tenglama misollarni dasturda ko’ramiz

Bu erda 5 qiymat talab qiladi: 4 koeffitsient va natija. Yuqoridagi misol uchun u quyidagicha bo'ladi:

CDiofantine dp (1,2,3,4,30); // yaratilgan klass nomi

Keyin, tenglamani yechish uchun Solve () funktsiyasini chaqiramiz, bu eritma o'z ichiga olgan allelni qaytaradi. a, b, c, d qiymatlarini to'g'ri olish uchun GetGene () ni chaqiramiz. Ushbu klassdan foydalanadigan standart main.cpp protsedurasi quyidagicha bo'lishi mumkin:

#include ""

#include "diophantine.h"

void main() {

CDiophantine dp(1,2,3,4,30);

int ans; ans = dp.Solve();

if (ans == -1) {

cout << "No solution found." << endl;

} else

{

gene gn = dp.GetGene(ans);

cout << "The solution set to a+2b+3c+4d=30 is:\n";

cout << "a = " << gn.alleles[0] << "." << endl;

cout << "b = " << gn.alleles[1] << "." << endl;

cout << "c = " << gn.alleles[2] << "." << endl;

cout << "d = " << gn.alleles[3] << "." << endl; }

}

Endi Cdiofantine klassini ko’rib chiqamiz

#include

#include

#define MAXPOP 25

struct gene {

int alleles[4];

int fitness;

float likelihood;

// Test for equality.

operator==(gene gn) {

for (int i=0;i<4;i++) {

if (gn.alleles[i] != alleles[i]) return false;

}

return true;

}

};

class CDiophantine {

public:

CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d.

int Solve();// Solve the equation.

// Returns a given gene.

gene GetGene(int i) { return population[i];}

protected:

int ca,cb,cc,cd;// The coefficients.

int result;

gene population[MAXPOP];// Population.

int Fitness(gene &);// Fitness function.

void GenerateLikelihoods(); // Generate likelihoods.

float MultInv();// Creates the multiplicative inverse.

int CreateFitnesses();

void CreateNewPopulation();

int GetIndex(float val);

gene Breed(int p1, int p2);

};

CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {}

int CDiophantine::Solve() {

int fitness = -1;

// Generate initial population.

srand((unsigned)time(NULL));

for(int i=0;i

for (int j=0;j<4;j++) {// 0 and the result.

population[i].alleles[j] = rand() % (result + 1);

}

}

if (fitness = CreateFitnesses()) {

return fitness;

}

int iterations = 0;// Keep record of the iterations.

while (fitness != 0 || iterations < 50) {// Repeat until solution found, or over 50 iterations.

GenerateLikelihoods();// Create the likelihoods.

CreateNewPopulation();

if (fitness = CreateFitnesses()) {

return fitness;

}

iterations++;

}

return -1;

}

int CDiophantine::Fitness(gene &gn) {

int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3];

return gn.fitness = abs(total - result);

}

int CDiophantine::CreateFitnesses() {

float avgfit = 0;

int fitness = 0;

for(int i=0;i

fitness = Fitness(population[i]);

avgfit += fitness;

if (fitness == 0) {

return i;

}

}

return 0;

}

float CDiophantine::MultInv() {

float sum = 0;

for(int i=0;i

sum += 1/((float)population[i].fitness);

}

return sum;

}

void CDiophantine::GenerateLikelihoods() {

float multinv = MultInv();

float last = 0;

for(int i=0;i

population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100);

}

}

int CDiophantine::GetIndex(float val) {

float last = 0;

for(int i=0;i

if (last <= val && val <= population[i].likelihood) return i;

else last = population[i].likelihood;

}

return 4;

}

gene CDiophantine::Breed(int p1, int p2) {

int crossover = rand() % 3+1;// Create the crossover point (not first).

int first = rand() % 100;// Which parent comes first?

gene child = population[p1];// Child is all first parent initially.

int initial = 0, final = 3;// The crossover boundaries.

if (first < 50) initial = crossover; // If first parent first. start from crossover.

else final = crossover+1;// Else end at crossover.

for(int i=initial;i

child.alleles[i] = population[p2].alleles[i];

if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);

}

return child;// Return the kid...

}

void CDiophantine::CreateNewPopulation() {

gene temppop[MAXPOP];

for(int i=0;i

int parent1 = 0, parent2 = 0, iterations = 0;

while(parent1 == parent2 || population[parent1] == population[parent2]) {

parent1 = GetIndex((float)(rand() % 101));

parent2 = GetIndex((float)(rand() % 101));

if (++iterations > 25) break;

}

temppop[i] = Breed(parent1, parent2);// Create a child.

}

for(i=0;i

}

Topshiriqni bajarishda foydalanilgan manbalar ro’yxati:

1. https://habr.com/en/post/128704/

2. http://algolist.manual.ru/

3. https://en.wikipedia.org/wiki/Genetic_algorithm sfsa