Визначено оцінки обчислювальної складності локального алгоритму (ЛА) під час розв'язання двоблочних та двоквазіблочних задач дискретного програмування (ДП) з додатковими обмеженнями багаторазового вибору. Досліджено класи задач дискретного програмування з блочною структурою, що ефективно розв'язуються шляхом ЛА, типову поведінку ЛА на різних класах блочних задач на підставі аналізу асимптотичних середніх. Доведено, що ЛА є досить ефективним, порівняно з існуючими алгоритмами ДП, алгоритмом з квазіекспоненційною оцінкою обчислювальної складності. Визначено блочні та квазіблочні структури, що відповідають найкращому та найгіршому застосуванню ЛА.

  Завантажити