@Nikaw

я стала решать, как задачу коммивояжера методом ветвей и границ, просто писала программу по алгоритму
есть проблема в том, что я застряла на моменте, где нужно вычеркнуть столбец и строку, ведь там надо ещё сохранить и указатели, то есть если вычёркивать 2 строку и 3 столбец, то указатели строки должны остаться 1345..., а указатели столбца 12456...
далее я хотела использовать while и чтобы он искал эти дуги
вот сам код
#include <bits/stdc++.h>
// ============================================================
using namespace std;
int prompt_menu_item()
{
int variant;
cout << "Выберите вариант\n" << endl;
cout << "1. Ввести числа с клавиатуры\n"
<< "2. Сгенерировать числа\n" << endl;
cout << ">>> ";
cin >> variant;
return variant;
}
//============================================================================
int main()
{
setlocale (LC_ALL, "RUS");
int i, j, n, min, min2, minn=0, min3, min4, k=0, l, f, minn1=0, minn2=0;
int P = std :: numeric_limits<int> :: max();
int variant = prompt_menu_item();
cout << " Введите количество типов деталей: \n";
cin >> n;
cout << "Матрица - "<< n <<" X " << n << endl;
int **E = new int* [n]; // создаём массив указателей
int **D = new int* [n];
int **C = new int* [n];
int **A = new int* [n];
int **B = new int* [n-1];
int **F = new int* [n];
for (int i = 1; i <= n; i++)
{
E[i] = new int [n]; //создаём элементы
D[i] = new int [n];
C[i] = new int [n];
A[i] = new int [n];
F[i] = new int [n];
}
for (int i = 1; i <= n; i++)
{
B[i] = new int [n];
}
switch (variant)
{
case 1:
{
for (int i = 1; i <= n; ++i) // Заполнение матрицы c клавиатуры
{
for (int j = 1; j <= n; ++j)
{
if(i==j)
E[i][j]=P;
else
{
cout<<"Введите элемент["<<i<<"]["<<j<<"]: \n";
cin>>E[i][j];
}
}
cout << endl;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
cout << E[i][j] << " "; //выводим матрицу
cout<<endl;
}
}
break;

case 2:
{
srand(time(NULL));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
if(i==j)
E[i][j]=P;
else
E[i][j] = rand() % n*n+1; //заполняем матрицу случайными элементами
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << E[i][j] << " "; //выводим матрицу
cout<<endl;
}
}
break;
default:
cout << "Вы выбрали неверный вариант" << endl;
exit(EXIT_FAILURE);
}
//==========================================================================
for(int i = 1;i <= n; i++) //находим матрицу, приведённую по строкам
{
min=E[i][1];
for(int j = 1;j <= n; j++)
if(E[i][j] < min)
min=E[i][j];
minn+=min; //находим константу приведения, меньше которой
for(int j = 1;j <= n; j++) //невозможно построить искомый маршрут
D[i][j]=E[i][j]-min;
}
cout<<"\nМатрица, приведённая по строкам:\n\n";
for(int i = 1;i <= n ; i++)
{
for(int j = 1;j <= n; j++)
cout << D[i][j] << " ";
cout<<endl;
}
//================================================================================
for(int j = 1;j <= n;j++) //находим матрицу, приведённую по столбцам
{
min2 = D[1][j];
for(int i = 1;i <= n; i++)
if(D[i][j] < min2)
min2 = D[i][j];
minn+=min2;
for(int i = 1;i <= n; i++)
C[i][j] = D[i][j] - min2;
}
cout<<"\nМатрица, приведённая по столбцам:\n";
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= n; j++)
cout << C[i][j] << " ";
cout<<endl;
}
cout<<"\nКонстанта приведения: " << minn; //выводим константу приведения
//================================================================================ ===111111
for(int i = 1;i <= n; i++) //находим степени нулевых элементов
for(int j = 1;j <= n; j++) //приведённой матрицы(суммы минимумов по строке и столбцу)
{
if (C[i][j]==0)
{
min3 = C[i][1];
for(int m = 2; m <= n; m++)
if( min3 > C[i][m] && m!=j)
min3 = C[i][m];
min4=C[1][j];
for(int m = 2;m <= n; m++)
if( min4 > C[m][j] && m!= i)
min4 = C[m][j];
if( min3+min4 > k || min3+min4 == k) //находим наибольшую степень нулевого элемента
{ //и координаты дуги, по которой мы будем проводить ветвление
k = min3 + min4;
l=i;
f=j;
}
}
}
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
A[i][j]=C[i][j];
cout << "\nНаибольшая степень нуля:" << k;
cout << "\nВетвление проводим по дуге:" << "(" << l <<"," << f << ")";
//================================================================================ ========
//исключаем ребро (l,f)
for(int i = 1;i <= n; i++) //находим минимальное по строкам
{
if(i==l)
{
min=C[i][1];
for(int j = 1;j <= n; j++)
{
if(j==f)
A[i][j]=P;
if(C[i][j] < min )
min=C[i][j];
}
minn1+=min;
}
}
for(int j = 1;j <= n;j++) //находим минимальное по столбцам
{
if(j==f)
{
min2 = C[1][j];
for(int i = 1;i <= n; i++)
if(i==l)
A[i][j]==P;
if(C[i][j] < min2 )
min2 = C[i][j];
minn1+=min2;
}
}
cout<<"\nМатрица, после исключения ребра:\n";
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= n; j++)
cout << A[i][j] << " ";
cout<<endl;
}
cout<<"\nСумма констант: " << minn1; //выводим константу приведения
minn1+=minn;
cout<<"\nКонстанта приведения без ребра: " << minn1;
//================================================================================ ===
//включаем ребро (l,f)
return 0;
}
Выход:
Выберите вариант

1. Ввести числа с клавиатуры
2. Сгенерировать числа

>>> 2
Введите количество типов деталей:
4
Матрица - 4 X 4
2147483647 13 1 1
5 2147483647 9 1
5 13 2147483647 9
13 13 1 2147483647

Матрица, приведённая по строкам:

2147483646 12 0 0
4 2147483646 8 0
0 8 2147483642 4
12 12 0 2147483646

Матрица, приведённая по столбцам:
2147483646 4 0 0
4 2147483638 8 0
0 0 2147483642 4
12 4 0 2147483646

Константа приведения: 16
Наибольшая степень нуля:4
Ветвление проводим по дуге: (4,3)
Матрица, после исключения ребра:
2147483646 4 0 0
4 2147483638 8 0
0 0 2147483642 4
12 4 2147483647 2147483646

Сумма констант: 0
Константа приведения без ребра: 16

Вернуться к обсуждению:
Определить такой порядок переналадки при котором время простоя оборудования минимально C++

0