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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
#1

Эйлеров путь - C++

10.12.2013, 23:08. Просмотров 1350. Ответов 18
Метки нет (Все метки)

Я примерно написал програму, но мой вариант работает долго - 28(иногда меньше, иногда больше) минут.Подскажите пожалуйста есть ли какой-то более быстрый вариант. У меня есть только 5 минут каждый раз.
Мой заключается в следующем - берем одну из 10000 вершин ну и начинаем искать, подходит-добавили-опять ищем-нашли-добавали ну и если ничего не осталось то вывели.
Но работает долго.
К сожалению графы и алгоритмы на них еще не изучал - подскажите пожалуйста какой-либо алгоритм который будет быстрее. Можно не пример, а типа блок-схемы

Добавлено через 22 минуты
C другой стороны при использовании 3 i7 и 1 i3 расписав точки начала проверок как 0, 2500, 5000, 7500 можно конечно упеть за 3-4 минуты в среднем, но я верю что есть более цивилизованные пути решения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 23:08     Эйлеров путь
Посмотрите здесь:

Эйлеров цикл - C++
Есть программа: def euler_circuit(G): EP= # Эйлеров цикл - массив вершин. #возвращает локальный замкнутый цикл ...

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

Нужный путь - C++
Доброй ночи, форумчане! Я программист ранга начинающего. Подскажите пожалуйста, что можно закодить, чтобы зависнуть в проецировании кода на...

К-ый путь в графе(ДП) - C++
Здраствуйте! Прошу Вас помоч с задачной на ДП, думаю над ней достаточно долго, но ничего в голову путного не приходит. Вот условие: ...

путь к файлу - C++
String x,n,v; x=Form1->Memo2->Text; // имя файла n= Form1->Memo1->Text; // имя папки v=".txt"; // разрешение файла...

Путь к файлу - C++
Добрый день форумчане! Хотелось бы узнать, как указывать путь к файлу выше по каталогу. Например: *****---folder---****** ...

Критический путь - C++
помогите найти алгоритм критического пути.Обыскал весь инет ничего не нашол. З.Ы: Можно как-то переписать алгоримт Дейстры чтоб он искал...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
Эксперт C
15835 / 10162 / 1522
Регистрация: 24.12.2010
Сообщений: 19,159
10.12.2013, 23:11     Эйлеров путь #2
В качестве начальной и конечной вершины можно рассматривать только вершины нечетных степеней. Их должно быть ровно 2, иначе эйлерова пути (не замкнутого) нет.
Если все вершины имеют четную степень, то имеется (обязательно!) эйлеров цикл (замкнутый путь). И тогда без разницы с какой из вершин начинать..
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
10.12.2013, 23:20  [ТС]     Эйлеров путь #3
Тут, к сожалению, не так я задал вопрос.
Те изначально известно что нечетных вершин 2 - не ноль - то есть не цикл, а именно путь - но на входе у меня 10000 строк и как определить нечетную я не пойму, хотя пока пишу это уже пару идей пришло.
Спасибо
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 09:47     Эйлеров путь #4
Цитата Сообщение от Aliru Посмотреть сообщение
28(иногда меньше, иногда больше) минут
жесть!
сие творение ищет эйлеров путь за N*logN (можно избавиться от логарифма если set заменить на что-нибудь на хешах, например unordered_map):
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
#include <cstdio>
#include <set>
#include <stack>
using namespace std;
 
const int N = 10001;
 
set< int > adj[ N ]; // граф на списках смежности
stack< int > st;
 
void insert_edge( int v, int w )
{
    adj[ v ].insert( w );
    adj[ w ].insert( v );
}
 
void remove_edge( int v, int w )
{
    adj[ v ].erase( w );
    adj[ w ].erase( v );
}
 
int traverse( int v )
{
    for ( set< int >::iterator it; ( it = adj[ v ].begin() ) != adj[ v ].end(); v = *it )
    {
        st.push( v );
        remove_edge( v, *it );
    }
    return v;
}
 
