Форум программистов, компьютерный форум CyberForum.ru

Поиск гамильтонова пути в орграфе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 5.00
e.b0sh
0 / 0 / 0
Регистрация: 27.11.2011
Сообщений: 5
28.11.2011, 22:08     Поиск гамильтонова пути в орграфе #1
Задача такая:
Дан ориентированный граф без циклов. Требуется проверить, существует ли в нем путь, прохо-
дящий по всем вершинам.
Первая строка входного файла содержит два целых числа n и m — количество вершин и дуг
графа соответственно. Следующие m строк содержат описания дуг по одной на строке. Ребро но-
мер i описывается двумя натуральными числами bi и ei — началом и концом дуги соответственно

Эту задачу нужно сдать в автоматическую систему проверки. Эта система прогоняет задачу по нескольким тестам и сверяет ответы. Если на каком-то тесте ответ неверный, то задача не принимается. Также там стоит ограничение по времени, т.е. если программа выполняется слишком долго, то задача не принимается.

Я решил эту задачу почти полным перебором, т.е. от каждой вершины графа запустил функцию, похожую на обход в глубину, но это оказалось слишком медленно. Затем я немного оптимизировал программу, запускал обход в глубину только от тех вершин, в которые нельзя попасть из других вершин (такая оптимизация работает, так как в графе нет циклов), но это всё равно оказалось слишком медленно Как можно еще оптимизировать алгоритм? Или, может, нужно использовать совершенно другой подход?

C++
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
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
const int N = 100001;
 
int n, m;
int count = 0;
vector<int> graph1[N]; // graph1[i] - список вершин, в которые можно попасть через вершину i
vector<int> graph2[N]; // graph2[i] - список вершин, из которых можно попасть в вершину i
 
bool dfs(int v)
{
    ++count;
    for (int i = 1; i < graph1[v].size(); ++i)
        dfs(graph1[v][i]);
    if (count == n)
        return true;
    else
    {
        --count;
        return false;
    }
}
 
bool hamiltonian()
{
    for (int i = 1; i <= n; ++i)
        if (graph2[i].size() == 1) // Если в вершину i нельзя попасть из любой другой вершины
            if (dfs(i))
                return true;
    return false;
}
 
int main()
{
    ifstream in("hamiltonian.in.txt");
    ofstream out("hamiltonian.out.txt");
 
    int i, u, v;
    in >> n >> m;
    for (i = 0; i <= n; ++i)
        graph1[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph1[u].push_back(v);
    }
 
    for (i = 0; i <= n; ++i)
        graph2[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph2[v].push_back(u);
    }
 
    if (hamiltonian())
        out << "YES";
    else
        out << "NO";
 
    in.close();
    out.close();
    return 0;
}
Добавлено через 5 часов 18 минут
Неужели никто не знает? Или я разделом ошибся? :\

Добавлено через 23 часа 4 минуты
upupup

Добавлено через 2 часа 36 минут
Моё улучшение было неверно реализовано и даже если его реализовать правильно, то всё равно слишком медленно...
Вопрос по-прежнему остается тем же: как улучшить мой код?
Упрощенный код по-сравнению с предыдущим:
C++
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
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
const int N = 100001;
enum COLOR {WHITE, BLACK};
 
int n, m;
int count = 0;
vector<int> graph[N]; // graph1[i] - список вершин, в которые можно попасть через вершину i
 
bool dfs(int v)
{
    ++count;
    for (unsigned i = 1; i < graph[v].size(); ++i)
        dfs(graph[v][i]);
    if (count == n)
        return true;
    else
    {
        --count;
        return false;
    }
}
 
bool hamiltonian()
{
    for (int i = 1; i <= n; ++i)
        if (dfs(i))
            return true;
    return false;
}
 
int main()
{
    ifstream in("hamiltonian.in.txt");
    ofstream out("hamiltonian.out.txt");
    int i, u, v;
    in >> n >> m;
    for (i = 0; i <= n; ++i)
        graph[i].push_back(i);
    for (i = 0; i < m; ++i)
    {
        in >> u >> v;
        graph[u].push_back(v);
    }
    if (hamiltonian())
        out << "YES";
    else
        out << "NO";
    in.close();
    out.close();
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2011, 22:08     Поиск гамильтонова пути в орграфе
Посмотрите здесь:

C++ Поиск пути
C++ Поиск пути в лабиринте
C++ Поиск пути
C++ Поиск оптимального пути в графе
Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней C++
Поиск пути C++
C++ поиск длины пути
C++ Поиск пути

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 07:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru