Форум программистов, компьютерный форум CyberForum.ru

Бродячий торговец - C++

Восстановить пароль Регистрация
 
Roodey
4 / 4 / 1
Регистрация: 23.05.2013
Сообщений: 36
27.12.2013, 10:03     Бродячий торговец #1
Приветствую господа, не нашел в какой раздел это следуюет написать, посему пишу в привычный))
Имеется задача о бродячем торговце, точнее говоря ее упрощенная версия. "Упрощения":
- Не нужно выполнять проверку на наличие пути, условлено, что один город соединен со всеми остальными
- Собственно, так как каждый город соединен со всеми другими, проверку на Гамильтонов граф делать тоже не надо
- "Торговец" всегда выходит из первого города и возвращается в него же.

А задание собственно следующее: Найти минимальный путь, по которому "торговец" может выйти из первого города, обойти все города по одному разу и вернуться в изначальный.

И мне необходимо написать последовательную и параллельную версии программы. Последовательная версия есть и полностью работает, а вот с параллельной есть огромные проблемы. Нет даже идеи как это реализовать.
Собственно, вот код последовательной
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
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <vector>
#include <stdlib.h>
#include <fstream>
 
using namespace std;
 
const int n = 4;        //тут вбивать количество городо
int a[n], a1[n], c[n];
 
//матрица расстояний:
int b[15][15]={
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,},
{0, 0, 66, 14, 28, 31, 69, 35, 17, 56, 5, 8, 46, 74, 96,},
{0, 66, 0, 16, 96, 33, 87, 2, 84, 12, 78, 96, 20, 92, 93,},
{0, 14, 16, 0, 41, 7, 24, 9, 42, 39, 63, 46, 46, 11, 19,},
{0, 28, 96, 41, 0, 57, 34, 55, 59, 17, 67, 36, 15, 86, 28,},
{0, 31, 33, 7, 57, 0, 91, 32, 0, 33, 71, 64, 79, 18, 75,},
{0, 69, 87, 24, 34, 91, 0, 94, 49, 72, 10, 15, 8, 25, 2,},
{0, 35, 2, 9, 55, 32, 94, 0, 54, 78, 41, 27, 43, 19, 43,},
{0, 17, 84, 42, 59, 2, 49, 54, 0, 85, 60, 69, 98, 66, 93,},
{0, 56, 12, 39, 17, 33, 72, 78, 85, 0, 44, 94, 20, 88, 15,},
{0, 5, 78, 63, 67, 71, 10, 41, 60, 44, 0, 49, 60, 68, 16,},
{0, 8, 96, 46, 36, 64, 15, 27, 69, 94, 49, 0, 70, 34, 0,},
{0, 46, 20, 46, 15, 79, 8, 43, 98, 20, 60, 70, 0, 48, 66,},
{0, 74, 92, 11, 86, 18, 25, 19, 66, 88, 68, 34, 48, 0, 85,},
{0, 96, 93, 19, 28, 75, 2, 43, 93, 15, 16, 0, 66, 85, 0}};
 
int iter=0;
int sum=0, sum1=99999;      //sum = сумма расстояний // sum1 = текущая минимальная сумма
int j=0, i=0, i1;       //счетчики
 
void f(int ind, int used)
{   sum=0;
    if(ind==n)
    {
        for(int i=0; i<n; i++)
        {
            cout<<a[i]<< " " ;
        }
        cout<<a[0];
        cout<<" || ";
        for(int i=0; i<n; i++)
        {
            cout<<b[a[i-1]][a[i]]<<" ";
            sum=sum+b[a[i-1]][a[i]];
            i1=i;
        }
        cout<<"||"<<b[a[i1]][1];
 
        sum=sum+b[a[i1]][1];
        cout<<'\t'<<" || amount = "<<sum;
        cout << endl;
        iter++;
        if(sum1>sum)    //поиск минимальной суммы
            {
                sum1=sum;
                for(int i=0; i<n; i++)      //запомнить путь для этой суммы
                    {
                        c[i]=a[i];
                    }
            }
    return;
    }
 
 
    for(int i=2; i<n+1; ++i)
    {
        if(used&(1<<i))
            continue;
        a[ind]=i;
        f(ind+1, used|(1<<i));
    }
}
 
 
int main()
{
    cout<<"Press 'Enter' to start ";
    cin.get();
 
    a[0] = 1;       //стартовая точка всегда '1'1
    f(1, 1);
 
    cout<<endl<<"number of paths = "<<iter<<endl;
    cout<<endl;
 
    cout<<"minimum amount = "<<sum1<<endl;
    cout<<"way is: ";
    for(int i=0; i<n; i++)
        {
            cout<<c[i]<<" ";
        }
        cout<<b[a[i1]][1];
        cout<<endl<<endl;
    for(int i1=1; i1<n+1; i1++)
    {
        for(int j1=1; j1<n+1; j1++)
            cout<<b[i1][j1]<<" ";
        cout<<endl;
    }
    cout<<endl;
    return 0;
}


Параллельную программу надо выполнить с применением MPI. Хотелось бы с openMP, но условие стоит, что с MPI...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2013, 10:03     Бродячий торговец
Посмотрите здесь:

C++ Коммивояжер (бродячий торговец)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 20:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru