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

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

Войти
Регистрация
Восстановить пароль
 
JJJJ
0 / 0 / 1
Регистрация: 17.12.2013
Сообщений: 11
#1

Найти вероятность существования пути в графе между заданными точками - C++

24.03.2014, 19:12. Просмотров 649. Ответов 1
Метки нет (Все метки)

Запутался в рекурсии. Смысл задачи: найти вероятность существования пути в графе между заданными точками. Смысл функции gen() на данном этапе: генерирование всех возможных матриц смежности и проверка есть путь или нет с помощью функции poisk().
Алгоритм: из матрицы смежности графа последовательно берем ребро и рекурсивно строим матрицы с существованием ребра и несуществованием ребра.
Все функции работают правильно кроме функции gen() - она выводит повторяющиеся матрицы, что в принципе по алгоритму быть не должно.
Кому не лень посмотрите код и покидайте идеи - у меня они кончились) Заранее благодарю

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
116
117
118
119
120
121
122
123
#include <iostream>
#include <vector>
#include <fstream>
#define M 4
#define P 0.1
 
using namespace std;
int graph[M][M]={
    {0,1,1,1},
    {1,0,0,0},
    {1,0,0,1},
    {1,0,1,0}
};
bool matrix[M][M]={0};
 
int count_paths(){
    int elements=0;
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            if(graph[i][j])
                elements++;
    return elements/2;
}
 
vector<int>get_nodes(int node, int g[M][M]){
    vector<int> nodes;
    int j=0;
    for(int i=node;j<M;j++)
    {
        if(g[i][j])
            nodes.push_back(j);
    }
    return nodes;
}
 
float result=0;
void res(int path_size,int etc){
    result+=pow(P,path_size)*pow((1-P),etc);    
}
 
bool is_element(vector<int> nodes,int element){
    for(vector<int>::iterator it=nodes.begin(); it != nodes.end(); ++it)
    {
        if(*it==element)
            return true;
    }
    return false;
}
 
vector<int> used;
bool poisk(int from, int to, int g[M][M]){//, vector<int>&path){
    if(from==to)
    {
        used.erase(used.begin(),used.end());
        return 1;
    }
    else{
        vector<int> nodes=get_nodes(from,g);//все смежные вершины нужной вершины
        used.push_back(from);
        for(vector<int>::iterator it=nodes.begin(); it != nodes.end(); ++it)
        {
            if(is_element(nodes,*it) && !is_element(used,*it))
            {
                if(poisk(*it,to,g))//,path))
                    return 1;
            }
        }
    }
    return 0;
}
 
void clear(){
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            matrix[i][j]=0;
}
ofstream ofs ("test.txt", std::ofstream::out);
void show(int g[M][M]){
    for(int i = 0 ; i < M; i++){
        for(int j = 0;j < M; j++)
            cout<<g[i][j];
        cout<<endl;
    }
    cout<<endl;
}
int cp=0;
 
void gen(int X, int Y, int from, int to, int g[M][M]){
    for(int i = X ; i < M; i++)
        for(int j = Y;j < M; j++){
            if(g[i][j] == 1 && j>i)//мы идем по ребрам графа
            {
                g[i][j] = 0;
                if(poisk(from,to,g))
                    cp++;
                else{}
                show(g);
                if(j+1<M && i<M)
                    gen(i,j+1,from,to,g);//считаем если ребра нет
                else if(i+1<M && j>=M){
                    gen(i+1,0,from,to,g);//считаем если ребра нет
                }
 
                g[i][j] = 1;
                if(j+1<M && i<M)
                    gen(i,j+1,from,to,g);//считаем если ребро есть
                else if(i+1<M && j>=M){
                    gen(i+1,0,from,to,g);//считаем если ребро есть
                }
 
            }
        }
}
 
int main(){
    int copy[M][M];
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            copy[i][j] = graph[i][j];
    gen(0,0,0,3,copy);
    ofs.close();
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2014, 19:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти вероятность существования пути в графе между заданными точками (C++):

Найти кратчайшие пути между двумя заданными точками графа - C++
Добрый вечер. Кто сможет написать программу для задачи, буду очень признателен 4) Найти кратчайшие пути из точки D1 в точку D8 Вот...

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

Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей - C++
Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей. ПОМОГИТЕЕЕЕ если кто напишет код...

Вычислить расстояние между двумя точками с заданными координатами - C++
Вычислить расстояние между двумя точками с заданными координатами:A(a,d),B(u,m).

Вычисление расстояния между двумя точками, заданными на плоскости их координатами - C++
Составить программу вычисления расстояния между двумя точками, заданными на плоскости их координатами.

Определить процедуру вычисления расстояния между двумя точками, заданными своими координатами - C++
помогите пожалуйста написать программы в с++ Даны действительные числа х1, у1, х2, у2, …,х10, у10. Найти периметр десятиугольника,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
JJJJ
0 / 0 / 1
Регистрация: 17.12.2013
Сообщений: 11
25.03.2014, 19:41  [ТС] #2
Если кому-то было интересно, я нашел ответ:
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
void gen(int X, int Y, int from, int to, int g[M][M]){
    bool f1 = true;
    for(int i = X ; i < M; i++){
        for(int j = Y;j < M; j++){
            if(g[i][j] == 1 && j>i && f1)//мы идем по ребрам графа
            {
                f1=false;
                g[i][j] = 0;
                if(poisk(from,to,g)){//главный подсчет
                    probab_way += probabulity(g);
                    cp++;
                }
                bool flag1 = true, flag2 = true;
                if(j+1<M && i<M){
                    flag1=false;
                    gen(i,j+1,from,to,g);//считаем если ребра нет
                }
                else if(i+1<M  && flag1){
                    gen(i+1,0,from,to,g);//считаем если ребра нет
                }
                g[i][j] = 1;
                if(j+1<M && i<M){
                    gen(i,j+1,from,to,g);//считаем если ребро есть
                    flag2 = false;
                }
                else if(i+1<M && flag2){
                    gen(i+1,0,from,to,g);//считаем если ребро есть
                }
            }
        }
    }
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2014, 19:41
Привет! Вот еще темы с ответами:

Найти максимальное и минимальное значение между точками и вывести их вместе с точками - C++
Я уже весь гугл перерыл и всю голову выпотрошил.не получается. Нужно написать функцию для двух массивов х и у. Эти массивы задают...

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Написать программу для нахождения кратчайшего пути между заданными вершинами графа - C++
visual studio windows forms нужна программа,которая будет вычислять кратчайший путь от вершины a до вершины b в графе, граф задается...

Найти самый используемый отрезок пути в графе - C++
Доброго времени суток. Столкнулся с такой проблемой: в графе нужно найти участок, который используется чаще всего при постройки пути от...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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