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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

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