Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Nzoth
1 / 1 / 0
Регистрация: 19.06.2016
Сообщений: 15
#1

Метод ближайшего соседа в задаче коммивояжера - C++

26.02.2017, 15:27. Просмотров 621. Ответов 2
Метки c++ (Все метки)

Всем привет, столкнулся со сложностями в реализации алгоритма ближайшего соседа по теории графов.
Его описание:
"Пункты обхода плана последовательно включаются в маршрут, причем каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута."

Я вижу алгоритм следующим образом: задаем начальный город (вершину) N, начинаем с первого элемента N-ой строки искать наименьшее значение в строке, находим находим наименьший элемент i, j в матрице, добавляем индекс столбца j в маршрут и наименьшее значение min в длину маршрута, присваиваем элементу i, j, а также симметричному элементу j, i значение -1 (помечаем что побывали в нем), переходим на j-ую строку и повторяем до тех пор, пока не побываем во всех вершинах.

Проблема в том, что я не знаю как вернуться в исходную вершину, после того как пройдены все остальные. Кроме того мой текущий алгоритм вычисляет только первую итерацию цикла и я думаю что ошибка в переходе на другую строку, но я не знаю как это исправить.

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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector <int> path;
const int N = 5;
int a[N][N];
 
void calcpath (int start)
{    
    int min, p_min, path_length = 0;
    
    if (start == 1) // если начинаем с первой строки, то за минимальное значение берем второй элемент 
        min = a[0][1];
    else
        min = a[start - 1][0];
 
    path.push_back(start); // добавляем начальную вершину в путь
 
    for (int i = start - 1; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i][j] < min && a[i][j] != 0 && a[i][j] != -1) // поиск наименьшего значения, игнорируем элементы со значениями 0 и -1
            {
                min = a[i][j];
                p_min = j;
            }
        }
        path.push_back(p_min + 1); // добавляем вершину в путь
        path_length += min; // добавляем значение в длину пути
        a[i][p_min] = -1;
        a[p_min][i] = -1;
        i = p_min; // переходим на новую строку
    }
 
    for (int i = 0; i < path.size(); i++)
    cout << path[i] << " -> ";
}
 
int main()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];
    
    calcpath(1);
    system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2017, 15:27
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Метод ближайшего соседа в задаче коммивояжера (C++):

Метод ближайшего соседа через STL Algorithm - C++
Добрый день. Подскажите можно метод ближайшего соседа сделать через сортировку с функтором?

Задача коммивояжера (метод ветвей и границ) - C++
Написать программу для решения задачи коммивояжёра с помощью метода ветвей и границ. Интерфейс должен позволять вводить количество городов...

Сортировка выбором (метод прямого выбора). Ошибка в задаче - C++
Привет. У меня есть программка решение на задачку &quot;Первые десять элементов массива М(30) отсортировать в порядке возрастания, а остальные в...

СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя - C++
Помогите ребят. Не могу построить алгоритмы для этих методов Язык C++

Алгоритм Коммивояжера - C++
кто может помочь с прогой на С или С++?

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

2
Nzoth
1 / 1 / 0
Регистрация: 19.06.2016
Сообщений: 15
04.03.2017, 08:48  [ТС] #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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector <int> path;
const int N = 5;
int a[N][N];
 
void calcpath (int start)
{    
    int min = 999, p_min = 0, path_length = 0, k;
    path.push_back(start);
 
    for (int i = start - 1; ; )
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i][j] < min && a[i][j] != 0)
            {
                min = a[i][j];
                p_min = j;
            }
        }
        
        path.push_back(p_min + 1);
        path_length += min;
        a[i][p_min] = 0;
        a[p_min][i] = 0;
        i = p_min;
        min = 999;
        k = 0;
 
        for (int a = 1; a <= N; a++)
        {
            for (int b = 0; b < path.size(); b++)
            {
                if (a == path[b])
                {
                    k++;
                    continue;
                }
            }
        }
 
        if (k == N)
            break;
    }
    
    for (int i = 0; i < path.size(); i++)
    cout << path[i] << " -> ";
    cout << endl;
    cout << path_length;
}
 
int main()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];
    
    calcpath(1);
    system("pause");
}
0
Nzoth
1 / 1 / 0
Регистрация: 19.06.2016
Сообщений: 15
19.03.2017, 13:08  [ТС] #3
Разобрался. Дело в том, что в зад. коммивояжера задан полный граф, а вернуться обратно в таком случае очень просто.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2017, 13:08
Привет! Вот еще темы с ответами:

Поиск ближайшего числа в массиве - C++
Смысл заключается в следующем: дана шкала в миллиметрах и показатель уровня заполнения емкости, соответствующая данной шкале, т.е. 1 мм =...

Вычисление ближайшего удачного года - C++
Здравствуй, меня зовут Аня. Являюсь студентом-первокурсником. Для себя выбрала не самый простой путь: стать программистом. Работаю (:D если...

Поиск ближайшего среднего арифметического (на C++) - C++
Люди добрые, помогите написать код программы на С++ Видел код этой программы на Pascal'е но не пойму как перевести его в Си++ Поиск...

Округление числа до ближайшего целого - C++
Часто видел в темах в вопросом &quot;как округлить до ближайшего целого&quot; ответы вроде &quot;использовать функцию a=floor(a+0.5); или a=round(a); ...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru