Актуальность темы исследования. В инженерной практика больное количество прикладных задач распределенных САПР сводится к решению задач транспортного типа, которые позволяют получать оптимальные решения за короткое время работы алгоритма. Задачи транспортного типа чаще всего встречаются при исследовании разнообразных процессов на транспорте и системах связи. Эти задачи, так же, как и ряд оптимизационных задач, такие как задачи, о потоке минимальной стоимости, о компоновке, о выборе оптимального варианта системы обнаружения ошибок по критерию достоверности, задача оперативного обнаружения ошибок и другие, сводятся к решению задач об экстремальном пути и коммивояжера. Применение классических методов и алгоритмов решения данных задач с экспоненциальной временной сложностью становится неэффективным из-за большой размерности задачи, сложности преодоления локальных оптимумов, помимо того, эвристические методы большей частью не адаптированы к параллельным вычислительным системам. Большинство задач данного типа, являются NP-полными. Единственным способом получения оптимального решения для NP-полных задач является полный перебор всего множества решений.
