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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.80
Фаягуль
0 / 0 / 0
Регистрация: 07.06.2012
Сообщений: 1
#1

Задача коммивояжера, программа - C++

10.06.2012, 20:47. Просмотров 3529. Ответов 0
Метки нет (Все метки)

Здравствуйте! Нашла программу решения задачи коммивояжера методом полного перебора почему компилируется но выдает пустое консольное окно?( помогите пожалуйста!









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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
template <class data>
class MatrixBase
{
    typedef short int shint;
    typedef unsigned int uint;
    typedef std::vector <data> vectorT;
    typedef std::vector <vectorT> matrixT;
    typedef std::vector <shint> vectorIndexT;
    typedef std::pair <int, int> VerticesPair;
    typedef std::vector <VerticesPair> EdgesVector;
 
    public:
 
        // признаки данных
        data nullAttr, infinityAttr;
 
        // конструктор
        MatrixBase (uint c, data nil = 0, data inf = -1) : nullAttr(nil), infinityAttr(inf)
        {
            __matrix.resize(c);
            for (uint i = 0; i < c; i++) {
                __matrix[i].resize(c);
                for (uint j = 0; j < c; __matrix[i][j++] = infinityAttr);
            }
        }
        // перегрузка операторов для сохранения тождественности объекта и матрицы
        vectorT & operator [] (uint index) { return __matrix[index]; }
        matrixT & operator () () { return __matrix; }
}
// метод прямого перебора (грубой силы)
        vectorIndexT TSP_BruteForce (int start = -1)
        {
            // длина обхода
            data length = nullAttr;
            // вектор индексов перебора, результирующий вектор индексов
            vectorIndexT index (__matrix.size(), 0), out (__matrix.size(), 0);
            for (uint i = 0; i < index.size(); i++, index[i] = i);
            // сортировка для пермутаций
            sort (index.begin(), index.end());
            // ключ выбора начального элемента
            bool any = (start <= -1);
            do {
                if ((index[0] == (shint)start) || (any)) {
                    // контур непрерывен
                    bool solid = true;
                    // аккумулятор значения
                    data acc = __matrix[index[index.size()-1]][index[0]];
                    for (uint i = 0; i < index.size() - 1; i++) {
                        // буферная переменная
                        data buffer = __matrix[index[i]][index[i+1]];
                        // проверка на непрерывность контура
                        if ((acc == infinityAttr) || (buffer == infinityAttr)) {
                            // контур прервался
                            solid = false;
                            break;
                        }
                        acc += buffer;
                    }
                    // предварительная проверка контура
                    if ((solid) && ((length == nullAttr) || (acc < length))) {
                        // длина обхода
                        length = acc;
                        // перезапись результата
                        out = index;
                    }
                }
            }
            // производим пермутацию (перестановку)
            while (next_permutation(index.begin(), index.end()));
            return out;
        }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.06.2012, 20:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача коммивояжера, программа (C++):

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

Задача коммивояжера методом динамического программирования - C++
Помогите пожалуйста переделать коммивояжера методом динамического программирования. Пусть n - это количество вершин графа. Тогда в цикле...

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

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

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2012, 20:47
Привет! Вот еще темы с ответами:

Граф, решение задачи коммивояжера - C++
Решить задачу коммивояжёра (человек выезжает из одного города, должен объехать все остальные вернуться в первоначальный, проехав...

Метод ближайшего соседа в задаче коммивояжера - C++
Всем привет, столкнулся со сложностями в реализации алгоритма ближайшего соседа по теории графов. Его описание: &quot;Пункты обхода плана...

Задача решена, но программа не работает с большими значениями - C++
Пусть An = sin(1–sin(2+sin(3–sin(4+…sin(n))…) Обозначим Sn = (…(A1+n)A2+n–1)A3+…+2)An+1 Для заданного N выведите выражение SN ...

Задача с классами. Программа с использованием класса Employee - C++
Задача: Напишите программу с использованием класса Employee, которая создает два объекта класса Employee, устанавливает значение членов...


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

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

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