Построение кратчайшего вершинно непересекающегося пути, проходящего через обязательные вершины
Сегодня мы разберём мою бакалавровскую дипломную работу о построении кратчайшего вершинно несамопересекающегося пути, проходящего через обязательные вершины (задача NP‑трудна).Текст диплома довольно сложный, поэтому я постараюсь изложить его попроще и уберу доказательства вспомогательных утверждений.Давайте же пройдём путь от рассмотрения ограничений задачи и её полиномиальных аналогов до ускоренного переборного алгоритма, который добьём метаэвристиками. Читать далее