Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу
Пояснение к решению
Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).
Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).
Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».
Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.
Решение на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <stdio.h> #include <vector> #include <stdlib.h> using namespace std; struct Graph { vector< vector<int> > AdjList; int Size; Graph(int n) { vector<int> List; for (int k = 0; k < n; k++) AdjList.push_back(List); Size = n; } void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин Size++; vector<int> List; AdjList.push_back(List); } void add_edge(int u, int v) { // u и v уже должны быть в списке вершин AdjList[u].push_back(v); } int simple_paths(int start, int end, int max_depth) { bool* on_path = (bool*) calloc(Size, sizeof(bool)); int cur_depth = 0; int count = 0; simple_paths(start, end, on_path, cur_depth, max_depth, count); return count; } void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) { if (cur_depth <= max_depth) { on_path[start] = true; if (start == end) count++; else for (int k = 0; k < AdjList[start].size(); k++) { int v = AdjList[start][k]; if (!on_path[v]) { cur_depth++; simple_paths(v, end, on_path, cur_depth, max_depth, count); on_path[v] = false; cur_depth--; } } } } }; int main() { int n, k, a, b, d, tmp1, tmp2; scanf("%d %d %d %d %d", &n, &k, &a, &b, &d); Graph G(n); for (int i = 0; i < k; i++) { scanf("%d %d", &tmp1, &tmp2); G.add_edge(tmp1 - 1, tmp2 - 1); } printf("%d\n", G.simple_paths(a-1, b-1, d)); return 0; } |
Решение на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
import java.util.*; import java.lang.*; import java.io.*; class myInt { int v; public myInt(int a) { this.v = a; } } class Graph { Vector<Vector<Integer>> AdjList; public Graph(int n) { AdjList = new Vector<Vector<Integer>>(n); for (int k = 0; k < n; k++) AdjList.add(new Vector<Integer>()); } public void add_vertex() { AdjList.add(new Vector<Integer>()); } public void add_edge(int u, int v) { AdjList.elementAt(u).add(v); } public int simple_paths(int start, int end, int max_depth) { boolean[] on_path = new boolean[AdjList.size()]; myInt cur_depth = new myInt(0); myInt count = new myInt(0); simple_paths(start, end, on_path, cur_depth, max_depth, count); return count.v; } public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) { if (cur_depth.v <= max_depth) { on_path[start] = true; if (start == end) count.v++; else for (int k = 0; k < AdjList.elementAt(start).size(); k++) { int v = AdjList.elementAt(start).elementAt(k); if (!on_path[v]) { cur_depth.v++; simple_paths(v, end, on_path, cur_depth, max_depth, count); on_path[v] = false; cur_depth.v--; } } } } } class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(), k = in.nextInt(); int a = in.nextInt(), b = in.nextInt(), d = in.nextInt(); int tmp1, tmp2; Graph G = new Graph(n); for (int i = 0; i < k; i++) { tmp1 = in.nextInt(); tmp2 = in.nextInt(); G.add_edge(tmp1 - 1, tmp2 - 1); } System.out.println(G.simple_paths(a-1, b-1, d)); } } |
Молодец! Зачтено.