void print_euler( int v )
{
    st.push( v = traverse( v ) );
    while ( !st.empty() )
    {
        printf( "%d ", v = st.top() ); st.pop();
        traverse( v );
    }
}
 
int find_odd_degree()
{
    for ( int v = 0; v < N; ++v )
        if ( adj[ v ].size() & 0x01 )
            return v;
    return -1;
}
 
int main()
{
    for ( int v, w; 1 < scanf( "%d%d", &v, &w ); insert_edge( v, w ) );
    print_euler( find_odd_degree() );
 
    return 0;
}
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:05  [ТС]     Эйлеров путь #5
Сейчас я дописал поиск нечетной вершины.
На входе у меня 260-280Кб строк
такого типа(на самом деле они по-моему по 25 или 30 символов но это не важно)
ATGCG
GCATG
CATGC
AGGCA
GGCAT
Ответ типа такой(отсортирован по алфавиту)
AGGCA -> GGCAT
CATGC -> ATGCG
GCATG -> CATGC
GGCAT -> GCATG
Все одинаковой длины.
Нечетное ребро - это когда первые (размер() -1) символов не повторяются нигде. Четное - когда у одной строки это начало,а у другой конец.
Вот код
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// OGP2.0.cpp : Defines the entry point for the console application.
//
 
// Overlap Graph Problem.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include "conio.h"
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <algorithm>
#include <iterator>
#include "vector"
 
using namespace std;
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    list<string> Lines;
    list<string>::iterator it;
    vector <string> lines;
    string s1, s2, example;
    ifstream Fin;
    Fin.open("d:\\dataset_52_7.txt");
    if (!Fin.is_open())
    {
        cout << "Can't open file-d:\\dataset_52_7.txt" << endl;
        exit(EXIT_FAILURE);
    }
    while (Fin.good())
    {
      getline(Fin, s1);
      Lines.push_back(s1);
      s1.clear();
    }
    if (Fin.eof())
        cout << "EOF" << endl;
    else 
        if (Fin.fail())
        cout << "Fuck a duck, HAX!!!" << endl;
    else
        cout << "!!!---!!!" << endl;
    Fin.close();
    //End of input
 
    
    //Lines.sort();
    for ( it = Lines.begin(); it != Lines.end(); it++)
        lines.push_back(*it);
    //sort & send dna to the vector
 
    int count = 0;
    for (int i = 0; i < lines.size(); i++)
    {
        s1 = lines.at(i);
        s1.erase(s1.begin() + s1.size() - 1);
        for (count = 0; count < lines.size(); count++)
        {
            example = lines.at(count);
            example.erase(example.begin());
            if (i != count)
            {
                if (s1 == example)
                    break;
            }
        }
        if (count == lines.size())
        {
            s1 = lines.at(i);
            break;
        }
    }
    //cout << s1;
    ofstream f_out("d:\\Result.txt", ios::app);
        if (!f_out) 
            {
                cout<<"Файл Result.txt невозможно открыть";
                exit(EXIT_FAILURE);
            }
        f_out << s1;
    while (lines.size() != 0)
    {
        example = s1;
        example.erase(example.begin());
        for (unsigned int i = 1; i < lines.size(); i++)
        {
            for (unsigned int j = 0; j < (s1.size() - 1); j++)
            {
                if (example.at(j) == lines.at(i).at(j))
                {
                    count++;
                }
            }
            if (count == example.size())
            {
                //f_out << s1 << " -> " << lines.at(i) << endl;
                //cout << s1 << " -> " << lines.at(i) << endl;
                s1.clear();
                s1 = lines.at(i);
                lines.erase(lines.begin() + i);
                break;
            }
            count = 0;
        }
        cout << lines.size();
        example.clear();
    }
    f_out.close();
    _getch();
    return 0;
}
Доходит до 4500 и потом не находит продолжения.
В чем может быть проблема?
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:10     Эйлеров путь #6
Цитата Сообщение от Aliru Посмотреть сообщение
ATGCG
GCATG
CATGC
AGGCA
GGCAT
можете поведать смысл этих строк
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:10  [ТС]     Эйлеров путь #7
Ну это ДНК, вернее ее куски нарезанные по н штук
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:18     Эйлеров путь #8
а как из этих строк строится граф? что является узлом? буквы или что? и как определяются ребра? соседние буквы образуют ребро или что? можете поподробнее объяснить
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:34  [ТС]     Эйлеров путь #9
Пусть длина строки н
(н-1) последних символов одной сторки это (н-1) первых символов другой строки.
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина. Есть еще одна но у нее последнии н-1 символов не повторяются.
2 нееных вершины - значит это эйлеров путь
И так мы выстраиваем этот путь - ну типа
AACACTT->ACACTTG
CACTTGT->ACTTGTA
CTTGTAA->TTGTAAG
Ну вот так

