Mavzu-11: “DAǴal kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala

MAVZU-11: “DAǴAL KUCH” USULI BILAN TARTIBLASHTIRISH. KOMMIVOYAJER HAQIDA MASALA.

Reja:

1. 
   Dag’al kuch usuli
   
2. 
   Kommivoyajer masalasi
   

Dag’al kuch usuli

• 
  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.
  
• 
  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) D_ji = D_ij.
  
• 
  Assimmetrik kommivoyajer masalasi  (ATSP) D_ji ≠ D_ij.
  
• 
  Qisman tartiblash masalasi  (SOP = sequential ordering problem)
  
• 
  Гамильтон siklini izlash (HCP = нamiltonian cycle problem) -
  

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; i

• 
  a[i]=i+1;
  
• 
  }
  
• 
  permute(a, 0, n-1);
  
• 
  return 0;
  
• 
  }00
  

misol
satrlar bo’yicha ayirish

Ustunlar bo’yicha ayirish

d = 44 + 3 = 47
Ixtiyoriy yechimning quyi chegarasi (narxning)

i-j qirrani o’chirish

masalan, 3-5

Matritsa ustida bajariladigan amal :

1. 
   i-satr va j- ustun o’chirib tashlanadi (matritsa o’lchami 1 ga kamayadi)
   
2. 
   cheklov (j, i): C_ji := +
   

3) Matritsani qayta qurish jarayoni

	1	2	3	4	5
1		0	15	3	2
2	0		12	22	20
3	18	14		2	0
4	3	44	18		0
5	15	1	0	0	

• 
  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; i

• 
  a[i]=i+1;
  
• 
  }
  
• 
  permute(a, 0, n-1);
  
• 
  return 0;
  
• 
  }00