Решение задачи коммивояжера(краш программы)

@murphy_ · Регистрация: 03.12.2018

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

Решаю задачу коммивояжера жадным алгоритмом. Когда побываем во всех городах, нужно вернуться в стартовый. Количество городов вводится с клавиатуры, расстояние между ними так-же. Строится матрица смежности. Дальше ввожу стартовую вершину. Для этой вершины ищется город, который находится ближе всего и мы идём в него. В массив пройденных расстояний записываем вершину из который уже вышли. Дальше для второго города ищем тот, который находится ближе всего, с учетом того, что мы не должны вернуться в предыдущий город. И так далее, пока не побываем во всех городах. Потом мы по массиву пройденных городов считаем пройденное расстояние и прибавляем к нему расстояние из последнего города в стартовый. Так вот, при прохождении проверки(я её выделил в коде), программа крашится, скрин краша прилагается. Если эту проверку закомментировать, то программа будет работать, но очень часто выдаёт ложный результат. Примечательно, что аналогичная проверка в предыдущем цикле работает нормально.

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <windows.h>
#include <conio.h>
#include <iomanip>
using namespace std;
//Функция проверки, можно ли пойти в этот город
bool check(int key, int *mas, int kol)
{
    for(int j = 0; j < kol; j++)
        if(mas[j] != -1)
        if(mas[j] == key)   //Если в этом городе мы уже были
            return false;  
    return true;
}
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int kol;
    do  //Ввод кол-ва городов
    {
        cout << "Введите количество городов(2-10) --> ";
        cin >> kol;
    }while(kol < 2 || kol > 10);
    //Создание матрицы смежности
    int **arr = new int *[kol];
    for(int i = 0; i < kol; i++)
       arr[i] = new int [kol];
    
    int kol1 = kol;
    int rasst;
    for(int i = 0; i < kol1; i++)
        {   
            for(int j = 0; j < kol1; j++)
                { 
                    if(i == j)  //Если одинаковые точки - заполняем нулями, чтобы получилась главная диагональ нулей
                        {
                            arr[i][j] = 0;
                            continue;
                        }
                    do  //Ввод расстояния между городами для заполнения матрицы смежности
                    {   
                    cout << "Введите расстояние от города " << i << " до города " << j << " --> ";
                    cin >> rasst;
                    }while(rasst < 1);
                    arr[i][j] = rasst;
                }   
        }
    //Вывод матрицы смежности
    cout << endl << "Матрица смежности: ";  
    for(int i = 0; i < kol; i++)
        {   
            cout << endl;
            for(int j = 0; j < kol; j++)
               cout << setw(5) << arr[i][j];
        }
    
    int *mas1 = new int [kol + 1];   //Массив городов, в которых мы побывали
    
    cout << endl;
    char ans;
    int start;
    do
    {
    for(int i = 0; i < kol; i++)    //Заполняем массив -1
        mas1[i] = -1;
    do  //Ввод стартового города
    {   
    cout << "Введите стартовый город --> ";
    cin >> start;
    }while(start < 0 || start > kol - 1);
    int now = start;
    int res = 0;
    for(int i = 0; i < kol; i++)
        {
            int min;
            if(now != 0)   //Если не нулевая строка
                min = arr[now][0];
            else
                min = arr[now][1];              
            for(int j = 0; j < kol; j++)
                {
                    if(check(j, mas1, kol))
                        if(arr[now][j] < min && arr[now][j] > 0)  //Нахождение минимума
                            min = arr[now][j];      
                }   
            int temp = now;
            for(int j = 0; j < kol; j++)
                {
                    //*******************************ВОТ ТУТ КРАШ**************************
                     if(check(j, mas1, kol))
                       //**********************************************************
                    if(arr[now][j] == min)
                        {   
                            mas1[i] = now;   //Заполняем массив пройденных городов
                            temp = j;
                            break;
                        }
                    
                }
            now = temp;
        }
 
    for(int i = 0; i < kol - 1; i++)   //Считаем пройденый путь
        {
            int j = mas1[i];
            int k = mas1[i + 1];
 
            cout << endl << res << " += " << arr[j][k];
            res += arr[j][k];       
        }
    
    now = mas1[kol - 1];  //Добавляем к результату возврат в начальную точку
    cout << endl << res << " += " << arr[now][start];
    res += arr[now][start]; 
    //Вывод маршрута
    cout << endl << "Маршрут: "; 
    for(int i = 0; i < kol; i++)
        cout << setw(5) << mas1[i];
    cout << setw(5) << start;
    
    cout << endl << "Пройденное расстояние: " << res;
    
    cout << endl << "Желаете продолжить поиск путей?(+, если да) --> ";
    cin >> ans;
    
    }while(ans == '+');
        
    delete [] mas1; //Удаление массива пройденных городов
    
    //Удаление матрицы смежности
    for(int i = 0; i < kol; i++) 
      delete [] arr[i];
    delete [] arr;   
    
    system("pause");
    return 0;
}

Решение задачи коммивояжера(краш программы)

@L0M · 16.12.2018, 01:27

Вы сделали несколько ошибок в результате которых происходило обращение к элементу массива по индексу -1.
У меня, например, ваш код крашился в строке 110 при входных данных: 3 города с расстояниями 5, 3 и 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
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
#include <iostream>
#include <iomanip>
#include <windows.h>
 
