Недавно передо мной встала задача — найти цикл минимального веса в взвешенном графе на 20 вершин и 100 ребер. Используя обычный dfs-подход(смотрим исходящие рёбра из текущей вершины, рекурсивно запускаемся от детей), и оптимизацию, что если текущий путь больше минимального найденного, то продолжать нет смысла, я получил TL Прошу вашего совета — какие ещё оптимизации тут можно применить?
Добавить к перебору меморизацию
Что тут можно запоминать, кроме того что я упомянул?
результаты для подмножеств. в любой момент в дфсе вершины делятся на использованные и нет. использованные образуют подмножество.
dp[v][msk] — путь минимального веса из вершины 0 в вершину v используя вершины из msk.
Советую почитать про ДП по подмножествам. Задачи, где n примерно равно 20, часто именно так и решаются. Например, здесь.
Чуть чуть дольше, чем нужно Может какие-то эвристики применить, чтобы ответ находился с большой вероятностью?
Вроде бы цикл минимального веса решается за O(M^2 log M) путем перебора удаляемого ребра и запуска Дейкстры
Тут это не пройдёт, нужен гамильтонов цикл, это NP-полная задача