Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
1

Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут....

22.07.2010, 04:46. Показов 7061. Ответов 30
Метки нет (Все метки)

Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, который позволил бы посетить их все по одному разу. Построить графическое изображение маршрута?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2010, 04:46
Ответы с готовыми решениями:

Проложить если возможно маршрут между противолежащими углами
Практическое задание: 9. Двумерный квадратный массив заполнен нулями и единицами. Проложить если...

Кратчайший маршрут
Очень сложная задачка на мой взгляд. Подскажите хотя-бы алгоритм! Буду очень благодарен.

Найти кратчайший маршрут
Найти кратчайший маршрут, который начинается и завершается в заданной вершине ориентированному...

Найти кратчайший маршрут, и указать последовательности торговых точек. Графы
Условие: Программа должна найти длину кратчайшего маршрута, но и указать последовательность...

30
Эксперт С++
5825 / 3476 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
22.07.2010, 06:16 2
Лучший ответ Сообщение было отмечено как решение

Решение

Цитата Сообщение от SergProgC++ Посмотреть сообщение
Построить графическое изображение маршрута?
Построй
4
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
23.07.2010, 21:22 3
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/////////////////////////////////////////////////////////////////////////////
//Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, 
//который позволил бы посетить их все по одному разу.
/////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <numeric>
#include <vector>
 
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef T_coord                T_dist;
typedef T_point                T_shift;
typedef std::vector<T_shift>   T_shifts;
/////////////////////////////////////////////////////////////////////////////
struct T_numbered_point : T_point
{
    //-----------------------------------------------------------------------
    int  num_;
    //-----------------------------------------------------------------------
    T_numbered_point
        (
            T_point  point,
            int      num           
        ) 
        : T_point(point), 
          num_   (num)
    {}
    //-----------------------------------------------------------------------
    T_shift operator- (const T_numbered_point&  np)//Для алгоритма std::adjacent_difference
    {        
        return T_point(*this) - np;                
    }
    //-----------------------------------------------------------------------        
    bool operator < (const T_numbered_point&  np)//Для алгоритма  std::next_permutation.
    {
        return num_ < np.num_;
    }
    //-----------------------------------------------------------------------    
};
/////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_numbered_point>   T_numbered_points;
/////////////////////////////////////////////////////////////////////////////
T_numbered_points  input_numbered_points()
{
    const int  POINTS_TOTAL_MIN = 2;
    int        points_total;    
    do
    {
        std::cout << "Введите количество точек >= "
                  << POINTS_TOTAL_MIN   
                  << ": ";
        std::cin >> points_total;
    }while(points_total < POINTS_TOTAL_MIN);
    
    std::cout << "Введите координаты "
              << points_total
              << " различных точек:"
              << std::endl;
    
    T_numbered_points  numbered_points;
    
    while(   numbered_points.empty()
          || numbered_points.size() != points_total)
    {        
        int point_num = numbered_points.size() + 1;
        std::cout << "X" 
                  << point_num
                  << " = ";
        int x;
        std::cin >> x;
        std::cout << "Y" 
                  << point_num
                  << " = ";
        int y;
        std::cin >> y;                
        T_numbered_point  numbered_point(T_point(x, y), point_num);
        if( !numbered_points.empty()
            && std::find(numbered_points.begin(), 
                         numbered_points.end(), 
                         numbered_point) != numbered_points.end() )
        {
             std::cout << "Такая точка уже есть."
                       << std::endl;       
        }
        else
        {
            numbered_points.push_back(numbered_point);
        }
        std::cout << std::endl;
    }    
    return  numbered_points;
}
/////////////////////////////////////////////////////////////////////////////
void print_optim_posledov_obchoda(const T_numbered_points&  numbered_points)
{    
    T_numbered_points  temp_numbered_points(numbered_points);    
    T_shifts           shifts(numbered_points.size());
    T_numbered_points  numbered_points_v_optim_posledov;
    T_dist             dist_sum_min;
    bool               dist_sum_min_is_init = false;
    do
    {
        std::adjacent_difference(temp_numbered_points.begin(), 
                                 temp_numbered_points.end(), shifts.begin());
 
        struct T_dist_sum
        {
            T_dist operator() (const T_shift& p1, const T_shift& p2)
            {
                return abs(p1) + abs(p2);
            }
        };   
 
        T_dist  dist_sum = std::accumulate(shifts.begin() + 1, shifts.end(), 
                                           T_dist(), T_dist_sum());
        if(!dist_sum_min_is_init
           || dist_sum < dist_sum_min)
        {
            dist_sum_min                      = dist_sum;
            dist_sum_min_is_init              = true;
            numbered_points_v_optim_posledov  = temp_numbered_points;
        }
    }while
         ( 
             std::next_permutation
                 (
                     temp_numbered_points.begin() + 1, 
                     temp_numbered_points.end()                     
                 ) 
         );
 
    struct T_print_point_num
    {
        void operator() (T_numbered_points::value_type  numbered_point)
        {
            std::cout << numbered_point.num_
                      << ' ';
        }
    };
 
    std::cout << "Минимальный путь обхода "
              << numbered_points.size()
              << " заданных точек в последовательности "
              << std::endl;
    
    std::for_each(numbered_points_v_optim_posledov.begin(),
                  numbered_points_v_optim_posledov.end(), T_print_point_num());    
 
    std::cout << std::endl
              << "равен "
              << dist_sum_min
              << "."
              << std::endl;
}
/////////////////////////////////////////////////////////////////////////////
 
int main()
{    
    std::locale::global(std::locale(""));
    T_numbered_points  numbered_points = input_numbered_points();
    print_optim_posledov_obchoda(numbered_points);   
    return 0;
}
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
29.07.2010, 20:44  [ТС] 4
я не очень разбираюсь в стандартной библиотеке пока, объяснить можешь? че где да как делается? кстати почему у меня компилятор ошибки выдает проект както надо настраивать что ли
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
29.07.2010, 20:59 5
Цитата Сообщение от SergProgC++ Посмотреть сообщение
... у меня компилятор ошибки выдает проект както надо настраивать что ли
Не знаю, у меня в Visual Studio нормально работает.
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
01.08.2010, 21:23  [ТС] 6
А используя стандартные динамические массивы это можно реализовать?
error C2918: 'T_dist_sum' : illegal use of local type in template instantiation
error C2780: '_Ty __cdecl std::accumulate(_II,_II,_Ty)' : expects 3 arguments - 4 provided
see declaration of 'accumulate'
error C2918: 'T_print_point_num' : illegal use of local type in template instantiation

вот какие ошибки, прокомментируй пожалусто код, если не трудно плизззз :-)

Добавлено через 5 минут
Вообщем я задаю количество точек и создаю два массива динамический для Y и X координат точек, нашел длинны между точками. А дальше не знаю чего делать. Без стандартной библиотеки можно это как нибудь решить. А и классы мы еще не проходили я их пока смутно понимаю:-(((
0
Шаровик затейник
695 / 444 / 78
Регистрация: 06.05.2010
Сообщений: 1,109
02.08.2010, 13:48 7
Цитата Сообщение от SergProgC++ Посмотреть сообщение
классы мы еще не проходили
в приведенном коде нет классов, только структуры
0
Эксперт С++
5825 / 3476 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
02.08.2010, 15:10 8
Цитата Сообщение от Crudelis Посмотреть сообщение
в приведенном коде нет классов, только структуры
А vector - уже не шаблонный класс?

Кстати, структуры С++ от классов отличаются только доступом по умолчанию.

Цитата Сообщение от SergProgC++ Посмотреть сообщение
А и классы мы еще не проходили я их пока смутно понимаю
Почитай литературу на эту тему, потом пригодится
1
Шаровик затейник
695 / 444 / 78
Регистрация: 06.05.2010
Сообщений: 1,109
02.08.2010, 16:16 9
Цитата Сообщение от Nameless One Посмотреть сообщение
А vector - уже не шаблонный класс?
я изучаю с++ и до векторов не дошел к сожалению, не могу ничего сказать
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
02.08.2010, 21:38  [ТС] 10
Цитата Сообщение от Crudelis Посмотреть сообщение
я изучаю с++ и до векторов не дошел к сожалению, не могу ничего сказать
Вот и я не дошел :-). Но зато, изучая вопрос нашел что его можно решить с помощью алгоритма Дейкстера. Я написал пример, но чтобы не вводить данные использовал массивы заранее заданного размера на 5 точек. и сразу задаю координаты, но вот не задача все работает но как только меняешь координаты теряюсь в результате может кто доработает этот код и укажет на ошибку, проверки сделаны чисто для пользователя в дальнейшем я их удалю. ВОт гляньте кто нибудь код,где ошибки , почему нормально не работает.
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
#include <iostream.h>
#include <math.h>
 
 
const int KolT=5;//количество точек
///////////////////////////////////
void main()
{
    double X[]={1,2,3,4,5}, Y[]={1,1,1,1,1},//координаты точек
           MasDl[KolT][KolT],//массив для хранения матрицы длин
           DlToch[KolT],//массив куда копируются длины от текущей точки до всех остальных
           Dlin, Dt, 
           NToch[KolT];//массив хранящий последовательность номеров точек
    int j=0,i=0,k=0;
    unsigned long int Max;// бесконечно большое число
    bool IndT[KolT];// массив индикатор прошли точку 1 или нет 0
//////////////////показываем какие у нас координаты/////////////////
    cout << "Vvedennie coord:\n";
        for(i=0; i<KolT; i++)
        {
            cout <<"Tochka "<<i+1<<": X="<<X[i]<<"Y="<<Y[i]<<"\n";
            for (j=0;j<KolT;j++)
            {
            Dlin=sqrt(((X[i]-X[j])*(X[i]-X[j]))+((Y[i]-Y[j])*(Y[i]-Y[j])));//находим расстояния между точками
 
                if(Dlin!=0)// если не 0 записываем в массив матрицы длин
                {
                MasDl[i][j]=Dlin;
                }
                else // иначе приравниваем длинну к бесконечно большой
                {
                MasDl[i][j]=Max;
                }
 
            }
        }
        cout<<"\n";
/////////////////проверка матрицы длин///////////////
cout<<"Matrica Dlin megdu tochkami\n";
 
    for (i=0;i<KolT;i++)
    {
        for (j=0;j<KolT;j++)
        {
        
        cout << MasDl[i][j]<<"   ";
        }
    cout<<"\n";
    }
    cout<<"\n";
/////////////////проверка массива индикатора и обнуление его///////////////
    cout<<"Massiv Indikator"<<"\n";
    for (i=0;i<KolT;i++)
    {   
        IndT[i]=0;
        cout << IndT[i]<<" ";
    }
    cout<<"\n";
////////////////////////////////
////////////////подготовка данных////////////////
    for (i=0;i<KolT;i++)
    {
        NToch[i]=i;cout<<"Tochka:"<<NToch[i]<<" ";// номер  точки
        IndT[i]=0;cout<<"Ee indikator:"<<IndT[i]<<" ";//обнуление (еще раз ну это можно удалить)
        DlToch[i]=MasDl[i][0];cout<<"Perv znac:"<<DlToch[i]<<" \n";//первая длинна текущей точки
    }
////////////////Поиск кратчайшего пути////////////////
    NToch[0]=0;//задаем начало
    IndT[0]=1;
    Dt=Max;// минимальная длина делаем ее большой
    cout<< "Posled tochek:";
    for(i=0;i<(KolT-1);i++)
    {
        Dt=Max;
        for (j=0;j<KolT;j++)
        {
        if((IndT[j]==0)&&(Dt>DlToch[j]))// сравниваем и ищем минимальную длинну для точки
        {
            Dt=DlToch[j];
            k=j;//запоминаем близ лежащую точку
        }
 
        IndT[k]=1;// меняем индикатор длижней точки на пройденную
        if((IndT[j]==0)&&(DlToch[j]>(DlToch[k]+MasDl[k][j]))) //еще раз смотрим массив на наличие блжайшей точки и сравниваем расстояние уже с найденной
        {
            DlToch[j]=DlToch[k]+MasDl[k][j];
            NToch[j]=k;//запоминаем номер
        }
        }
        cout<<NToch[k]<<" "; //вывод точек как они связываются
    }
 
    
    cout<<"\nMinimalnoe rasstoyanie: "<<Dt<<"\n";// вывод мин.расстояния
////////////////////////////////
    cout<<"Massiv Indikator"<<"\n";
    for (i=0;i<KolT;i++)
    {   
        cout << IndT[i]<<" ";//проверим индикатор все ли точки прошли
    }
    cout<<"\n";
////////////////////////////////
}
Кстати я планирую вывод графика на OpenGL сделать может кто сразу до ума доведет прогу :-)))

Добавлено через 2 минуты
И еще если код пишите хоть какой нибудь коммент вставляйте, ведь уровень у всех разный. Заранее спасибо:-)))

Добавлено через 2 минуты
Цитата Сообщение от Mr.X Посмотреть сообщение
Не знаю, у меня в Visual Studio нормально работает.
Что у всех эта прога работает? :-((( Я что один такой у которого ошибки
0
Эксперт С++
2343 / 1716 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:39 11
Цитата Сообщение от SergProgC++ Посмотреть сообщение
Что у всех эта прога работает? :-((( Я что один такой у которого ошибки
Что за среду используете?
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
02.08.2010, 21:41  [ТС] 12
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Что за среду используете?
Microsoft Visual C++ 6.0 и Windows 7

это у меня или я не так понимаю?:-(
0
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
02.08.2010, 21:45 13
Цитата Сообщение от SergProgC++ Посмотреть сообщение
изучая вопрос нашел что его можно решить с помощью алгоритма Дейкстера.
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Или это именно Дейкстер О_о ?
0
Эксперт С++
2343 / 1716 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 21:45 14
Цитата Сообщение от SergProgC++ Посмотреть сообщение
Microsoft Visual C++ 6.0
Эта среда устарела и не поддерживает ни один из стандартов С++ (только проект C++98), поэтому и ошибки. Скачайте более новую версию MSVS (минимум 2005), подойдет и Express версия. Ссылку на скачивание можете узнать в теме Бесплатные среды(IDE) для программирования на С/С++.
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
02.08.2010, 22:09  [ТС] 15
Цитата Сообщение от Хохол Посмотреть сообщение
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Так может другой алгоритм предложете? Вместе и обдумаем!

Добавлено через 2 минуты
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Эта среда устарела и не поддерживает ни один из стандартов С++ (только проект C++98), поэтому и ошибки. Скачайте более новую версию MSVS (минимум 2005), подойдет и Express версия. Ссылку на скачивание можете узнать в теме Бесплатные среды(IDE) для программирования на С/С++.
Понимаете среда должна быть эта и не каких шаблонов использовать нельзя, Мне вообще ее показывать на Borland C++ 3.0

Добавлено через 2 минуты
Цитата Сообщение от Хохол Посмотреть сообщение
SergProgC++, ваша задача к алгоритму Дейкстры никакого отношения не имеет.
Или это именно Дейкстер О_о ?
Я так понял длины это веса ребер, точки задаются координатами, отсюда следует что это граф, вот почему этот алгоритм использую :-)) но если предложите свой не обижусь. А лучше и реализацию посмотреть:-)))

Добавлено через 4 минуты
Очень прошу пишите по теме, че вокруг да около ходим, то среду обсуждаем то че такое вектор :-(((

Добавлено через 12 минут
Извиняюсь но у меня иногда ощущение складывается что, одни знают о чем говорят,а другим лишьбы че нить ляпнуть:-)))
0
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
02.08.2010, 22:17 16
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
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
ifstream fin("input.txt");
ofstream fout("output.txt");
 
struct point
{
    int x, y;
    bool operator < (const point &p)
    {
        return x < p.x || x == p.x && y < p.y;
    }
};
 
#define sqr(x) ((x)*(x))
 
double dist(const point &a, const point &b)
{
    return sqrt(double(sqr(a.x-b.x) + sqr(a.y-b.y)));
}
 
int main()
{
    int n;
    fin >> n;
    vector<point> v(n);
    for(int i = 0; i < n; i++)
        fin >> v[i].x >> v[i].y;
    sort(v.begin(),v.end());
    vector<point> ans(n);
    double mi = 987654321;
    do {
        double len = 0;
        for(int i = 0; i < n-1; i++)
            len += dist(v[i],v[i+1]);
        if(len < mi)
        {
            mi = len;
            ans = v;
        }
    }while(next_permutation(v.begin(),v.end()));
    for(int i = 0; i < n; i++)
        fout << ans[i].x << ' ' << ans[i].y << endl;
}
То же самое что у Mr.X только попроще написано.
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
02.08.2010, 22:22  [ТС] 17
Цитата Сообщение от Хохол Посмотреть сообщение
То же самое что у Mr.X только попроще написано.
Ох только же говорил что шаблоны нельзя и в MVC++ 6 опять ошибка но я ее исправил и она тупо вылетает после запуска (У тебя i инициализированно два раза типом int) кстати вы их проверяете :-((( или так пишите

47 строка ошибка ;-)

кстати кода копируешь код с другого сайта хоть проверяйте :-)) я его уже видел , но не тут
 Комментарий модератора 
SergProgC++, уважайте людей, которые пытаются Вам помочь, а не обвиняйте.
0
Эксперт С++
2343 / 1716 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:32 18
SergProgC++, приведите конкретные сообщения об ошибках.
0
Эксперт GPSS
548 / 409 / 103
Регистрация: 02.07.2010
Сообщений: 1,703
02.08.2010, 22:34  [ТС] 19
ЛАдно и звиняюсь может и не с другого просто знакомый до боли

1.cpp(47) : error C2374: 'i' : redefinition; multiple initialization
warning C4508: 'main' : function should return a value; 'void' return type assumed
0
Эксперт С++
2343 / 1716 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
02.08.2010, 22:48 20
SergProgC++, код приведенный Хохол корректен c точки зрения текущего стандарта C++ (warning не в счет). Проблема в том, что вы используете устаревшую среду, которой практически никто не пользуется. Подгоняйте код под свою IDE.
Цитата Сообщение от Хохол Посмотреть сообщение
C++
1
int n;
замените на:
C++
1
int n, i;
Обе строки:
Цитата Сообщение от Хохол Посмотреть сообщение
C++
1
for(int i = 0; i < n; i++)
замените на:
C++
1
for(i = 0; i < n; i++)
В конце функции main вставьте:
C++
1
return 0;
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.08.2010, 22:48
Помогаю со студенческими работами здесь

Проложить маршрут
Народ, подскажите или дайте ссылку ибо у самого найти не получается. Есть четырехэтажное здание,...

Как правильно проложить маршрут?
у меня dhcp сервер. У него 2 интерфейса. у первого 10.1.3.1 , у второго 12.1.3.1 - ip. и 2 ПК...

Проложить маршрут из одной клетки в другую
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из...

Отрисовать набор точек в трехмерной системе координат (с возможностью вращения)
Подскажите, как отрисовать набор точек в трехмерной системе координат с возможностью вращения.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru