Задача коммивояжёра с использованием динамического программирования || Коммивояжёр || DAA || Прое...

#sudhakaratchala #daavideos #dynamicprogramming Пусть G=(V,E) — ориентированный граф с n вершинами. где V — множество вершин, а E — множество рёбер. Рёбра заданы вместе с их стоимостью Cij, где Cij = 0 для всех i,j. cost(i,j) = 0, если (i==j) Cij, если (i,j) ≠ E(G) ꝏ, если (i,j) ≠ E(G) Тур для графа G — это ориентированный цикл, который включает каждую вершину ровно один раз. Тур начинается с вершины «1» и заканчивается вершиной «1», но оставшиеся вершины посещаются ровно один раз. Стоимость тура — это сумма стоимостей рёбер на этом пути. Пусть g(i,S) — длина минимального кратчайшего пути, начинающегося с вершины «i», проходящего через все вершины в «s» ровно один раз и заканчивающегося в вершине «i». g(i,S)=min{Cij + g(j, {S}-{j}} jϵS где S=V-{1} Если имеется n вершин, то может быть образовано (n-1)! циклов. Максимальное количество возможных ребер равно 2n. Цель задачи коммивояжера — найти кратчайший путь минимального размера/оптимальное решение.