Hardprob/Minimum Traveling Repairman — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Граф <m>G=\left(V,E\right)</m>, стартовая вершина <m>r\in V</m>, длины на ребрах <m>∀e\in E, l(e)\in N</m>, у…») |
(нет различий)
|
Версия 22:12, 8 апреля 2023
- Граф , стартовая вершина , длины на ребрах , удовлетворяющие неравенству треугольника.
- Найти обход, стартующий в r, обходящий все вершины в G, т.е. перестановка , такая что $\pi(1)=r$" width="63" height="31" border="0" align="MIDDLE">.
- Минимизировать , где — полное расстояние пройденное в этом пути от стартовой вершины, до вершины v.
Задача в лаб22 (рид-онли просмотр)