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

@Cheshire Cat · Регистрация: 11.12.2010

Студворк — интернет-сервис помощи студентам

Необходимо найти покрытие, близкое к кратчайшему, по методу "минимальный столбец - максимальная строка".
Описание алгоритма:
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 · 11.12.2010, 23:44

ed не может быть больше N?

Добавлено через 5 минут
Повторяющееся объявление переменной.

C++
1
int**A=new int*[M];

@Cheshire Cat · 11.12.2010, 23:55 **[ТС]**

Сообщение от lemegeton

ed не может быть больше N?

Добавлено через 5 минут
Повторяющееся объявление переменной.

C++
1
int**A=new int*[M];

ed не может быть больше N, поскольку в строке не может быть больше единиц чем столбцов.
Перед переопределением А я освобождаю память. Мне нужно вычеркнуть из матрицы столбцы, в которых в максимальной строке содержатся 1. Я делаю это перемещением всех столбцов, в которых в макс. строке 0, в матрицу Temp, затем освобождаю память, выделенную для массива А, заново выделяю, но с новыми границами, и последовательно копирую в А содержимое Temp (на этом шаге возникает исключительная ситуация, её причина мне непонятна)

@lemegeton · 11.12.2010, 23:59

Вы заново объявляете переменную, которая является параметром ф-ции. Это вообще не должно собираться.

Code
1
error: declaration of ‘int** A’ shadows a parameter

Чем вы это собираете?

@Cheshire Cat · 12.12.2010, 00:03 **[ТС]**

Microsoft Visual Studio 2010

@lemegeton · 12.12.2010, 00:14

Это был риторический вопрос. Прекомпилированный заголовок и название ф-ци main().
У меня этот код не собирается в GCC (4.4), а MSVS C++ 2010 под рукой нет.
Попробуйте убрать объявление (оставьте только создание), ну и попробуйте избавиться от сишных библиотек (особенно от scanf, system, exit) для чистоты.

@Cheshire Cat · 12.12.2010, 00:21 **[ТС]**

ошибка найдена, элементарная невнимательность. Строка 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];

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@Cheshire Cat 1 / 1 / 1 Регистрация: 11.12.2010 Сообщений: 14
	12.12.2010, 00:03 [ТС]
	Microsoft Visual Studio 2010 0

@lemegeton 4903 / 2696 / 921 Регистрация: 29.11.2010 Сообщений: 5,783
	12.12.2010, 00:14
	Это был риторический вопрос. Прекомпилированный заголовок и название ф-ци main(). У меня этот код не собирается в GCC (4.4), а MSVS C++ 2010 под рукой нет. Попробуйте убрать объявление (оставьте только создание), ну и попробуйте избавиться от сишных библиотек (особенно от scanf, system, exit) для чистоты. 0