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

Давайте же пройдём путь от рассмотрения ограничений задачи и её полиномиальных аналогов до ускоренного переборного алгоритма, который добьём метаэвристиками.