Вохӯрӣ дар миёна
Вохӯрӣ дар миёна
Муқаддима ба Meet in the Middle
Meet in the Middle як усули ҳаллу фасли масъалаҳо мебошад, ки вақте ҳалли мустақими brute-force хеле суст аст, истифода мешавад.
Идея ин аст, ки масъаларо ба ду қисм ҷудо кунем, ҳар қисмро ҷудогона ҳал кунем ва баъд натиҷаҳои қисмиро якҷо намоем.
Он махсусан муфид аст, вақте ки brute force тақрибан аст ва хеле калон аст (масалан, ).
Мафҳум
Идеяи асосӣ ин аст, ки як маҳдудиятро пайдо кунем, ки онро ба ду ним тақсим кардан мумкин аст.
Баъд аз он, мо ҳар ду нимро мустақилона ҳал мекунем ва аз натиҷаҳои қисмии онҳо барои сохтани ҷавоби ниҳоӣ истифода мебарем.
Ин аксар вақт тавозуни хуб байни brute force-и пурра ва алгоритмҳои пешрафтатар мебошад.
Масъалаи Subset Sum
Як мисоли классикии Meet in the Middle ин Subset Sum аст.
Баёни масъала
Бо дода шудани маҷмӯи адади бутун, ки ва суммаи ҳадаф , муайян кунед, ки оё зермаҷмӯае вуҷуд дорад, ки суммаи он маҳз бошад.