Dag’al kuch usuli Kommivoyajer masalasi Kalit so’zlar: Dag’al kuch usuli метод «грубой силы»



Download 1,07 Mb.
Sana13.06.2022
Hajmi1,07 Mb.
#662921
Bog'liq
10-m


10-ma’ruza
Mavzu: “Dag’al kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala.
Reja:

  1. Dag’al kuch usuli

  2. Kommivoyajer masalasi

Kalit so’zlar: Dag’al kuch usuli ( метод «грубой силы», brute force), matritsalarni ko’paytirish, ketma-ket qidiruv, kommivoyajer masalasi.
Dag’al kuch usuli ( метод «грубой силы», англ. brute force) — matematik masalalarni yechish usulidir.
Bu usulda mavjud bo’lgan barcha variantlar ko’rib chiqiladi.
Dag’al kuch usuli xususiyatlari

  • Dag’al kuch usuli deyarli barcha turdagi masalalarga tadbiq qilish mumkin;

  • Ko’pincha tadbiq qilish eng oson;

  • Kam hollarda chiroyli va samarali algoritmlarni beradi;

  • O’lchami uncha katta bo’lmagan masalalarni yechishda foydali;

  • Boshqa algoritmlarning samaradorligini aniqlash uchun o’lchov vazifasini bajaradi.

Masalan: tanlab saralash yoki pufakcha usulida saralash

Dag’al kuch usuliga asoslangan algoritmlar:

  • Matritsalarni ko’paytirish;

  • Ketma-ket qidiruv (Ro’yhatdagi eng kichik va eng katta elementni topish);

  • Tanlab saralash;

  • Pufakcha usulida saralash;

  • Satrdan qism satrni qidirish;

  • Tekislikda eng yaqin joylashgan nuqtalar juftligini topish.

Kommivoyajer masalasi
Shaharlar to’plami va ular orasidagi sayohat narxi (masofasi) berilgan.
Shunday tartibni aniqlash kerakki, sayohatchi hamma shaharlarga tashrif buyurib, dastlabki shaharga qaytib kelganda, sayohatning umumiy narxi (masofasi) minimal bo’lsin.

Kommivoyajer masalasi

  • Masalaning bir nechta variantlari mavjud :

  • Simmetrik kommivoyajer masalasi  (TSP = traveling salesman problem) Dji = Dij.

  • Assimmetrik kommivoyajer masalasi  (ATSP) Dji ≠ Dij.

  • Qisman tartiblash masalasi  (SOP = sequential ordering problem)

  • Гамильтон siklini izlash (HCP = нamiltonian cycle problem) -

Yechish usullari
1. Aniq usullar - Aniq usullar nafaqat biron bir yechimni topibgina qolmay, balki natijaning eng yaxshi yechim ekanligini isbotlaydi.
Shaharlar orasidagi masofalarni matritsa shaklida yozamiz (pastdagi jadval). Masalan, 2-shahardan 3-shahargacha (va 3 dan 2 gacha) masofa 7. Grafik yo'naltirilmaganligi sababli, bu matritsa simmetrikdir. Chiziqlar shahardan unga "taqiqlangan" o'tishlarni belgilaydi.

har qanday shahar boshlang'ich (va tugaydigan) sifatida tanlanishi mumkin. bu nol shahar bo'lsin. keyin nollar bilan o'ralgan 1 dan 4 gacha bo'lgan raqamlarning har qanday almashinuvi har bir shaharni bir marta bosib o'tadigan yo'lni anglatadi. masalan, 0,1,3,2,4,0 demak, 0 shahridan boshlab 1-shaharga, keyin 3-shaharga va h.k.
Shaharlar ro’yxati raqamlarini kombinatsiya qilish dasturi
void permute(int a[], int l, int r)
{
if (l == r){
for(int i=0; i<=r; i++){
cout<<*(a+i)<<" ";
}
cout<}
else
{
for (int i = l; i <= r; i++)
{
swap(*(a+l), *(a+i));
permute(a, l+1, r);
swap(*(a+l), *(a+i));
}
}
}
int main()
{
int a[20];
int n;
cout<<"Massiv elementlar sonini kiriting"<cin>>n;
for(int i=0; ia[i]=i+1;
}
permute(a, 0, n-1);
return 0;
}
Shaharlar ro’yxati raqamlarini kombinatsiya qilish

Mavzu yuzasidan savollar

  1. dag’al” kuch usuli nima?

  2. Dag’al” kuch metodi bilan qaysi masalalarni yechish mumkin.

  3. Dag’al” kuch metodi qanday holatlard qo’llaniladi?

Kommivoyajer masalasi haqida ma’lumot bering
Download 1,07 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish