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

Алгоритм нахождения покрытия, близкого к кратчайшему - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Cheshire Cat
1 / 1 / 1
Регистрация: 11.12.2010
Сообщений: 14
11.12.2010, 23:23     Алгоритм нахождения покрытия, близкого к кратчайшему #1
Необходимо найти покрытие, близкое к кратчайшему, по методу "минимальный столбец - максимальная строка".
Описание алгоритма:
1. Исходная таблица считается текущей преобразуемой таблицей покрытий, множество строк покрытий - пусто.
2. В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу, если в таблице есть не вычеркнутые столбцы, то выполняется п.2, иначе - покрытие построено.

Вопрос не по алгоритму, но по возникновению исключительной ситуации.
0xC0000005: Access violation writing location 0xcdcdcdcd. Выполнение останавливается на строке 107:
C++
1
for (int i=0; i<M; i++){ for (int j=0; j<N; j++) A[i][j]=Temp[i][j];}
B чём может быть причина? почитал немного об этом в интернете, реестр почистил Reg Organizer`ом, стоит антивирус Касперского. Если проблема в том, что где-то не освобождаю память, укажите, пожалуйста, где (проверял, но мог и не заметить).
Просьба не ругаться по поводу некоторой "сложности" алгоритма, а ответить на вопрос по существу. Если есть предложения, как улучшить алгоритм - буду очень благодарен за решения.
Моя реализация:
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
#include "stdafx.h"
#include <iostream>
using namespace std;
void Perebor(int**A,int M, int N, int**B, int c);
void Min_column(int**A, int N, int M, int* Sum, int**B,int c);
void Max_row(int**A, int MCN, int M, int N, int**B, int c);
void Build_cover(int**A,int**B,int c, int MRN, int N,int M);
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c);
int _tmain(int argc, _TCHAR* argv[])
{
    int M,N,c=0; //М - для хранения кол-ва строк, N- для хранения кол-ва столбцов
    cout<<"Enter number of rows: ";cin>>M;
    cout<<"Enter number of columns: ";cin>>N;
    int **B= new int*[M-1]; // массив В организован для хранения покрытия
    int **A= new int*[M];                       
    for (int i=0; i<M; i++) {A[i]= new int[N];}            
    cout<<"Fill the matrix\n";
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){scanf("%u", &A[i][j]);}
    }
    Perebor(A,M,N,B,c);
return 0;
};
void Perebor(int**A,int M, int N, int**B, int c){
    int *Sum= new int[N]; //в массиве Sum будем хранить кол-во единиц в каждом столбце матрицы
    for (int j=0; j<N; j++){
        Sum[j]=0;
        for (int i=0; i<M; i++){
            Sum[j]=Sum[j]+A[i][j];
        }
        if (Sum[j]==0) {
            cout<<"There is no cover in this matrix\n"; delete[]Sum;
            for(int i=0; i<M; i++) delete[]A[i]; delete[]A; delete[]B; exit(1);}
    };
    Min_column(A,N,M,Sum,B,c);
}
void Min_column(int**A, int N, int M, int* Sum, int**B,int c){
    int MCS=0; //Переменная для хранения кол-ва единиц в минимальном столбце
    int MCN=0; // Переменная для хранения номера минимального столбца
    for (int j=0; j<N-1; j++){
        if (Sum[j]<=Sum[j+1]){
            if (MCS==0){MCS=Sum[j];MCN=j;}             //организовано для того, чтобы мин. столбцом
            else{ if(MCS>Sum[j]){MCS=Sum[j];MCN=j;}} //стал первый обнаруженный мин. столбец
        }
        else {if (MCS==0){MCS=Sum[j+1];MCN=j+1;}}
    }
    delete[] Sum;
    Max_row(A,MCN,M,N,B,c);
}
void Max_row(int**A, int MCN, int M, int N, int**B, int c){
    int *Sum= new int[M];
    int MRS=0,MRN=0;
    for (int i=0; i<M; i++){
        Sum[i]=0;
        if (A[i][MCN]==1){
            for(int j=0; j<N; j++) Sum[i]=Sum[i]+A[i][j];
        }
    }
    for (int i=0; i<M-1; i++){
        if (Sum[i]-Sum[i+1]!=0){
            if(Sum[i]>Sum[i+1]){
                if (MRS==0) {MRS=Sum[i]; MRN=i;}
                else{
                    if(MRS<Sum[i]) {MRS=Sum[i]; MRN=i;}
                }
            }
            else{ 
                if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
                else{
                    if(MRS<Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
                }
            }
        }
        if (Sum[i]!=0 && Sum[i+1]!=0 && Sum[i]==Sum[i+1]){
            if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
            else{
                if(MRS<=Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
                }
        }
    }
    delete[] Sum;
    Build_cover(A,B,c,MRN,N,M);
}
void Build_cover(int**A,int**B,int c, int MRN, int N,int M){
    B[c]=new int[N];
    for(int j=0; j<N; j++) B[c][j]=A[MRN][j];
    c++;
    Erase_columns(A,B,MRN,M,N,c);
}
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c){
    int d=0,e=0; // Счётчики для массива Temp (d-строки, е-столбцы)
    int ed=0; //Счётчик количества единиц в максимальной строке
    for (int j=0; j<N; j++) if (A[MRN][j]==1) ed++;
    if (ed==N){cout<<"Cover is built\n"; for(int i=0; i<M; i++) delete[]A[i]; delete[]A; delete[]B; system("Pause"); exit(1);}
    int**Temp=new int*[M];
        for (int i=0; i<M; i++) Temp[i]=new int[N-ed];
        for (int j=0; j<N; j++){
            if (A[MRN][j]!=1){
                for (int i=0; i<M; i++){Temp[d][e]=A[i][j]; d++;}
                e++;d=0;}
        }
        for (int i=0; i<M; i++){delete[]A[i];}
        delete[]A;
        N=N-ed;
        int**A=new int*[M];
        for(int i=0; i<N; i++) A[i]=new int[N];
        for (int i=0; i<M; i++){ for (int j=0; j<N; j++) A[i][j]=Temp[i][j];}
        for (int i=0; i<M; i++) delete[]Temp[i];
        delete[]Temp;
        Perebor(A,M,N,B,c);
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.12.2010, 23:44     Алгоритм нахождения покрытия, близкого к кратчайшему #2
ed не может быть больше N?

Добавлено через 5 минут
Повторяющееся объявление переменной.
C++
1
int**A=new int*[M];
Cheshire Cat
1 / 1 / 1
Регистрация: 11.12.2010
Сообщений: 14
11.12.2010, 23:55  [ТС]     Алгоритм нахождения покрытия, близкого к кратчайшему #3
Цитата Сообщение от lemegeton Посмотреть сообщение
ed не может быть больше N?

Добавлено через 5 минут
Повторяющееся объявление переменной.
C++
1
int**A=new int*[M];
ed не может быть больше N, поскольку в строке не может быть больше единиц чем столбцов.
Перед переопределением А я освобождаю память. Мне нужно вычеркнуть из матрицы столбцы, в которых в максимальной строке содержатся 1. Я делаю это перемещением всех столбцов, в которых в макс. строке 0, в матрицу Temp, затем освобождаю память, выделенную для массива А, заново выделяю, но с новыми границами, и последовательно копирую в А содержимое Temp (на этом шаге возникает исключительная ситуация, её причина мне непонятна)
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.12.2010, 23:59     Алгоритм нахождения покрытия, близкого к кратчайшему #4
Вы заново объявляете переменную, которая является параметром ф-ции. Это вообще не должно собираться.
Код
error: declaration of ‘int** A’ shadows a parameter
Чем вы это собираете?
Cheshire Cat
1 / 1 / 1
Регистрация: 11.12.2010
Сообщений: 14
12.12.2010, 00:03  [ТС]     Алгоритм нахождения покрытия, близкого к кратчайшему #5
Microsoft Visual Studio 2010
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
12.12.2010, 00:14     Алгоритм нахождения покрытия, близкого к кратчайшему #6
Это был риторический вопрос. Прекомпилированный заголовок и название ф-ци main().
У меня этот код не собирается в GCC (4.4), а MSVS C++ 2010 под рукой нет.
Попробуйте убрать объявление (оставьте только создание), ну и попробуйте избавиться от сишных библиотек (особенно от scanf, system, exit) для чистоты.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2010, 00:21     Алгоритм нахождения покрытия, близкого к кратчайшему
Еще ссылки по теме:

Алгоритм нахождения простых чисел C++
C++ Алгоритм нахождения корней
C++ Не работает алгоритм нахождения слов

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

Или воспользуйтесь поиском по форуму:
Cheshire Cat
1 / 1 / 1
Регистрация: 11.12.2010
Сообщений: 14
12.12.2010, 00:21  [ТС]     Алгоритм нахождения покрытия, близкого к кратчайшему #7
ошибка найдена, элементарная невнимательность. Строка 106
До:
C++
1
2
int**A=new int*[M];
 for(int i=0; i<N; i++) A[i]=new int[N];
После:
C++
1
2
int**A=new int*[M];
for(int i=0; i<M; i++) A[i]=new int[N];
Yandex
Объявления
12.12.2010, 00:21     Алгоритм нахождения покрытия, близкого к кратчайшему
Ответ Создать тему
Опции темы

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