Вохӯрӣ дар миёна

Вохӯрӣ дар миёна

Муқаддима ба Meet in the Middle

Meet in the Middle як усули ҳаллу фасли масъалаҳо мебошад, ки вақте ҳалли мустақими brute-force хеле суст аст, истифода мешавад.
Идея ин аст, ки масъаларо ба ду қисм ҷудо кунем, ҳар қисмро ҷудогона ҳал кунем ва баъд натиҷаҳои қисмиро якҷо намоем.

Он махсусан муфид аст, вақте ки brute force тақрибан $O(2^n)$ аст ва $n$ хеле калон аст (масалан, $n \approx 40$).

Мафҳум

Идеяи асосӣ ин аст, ки як маҳдудиятро пайдо кунем, ки онро ба ду ним тақсим кардан мумкин аст.
Баъд аз он, мо ҳар ду нимро мустақилона ҳал мекунем ва аз натиҷаҳои қисмии онҳо барои сохтани ҷавоби ниҳоӣ истифода мебарем.

Ин аксар вақт тавозуни хуб байни brute force-и пурра ва алгоритмҳои пешрафтатар мебошад.

Масъалаи Subset Sum

Як мисоли классикии Meet in the Middle ин Subset Sum аст.

Баёни масъала

Бо дода шудани маҷмӯи адади бутун, ки ва суммаи ҳадаф , муайян кунед, ки оё зермаҷмӯае вуҷуд дорад, ки суммаи он маҳз бошад.