VPF::макс путь в большом графе - Форум программистов

Stolzen

Дата 17.3.2011, 12:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Имеется очень большой граф, кол-во вершин около 10^6, кол-во ребер - 10^6, Ребер раза в 1,5 больше, чем вершин, причем некоторые вершины имеют достаточно большое кол-во ребер (10, 20). В графе есть циклы.

Для поиска макс. пути можно запускать поиск в ширину из каждой вершины и смотреть, улучшился ли макс путь на этой итерации. Но это происходит ОЧЕНЬ долго. (O(n * (n + m)) = O(2 * 10^12)). За ночь работы программы ответ так и не был найден.

Какие алгоритмы можно использовать для ускорения? Может быть, какие-нибудь эвристики, дающие достаточно хороший приближенный результат.

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Akina

Дата 17.3.2011, 12:43 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Гм... максимальный путь и циклы как-то не стыкуются... или ещё наложено требование однократности прохода? или двукратности?

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Stolzen

Дата 17.3.2011, 12:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Однократности прохода. Т.е. нужно найти максимальный простой путь в данном графе.

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Akina

Дата 17.3.2011, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Значит, надо идти по пути упрощения графа... поскольку

Цитата(Stolzen @ 17.3.2011, 13:10

)

Ребер раза в 1,5 больше, чем вершин

то возможно, что граф состоит из "облаков", соединённых только одним ребром? Или он всё-таки больше напоминает сферу?

--------------------

Stolzen

Дата 17.3.2011, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Возможно. Большинство вершин (около половины) кратности 1. А какие есть идеи? Найти мосты между этими "облаками" и далее уже искать наибольший путь в каждом таком кластере?
Но, в целом, хотелось бы узнать подходы для случайных графов - т.е. для "сфер".

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pavia

Дата 17.3.2011, 19:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12

Цитата(Stolzen @ 17.3.2011, 12:10

)

Но это происходит ОЧЕНЬ долго. (O(n * (n + m)) = O(2 * 10^12)). За ночь работы программы ответ так и не был найден.

Измени формат хранения, графа. Храни не как матрицу смежности. А как вершина массив смежных вершин(ссылки).
БУдет (O(n * (n + m)) = O(20 * 10^6)).
Рекурсия заменить циклом. А стек представь динамическим массивом.

Stolzen

Дата 17.3.2011, 21:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Хм.

У меня и сейчас O(n * (n + m)).
Рекурсию не использую - она не нужна для поиска в ширину.
Граф представлен списком смежности.

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pavia

Дата 17.3.2011, 21:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 418
Регистрация: 6.12.2008

Репутация: 11
Всего: 12

Stolzen,
Проверяйте код. Код в студию. Скорее всего где-то ошибка. Должно за несколько минут считаться.

Это сообщение отредактировал(а) Pavia - 17.3.2011, 21:39

Stolzen

Дата 18.3.2011, 12:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Цитата(Pavia @ 17.3.2011, 22:39

)

Должно за несколько минут считаться.

Задача NP-полная, поэтому за несколько минут при O(E) = 10^6 и O(V) = 10^6 точное решение не получить.

Но, тем не менее, вод код:

Код


#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#include <hash_map>

namespace std {
    using namespace __gnu_cxx;
}

using namespace std;

typedef unsigned int uint;

struct edge {
    uint id;
    uint to;
    uint data;
};

int main() {
    ifstream in;
    in.open("task.dat", ios::in | ios::binary);

    hash_map<uint, vector<uint> > vertices_map(2000000);

    do {
        edge n;
        in.read((char *)(&n), sizeof(edge));
        vertices_map[n.id].push_back(n.to);
    } while (!in.eof());

    in.close();

    uint n = vertices_map.size();
    cout << n << endl;

    hash_map<uint, uint> *max_path;
    max_path = new hash_map<uint, uint>(2 * n);
    uint max_path_len = 0, max_path_vertex_to, max_path_vertex_from, old_path_len;
    uint cnt = 0;

    hash_map<uint, vector<uint> >::iterator it = vertices_map.begin();
    for (; it != vertices_map.end(); ++it) {
        hash_map<uint, char> used(2 * n);
        hash_map<uint, uint> dist(2 * n), *path;
        path = new hash_map<uint, uint>(2 * n);

        uint v = it->first;

        queue<uint> q;
        q.push(v);
        dist[v] = 0;
        used[v] = true;

        old_path_len = max_path_len;

        while (!q.empty()) {
            uint from = q.front(); q.pop();
            vector<uint> *vertices = &(vertices_map[from]);

            for (uint i = 0; i < vertices->size(); ++i) {
                uint to = vertices->at(i);

                if (!used[to]) {
                    used[to] = true;
                    (*path)[to] = from;
                    q.push(to);
                    uint d = dist[from] + 1;

                    if (d > max_path_len) {
                        max_path_len = d;
                        max_path_vertex_to = to;
                    }

                    dist[to] = d;
                }
            }
        }

        if (max_path_len != old_path_len) {
            delete max_path;
            max_path_vertex_from = v;
            max_path = path;
        } else {
            delete path;
        }

        cnt++;
    }

    uint *edges = (uint *)malloc(max_path_len * sizeof(uint));
    n = max_path_len - 1;

    for (uint v = max_path_vertex_to; v != max_path_vertex_from; v = (*max_path)[v]) {
        edges[n--] = v;
    }

    edges[0] = max_path_vertex_from;

    ofstream out("out.dat");
    out.write((char *)(&max_path_len), sizeof(uint));
    out.write((char *)(edges), max_path_len * sizeof(uint));
    out.close();

    free(edges);

    cout << "done" << endl;

    return 0;
}

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Silent

