Неточность алгоритма ветвей и границ

Аннотация

Подшивалов С. Ф., Подшивалова К. С., Токарева Л. В., Комолова Н. В.

Дата поступления статьи: 10.05.2018

Целью работы является проверка точности решения задачи коммивояжера методом ветвей и границ (ВиГ) при большой разнице в длине хорд транспортного графа. Она считается NP–трудной задачей. Доказано, что метод ВиГ может не давать оптимального результата в транспортном графе с большой разницей величин элементов в ячейках исходной матрице, когда нулевые ее ячейки будут иметь сильно отличающиеся друг от друга оценки. Причиной неточности решения задачи коммивояжера является неадекватность принятой модели расчета исходной постановки задачи. Она заключается в несправедливость второй гипотезы по оценке нулевого элемента в оценочной матрице, включаемого в оптимальный маршрут. Гипотеза принята без строгих доказательств и носит вероятностный характер. Предложена методика усовершенствования метода ветвей и границ, которая заключается в дополнительной проверке полученного оптимального маршрута путем удаления ветви с оценкой на одну ступень ниже максимальной на каждом этапе ветвления.

Ключевые слова: коммивояжер, оптимальный маршрут, метод ветвей и границ, недостатки, гипотезы, алгоритм, неточность решения, причины, численный эксперимент, усовершенствование.

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

`