Добавлено через 6 минут
Извиняюсь точнее так
AACACTT->ACACTTG
ACACTTG->CACTTGT
CACTTGT->ACTTGTA
ACTTGTA->CTTGTAA
CTTGTAA->TTGTAAG
Исправил
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 11:35     Эйлеров путь #10
я вас правильно понял: вам надо по кускам восстановить полную цепочку? и
Цитата Сообщение от Aliru Посмотреть сообщение
Я там нашел строку и потом проверил ее у которой начальные н-1 символов не повторяются нигде кроме нее самой - значит это нечетная вершина.
нечетная - значит начальная, а это
Цитата Сообщение от Aliru Посмотреть сообщение
Есть еще одна но у нее последнии н-1 символов не повторяются.
значит конечная вершина?
если так, то при чём здесь эйлеров путь, никак не уловлю?
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 11:38  [ТС]     Эйлеров путь #11
да, но я думал это граф. я их еще не учил, но...
а о чем тогда задача, натолкнте на алгоритм пожалуйста
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:29     Эйлеров путь #12
продолжаем разговор
Цитата Сообщение от ya_noob Посмотреть сообщение
я вас правильно понял: вам надо по кускам восстановить полную цепочку?
я не услышал ответа. да или нет?
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 12:32  [ТС]     Эйлеров путь #13
Да.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.12.2013, 12:48     Эйлеров путь #14
хорошо. мне сложно запомнить ATGC, так что давайте далее будем говорить про ABCD.
итак, может ли во входных данных встретиться такое

AABC
ABCD
BCDD
CDDB
ABCD
BCDB
CDBA
DBAB
BABC
? попробуйте нарисовать эту цепочку
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 17:58     Эйлеров путь
Еще ссылки по теме:

Путь к файлу - C++
Всем привет) помогите как считать строки с файла, вроде все работает но файл не находит, как правильно указать путь? #include...

Путь к файлу - C++
Как сделать чтоб пользователь указывал путь к файлу который используеться дл читения?

Путь к процессам - C++
Нашел вот такой код#include &lt;windows.h&gt; #include &lt;Psapi.h&gt; int main(){ int pid = 3432; // PID of notepad.exe char...

Длинный путь - C++
Имеется n городов пронумерованных от 1 до n и m соединяющих дорог. Расстояния между любыми двумя городами равны 1. Найти длину пути между...

Путь символа - C++
Здорова господа! Есть интересная задачка: &quot;Проследите путь символа в вашей системе от клавиатуры до экрана на примере следующего...


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

Или воспользуйтесь поиском по форуму:
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
11.12.2013, 17:58  [ТС]     Эйлеров путь #15
ТУТ есть AABC->ABCD->BCDD->CDDB и ABCD->BCDB->CDBA->DBAB->BABC
а у меня будет типа
Вход:
BCDD
DDBB
BBAB
DBBA
CDDB
AABC
ADCD
Выход
AABC->ABCD->BCDD->CDDB->DDBB->DBBA->BBAB
то есть AABC это начало так как комбинация AAB больше нигде не встеекается как последние 3 символа(н-1),
а вот ВСD - это начало BCDD И конец ABCD
я вот опять день думал периодически впринципе то мой код должен работать - но он доходит до 6311 отрезков и больше не находит
Yandex
Объявления
11.12.2013, 17:58     Эйлеров путь
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru