Оптимизации для задачи с наибольшим путем в циклическом графе - PullRequest
Новая
       52

Оптимизации для задачи с наибольшим путем в циклическом графе

13 голосов
/ 23 ноября 2010

Какие существуют способы оптимизации для поиска самого длинного пути в циклическом графе?

Самый длинный путь в циклических графах известен как NP-полный.Какая оптимизация или эвристика могут сделать поиск самого длинного пути быстрее, чем DFS для всего графа?Есть ли вероятностные подходы?

У меня есть график с определенными качествами, но я ищу ответ на этот вопрос в общем случае.Ссылка на документы была бы фантастической.Вот частичный ответ:

  1. Подтвердите, что это циклический.Самый длинный путь в ациклических графах легко вычисляется с помощью динамического программирования.

  2. Узнайте, является ли граф плоским (какой алгоритм лучше?).Если это так, вы можете увидеть, является ли это блок-графом, графом Птолемея или графиком кактусов, и применить методы, найденные в этой статье .

  3. Узнайте, какво многих простых циклах используется алгоритм Дональда Джонсона ( реализация Java ).Вы можете изменить любой циклический граф на ациклический, удалив ребро в простом цикле.Затем вы можете запустить решение для динамического программирования, найденное на странице Википедии .Для полноты вы должны будете сделать это N раз для каждого цикла, где N - длина цикла.Таким образом, для всего графа число раз, которое вы должны запустить решение DP, равно произведению длин всех циклов.

  4. Если вам нужно DFS для всего графикаВы можете сократить некоторые пути, предварительно рассчитав «достижимость» каждого узла.Эта достижимость, которая в основном применима к ориентированным графам, представляет собой количество узлов, которые каждый узел может достичь без повторений.Это максимальная длина самого длинного пути от этого узла.С этой информацией, если ваш текущий путь плюс достижимость дочернего узла меньше, чем самый длинный, который вы уже нашли, нет смысла брать эту ветку, так как невозможно найти более длинный путь.

1 Ответ

6 голосов
/ 24 ноября 2010

Вот подход O (n * 2 ^ n) динамического программирования, который должен быть выполнимым, скажем, до 20 вершин:

m(b, U) = максимальная длина любого пути, заканчивающегося на b и посещающего только (некоторые из) вершин в U.

Первоначально установите m(b, {b}) = 0.

Тогда m(b, U) = максимальное значение m(x, U - x) + d(x, b) для всех x в U, так что x не является b и существует ребро (x, b). Возьмите максимум этих значений для всех конечных точек b, с U = V (полный набор вершин). Это будет максимальная длина любого пути.

В следующем коде C предполагается матрица расстояний в d[N][N]. Если ваш график невзвешенный, вы можете изменить каждый доступ на чтение к этому массиву на константу 1. В массиве p[N][NBITS].

также вычисляется трассировка, показывающая оптимальную последовательность вершин (их может быть больше одной). 
#define N 20
#define NBITS (1 << N)

int d[N][N];       /* Assumed to be populated earlier.  -1 means "no edge". */
int m[N][NBITS];   /* DP matrix.  -2 means "unknown". */
int p[N][NBITS];   /* DP predecessor traceback matrix. */

/* Maximum distance for a path ending at vertex b, visiting only
   vertices in visited. */
int subsolve(int b, unsigned visited) {
    if (visited == (1 << b)) {
        /* A single vertex */
        p[b][visited] = -1;
        return 0;
    }

    if (m[b][visited] == -2) {
        /* Haven't solved this subproblem yet */
        int best = -1, bestPred = -1;
        unsigned i;
        for (i = 0; i < N; ++i) {
            if (i != b && ((visited >> i) & 1) && d[i][b] != -1) {
                int x = subsolve(i, visited & ~(1 << b));
                if (x != -1) {
                    x += d[i][b];
                    if (x > best) {
                        best = x;
                        bestPred = i;
                    }
                }
            }
        }

        m[b][visited] = best;
        p[b][visited] = bestPred;
    }

    return m[b][visited];
}

/* Maximum path length for d[][].
   n must be <= N.
   *last will contain the last vertex in the path; use p[][] to trace back. */
int solve(int n, int *last) {
    int b, i;
    int best = -1;

    /* Need to blank the DP and predecessor matrices */
    for (b = 0; b < N; ++b) {
        for (i = 0; i < NBITS; ++i) {
            m[b][i] = -2;
            p[b][i] = -2;
        }
    }

    for (b = 0; b < n; ++b) {
        int x = subsolve(b, (1 << n) - 1);
        if (x > best) {
            best = x;
            *last = b;
        }
    }

    return best;
}

На моем ПК это решает полный граф 20x20 с весами ребер, случайно выбранными в диапазоне [0, 1000), примерно за 7 с и требует около 160 Мб (половина этого для трассы предшественника).

(Пожалуйста, без комментариев по поводу использования массивов фиксированного размера. Используйте malloc() (или еще лучше, C ++ vector<int>) в реальной программе. Я просто написал это таким образом, чтобы все было яснее.)

...