O‘rtada uchrashish

O‘rtada uchrashish

Meet in the Middle ga kirish

Meet in the Middle — to‘g‘ridan-to‘g‘ri brute-force yechim juda sekin bo‘lganda qo‘llaniladigan muammo yechish texnikasi.
G‘oya shundan iboratki, muammoni ikki qismga bo‘lib, har bir qismini alohida yechamiz va so‘ng qisman natijalarni birlashtiramiz.

U ayniqsa brute force taxminan $O(2^n)$ bo‘lganda va $n$ juda katta bo‘lsa (masalan, $n \approx 40$) foydali.

Konseptsiya

Asosiy g‘oya — ikki yarmga bo‘lish mumkin bo‘lgan cheklovni topish.
Shundan so‘ng, ikkala yarmini mustaqil yechamiz va yakuniy javobni qurish uchun ularning qisman natijalaridan foydalanamiz.

Bu ko‘pincha to‘liq brute force va yanada ilg‘or algoritmlar o‘rtasidagi yaxshi muvozanatdir.

Subset Sum muammosi

Meet in the Middle ning klassik misoli — Subset Sum.

Masala bayoni

$$ bo‘lgan ta butun sonlar to‘plami va maqsadli yig‘indi berilgan. Yig‘indisi aynan ga teng bo‘lgan biror subset mavjud yoki yo‘qligini aniqlang.