using namespace std;
 
//Функция проверки, можно ли пойти в этот город
bool check(int key, int *mas, int kol) {
    for (int j = 0; j < kol; j++)
        if (mas[j] == key)   //Если в этом городе мы уже были
            return false;
    return true;
}
 
int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
 
    int kol;
    do  //Ввод кол-ва городов
    {
        cout << "Введите количество городов(2-10) --> ";
        cin >> kol;
    } while (kol < 2 || kol > 10);
    //Создание матрицы смежности
    int **arr = new int *[kol];
    for (int i = 0; i < kol; i++)
        arr[i] = new int[kol];
 
    int rasst;
    for (int i = 0; i < kol; i++) {
        for (int j = i; j < kol; j++) {
            if (i == j)  //Если одинаковые точки - заполняем нулями, чтобы получилась главная диагональ нулей
            {
                arr[i][j] = 0;
                continue;
            }
            do  //Ввод расстояния между городами для заполнения матрицы смежности
            {
                cout << "Введите расстояние от города " << i << " до города " << j << " --> ";
                cin >> rasst;
            } while (rasst < 1);
            arr[i][j] = arr[j][i] = rasst;
        }
    }
    //Вывод матрицы смежности
    cout << endl << "Матрица смежности: ";
    for (int i = 0; i < kol; i++) {
        cout << endl;
        for (int j = 0; j < kol; j++)
            cout << setw(5) << arr[i][j];
    }
 
    int *route = new int[kol];   // Маршрут (массив городов, в которых мы побывали в порядке посещения)
 
    cout << endl;
    char ans;
    int start;
    do {
        for (int i = 0; i < kol; i++)    //Заполняем массив -1
            route[i] = -1;
        do  //Ввод стартового города
        {
            cout << "Введите стартовый город --> ";
            cin >> start;
        } while (start < 0 || start > kol - 1);
 
        route[0] = start;
        int now = start;
        int path = 0;                       // длина уже пройденного пути
        cout << "\nМаршрут:" << endl;
        for (int i = 1; i < kol; i++) {     // i - индекс по маршруту и количество переходов, не считая возврата в стартовый город
            int min = INT_MAX, min_town;
            for (int j = 0; j < kol; j++) {
                if (check(j, route, kol) && arr[now][j] < min && arr[now][j] > 0) {  //Нахождение минимума
                    min = arr[now][j];      // запомнили текущий минимум
                    min_town = j;           // запомнили номер города для текущего минимума
                }
            }
            // а здесь min - действительный минимум и min_town - номер города с минимальным расстоянием от текущего
            path += min;            // добавляем к общему пути
            route[i] = min_town;    // добавляем город в маршрут
            cout << setw(2) << now << " -> " << setw(2) << route[i] << "   (расстояние " << min << ", путь " << path << ")" << endl;
            now = route[i];
        }
        // обрабатываем возврат в стартовый город
        path += arr[start][now];
        cout << setw(2) << now << " -> " << setw(2) << start << "   (расстояние " << arr[start][now] << ", путь " << path << ")" << endl;
        cout << "Общая длина пройденного пути: " << path << endl;
 
        cout << endl << "Желаете продолжить поиск путей?(+, если да) --> ";
        cin >> ans;
 
    } while (ans == '+');
 
    delete[] route; //Удаление массива пройденных городов
 
    //Удаление матрицы смежности
    for (int i = 0; i < kol; i++)
        delete[] arr[i];
    delete[] arr;
 
    system("pause");
    return 0;
}

@murphy_ · 16.12.2018, 12:33 **[ТС]**

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

Вы сделали несколько ошибок в результате которых происходило обращение к элементу массива по индексу -1.
У меня, например, ваш код крашился в строке 110 при входных данных: 3 города с расстояниями 5, 3 и 2.
Кроме того, у вас при заполнении матрицы смежности возможен вариант, когда путь туда не равен пути обратно. В реальной жизни такое возможно, но здесь, я думаю, можно упростить задачу и считать, что длина пути не зависит от направления движения. Это, кстати, уменьшает количество значений, вводимых в матрицу смежности, вдвое.
Я тут подредактировал ваш код. Поправил ошибки, убрал лишнее. С пристрастием не тестировал, но вроде работает правильно.

Спасибо, переделал по вашему алгоритму и теперь работает.
А матрица такая по условию должна быть.

@Wlod · 01.11.2019, 21:09

можно просить Вас о помощи?
получил задание, решить ту же самую задачу методом ближайшего соседа(жадным).
Разница в том что на входе получаю координаты точек. т.е. надо рассчитать расстояния между городами. На бумаге рассчитываю, но вот как нужно изменить код чтобы прикрутить к нему недостающую часть не знаю, т.к. не силен в программировании.
Заранее примного благодарен за потраченное время и Вашу помощь.

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@Wlod 0 / 0 / 0 Регистрация: 21.05.2019 Сообщений: 4
	01.11.2019, 21:09
	можно просить Вас о помощи? получил задание, решить ту же самую задачу методом ближайшего соседа(жадным). Разница в том что на входе получаю координаты точек. т.е. надо рассчитать расстояния между городами. На бумаге рассчитываю, но вот как нужно изменить код чтобы прикрутить к нему недостающую часть не знаю, т.к. не силен в программировании. Заранее примного благодарен за потраченное время и Вашу помощь. 0