Дата 18.3.2011, 16:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Stolzen, а вы уверены, что формулировка задачи и приведенный код говорят об одном и том же? у меня закралось сомнение, что нет - в формулировке говорится о "пути максимальной длины" (при наличии циклов), а в решение заключается в поиске пары вершин с максимальным кратчайшим расстоянием, что не одно и то же. Поправьте, если я неправ в понимании формулировки. Пример для иллюстрации:
user posted image

Максимальный путь - 1 2 3 4 5 (или 1 3 2 4 5), длина 4
Решение программы - 1 2 4 5 (или 1 3 4 5), длина 3

Как бы то ни было, но в приведенном коде я бы не стал так активно использовать STL (хотя и профессионально - читабельно и ясно), плюс обязательно распараллелил, раз алгоритмически улучшить не получится. черновой вариант:

Код


#pragma comment(linker, "/STACK:16777216")
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <omp.h>
#include <windows.h>
#include <iostream>
#include <conio.h>
using namespace std;

const int NMAX = 1000000;    //максимум миллион вершин
const int MMAX = 20;    //максимум 20 ребер из вершины

typedef unsigned int uint;
struct edge {
    uint id;
    uint to;
    uint data;    //не знаю зачем это поле, но раз надо - значит надо
};

uint a[NMAX+1][MMAX+1];    //NMAX+1 - нумерация вершин с 1
//MMAX+1 - для хранения в a[i][0] количества смежных вершин
int count = 0;
uint max_path_len[2], max_path_vertex_to[2], max_path_vertex_from[2], old_path_len[2];
uint max_path[2][NMAX];

uint q[NMAX];
bool ex[NMAX];
uint path[2][NMAX];
uint dist[NMAX];

void init()
{
    FILE * in = fopen("task.dat", "r");
    uint id, to, data;
    while (fscanf(in,"%d %d %d",&id, &to, &data) != EOF)
    {
        a[id][0]++;
        a[id][a[id][0]] = to;
        count = (count < id) ? id : count;
    };
    fclose(in);
}

void solve()
{
#pragma omp parallel sections private (q, ex, dist)
    {
#pragma omp section
        {
            for (int i = 1; i < count/2; i++)
            {
                //поиск в ширину из вершины i
                int head = 0, tail = 1;
                memset(ex,true,sizeof(ex));
                memset(path,0,sizeof(path));
                memset(dist,0,sizeof(dist));
                q[0] = i;
                ex[i] = false;
                old_path_len[0] = max_path_len[0];
                while (head < tail) {
                    uint from = q[head];
                    for (uint i = 1; i <= a[from][0]; i++) 
                    {
                        uint to = a[from][i];
                        if (ex[to]) {
                            ex[to] = false;
                            path[0][to] = from;
                            q[tail++] = to;
                            uint d = dist[from] + 1;
                            if (d > max_path_len[0]) {
                                max_path_len[0] = d;
                                max_path_vertex_to[0] = to;
                            }
                            dist[to] = d;
                        }
                    }
                    head++;
                }
                if (max_path_len[0] != old_path_len[0]) 
                {
                    max_path_vertex_from[0] = i;
                    memcpy(max_path[0], path[0], sizeof(path[0]));
                } 
            }
        }
#pragma omp section
        {
            for (int i = count/2; i <= count; i++)
            {
                //поиск в ширину из вершины i
                int head = 0, tail = 1;
                memset(ex,true,sizeof(ex));
                memset(path,0,sizeof(path));
                memset(dist,0,sizeof(dist));
                q[0] = i;
                ex[i] = false;
                old_path_len[1] = max_path_len[1];
                while (head < tail) {
                    uint from = q[head];
                    for (uint i = 1; i <= a[from][0]; i++) 
                    {
                        uint to = a[from][i];
                        if (ex[to]) {
                            ex[to] = false;
                            path[1][to] = from;
                            q[tail++] = to;
                            uint d = dist[from] + 1;
                            if (d > max_path_len[1]) {
                                max_path_len[1] = d;
                                max_path_vertex_to[1] = to;
                            }
                            dist[to] = d;
                        }
                    }
                    head++;
                }
                if (max_path_len[1] != old_path_len[1]) 
                {
                    max_path_vertex_from[1] = i;
                    memcpy(max_path[1], path[1], sizeof(path[1]));
                } 
            }

        }
    }
}

void out()
{
    FILE * out = fopen("out.dat","w");
    int index = 0;
    if (max_path_len[0] > max_path_len[1]) index = 0; else index = 1;
    fprintf(out,"%d\n", max_path_len[index]);
    for (uint v = max_path_vertex_to[index]; v != 0; v = max_path[index][v])
        fprintf(out,"%d ",v);
    fclose(out);
}

int main()
{
    int start = GetTickCount();
    cout << "start\n";

    init();
    cout << "data read: " << (GetTickCount()-start) << "ms\n";
    start = GetTickCount();

    solve();
    cout << "Total time: " << (GetTickCount()-start) << "ms\n";
    out();
    cout << "press any key";
    getch();
    return 0;
}

Для 10000 вершин со случайным количеством ребер (1-20) у меня работает 150с. Сколько работает Ваш код, засечь не получилось - элементарно не хватает толку откомпилировать ))

Stolzen

Дата 5.4.2011, 12:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: нет
Всего: 48

Хорошо, спасибо, посмотрю получше предложенный код.

А пробовали свой алгоритм для 10^6 вершин со случайным кол-вом ребер? 10^4 это все-таки не 10^6. И можно попробовать ваш файлик с вершинами?

STL активно используется из-за способа задания вершин - вместо порядкового номера каждой вершине присвоено 4 байта, поэтому и использую hash_map. (Которая, кстати, не STL, но входит в GNU C++)

Это сообщение отредактировал(а) Stolzen - 5.4.2011, 12:30

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »