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

Жадный алгоритм для определения последовательности обхода городов. - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 5.00
Taymyr
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 7
05.01.2011, 16:48     Жадный алгоритм для определения последовательности обхода городов. #1
Здравствуйте! Изучаю разные транспортные алгоритмы и возник следующий вопрос.

На основе данных, полученных из txt-файла формирую двумерный массив: матрицу смежности ras[i][j], в которой хранятся расстояния между городами. Пытаюсь применить жадный алгоритм для составления последовательности обхода городов. В 0-й строке ищу минимальный элемент, запоминаю индекс в массив mashrut[n] и перехожу в строку с этим индексом. Там снова ищу минимальный элемент и т.д. После того, как нашёл минимальный элемент в строке - зануляю весь его столбец (всё равно в эту вершину больше заходить не будем). И ищу дальше. Но последовательность всё равно выдаёт неверную - 1, 2, 3, 4, 5. Вместо 1, 3, 5, 2, 4. Подскажите пожалуйста!



Добавлено через 46 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(j=0;j<kolvo;j++)
{       double mvstr=1000;
        if(ras[i][j]<mvstr && ras[i][j]!=0)
        {
            mvstr=ras[i][j];
            printf("%lf !!", mvstr);
            marshrut[n]=j;
            i=j;
            int stolbec=j;
            n++;
            for(int ii=0; ii<kolvo; ii++)
            {
                ras[ii][stolbec]=0;
            }
        }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2011, 16:48     Жадный алгоритм для определения последовательности обхода городов.
Посмотрите здесь:

Жадный алгоритм C++
C++ Жадный алгоритм
Алгоритм обхода лабиринта C++
Составить алгоритм определения последовательности номеров удаляемых спортсменов C++
C++ Жадный алгоритм на графе
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alloyr
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 8
25.11.2012, 10:35     Жадный алгоритм для определения последовательности обхода городов. #21
valeriikozlov, пришли мне, пожалуйста, улучшенную задачу коммивояжера с помощью жадного алгоритма, которое должно находить кратчайший путь по заданным городам и сумму найденного пути.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2012, 21:43     Жадный алгоритм для определения последовательности обхода городов. #22
Цитата Сообщение от alloyr Посмотреть сообщение
valeriikozlov, пришли мне, пожалуйста, улучшенную задачу коммивояжера с помощью жадного алгоритма, которое должно находить кратчайший путь по заданным городам и сумму найденного пути.
а чем не нравится код из 12 поста?
Сумму найденного пути очень элементарно там найти (вставить этот кусок нужно перед выводом пути):
C++
1
2
3
4
5
6
7
8
9
int sum=0;
if(N>1)
{
    sum+=mas[0][mas_res[0]];
    for(i=0; i<N-2; i++)
        sum+=mas[mas_res[i]][mas_res[i+1]];
    sum+=mas[0][mas_res[N-2]];
}
// здесь в переменной sum нужное значение
alloyr
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 8
26.11.2012, 19:33     Жадный алгоритм для определения последовательности обхода городов. #23
valeriikozlov, Моя задача с N городами (желательно 5 городов) и в ответе путь коммивояжера должен быть 1-5-3-4-2-1 и сумма пути 13 - вот что требуется для улучшения задачи. Прошу мне сегодня прислать улучшенную (модифицированную) задачу . Буду благодарен.
alloyr
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 8
27.11.2012, 20:46     Жадный алгоритм для определения последовательности обхода городов. #24
valeriikozlov, Был у преподавателя программа почти правильна, только должна работать не из клавиатуры, а из файла (создать input.txt - потом появится output.txt)(таково условие преподавателя). Поэтому решенную задачу (кому нибудь пригодится) прикладываю здесь - путь коммивояжера начинается с 1 города (5 городов), ответ таков: путь 1-5-3-4-2-1 и сумма пути 13. Матрица стоимостей такова:

100 1 2 7 5
1 100 4 4 3
2 4 100 1 2
7 4 1 100 3
5 3 2 3 100

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
#pragma once
 
#define WIN32_LEAN_AND_MEAN     // Exclude rarely-used stuff from Windows headers                       
 
#include <stdio.h>
#include <conio.h>
#include <fstream>
#include <tchar.h>
#include <iostream> // заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++
using namespace std; // Если поместить using namespsce std; то все последующие операторы будут брать переменные и ф-ции из области std
 
 
 
Ход выполнения задачи:
 
#include "stdafx.h"
 
void print_matr(int**a,int n )
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cout.width(4);
            cout<<a[i][j];
        }
        cout<<'\n';
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
     setlocale(LC_CTYPE, "russian"); // использование библ-ки русского языка
     ifstream fin;
     ofstream fout;
     int N, **mas, i, j, *mas_res, res=0, min, tmp=1, sum=0; // обычное заполнение массива.
     bool *mas1;
     fin.open("input.txt");
     fout.open("output.txt");
     fin>>N;
     cout<<N<<'\n';
     mas=new int*[N];
     for (i=0; i<N; i++)
         mas[i]=new int[N];
     mas_res=new int[N-1];
     mas1=new bool[N];
     for (i=0; i<N; i++)
        mas1[i]=false;
     for( i=0; i<N; i++) // Берется N-ый город
           for( j=0; j<N; j++) // и заполняется расстояние между ним и остальными городами
           {
               fin>>mas[i][j];
           }
     print_matr(mas,N);
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            fout.width(4);
            fout<<mas[i][j];
        }
        fout<<'\n';
    }
 
      mas1[0]=true;
      for(i=0; i<N-1; i++) // цикл по городам
           {
              min=-1; // начальное значение минимума
              for(j=0; j<N; j++) // цикл по расстояниям между городом, из вышенаписанного цикла и остальными городами
                   if(!mas1[j] && mas[tmp][j]>0) // !mas1[j] - если город j еще не посещали и mas[tmp][j]>0 - путь из города в котором находимся tmp в город j есть
                     {
                              if(min==-1) min=j;// если минимум равен -1, то минимум присвоить индексу
                                                // если не -1, то сравниваем значения и ищем минимальное среди них
                              else
                              { // ну тут считаем все делается аналогично циклу заполнение расстояний
                                // только тут вместо того, чтобы вводить значения в массивы между городами,
                                // их тут сравнивают. берут расстояние между первым и второым городом и сравнивается с 1ым и 3им.
                                // потом 1ым и 4ым и так далее. Увеличили i, город уже стал вторым и заново пошел цикл. Между 2ым и 3им городом
                                // т.к. между 2ым и 1ым городом сравнение было б на предыдущем этапе, когда i=1 (ну 1ый город со 2ым сравнивали). 
                                // смысл еще раз сравнивать 2ой с 1ым)) 
                                   if(mas[tmp][j]<mas[tmp][min])
                                              min=j;
                              }
                      }
              mas_res[res++]=min;// записали это минимальное расстояние
                                 // перед этим нашли, что самый короткий путь из вершины где сейчас находимся tmp лежит в врешину с индексом min
              mas1[min]=true; // помечаем вершину min как пройденную
              tmp=min;  // считаем что вершина где сейчас находимся - вершина с индексом min (переходим из вершины tmp в вершину min)
 
                }
      cout<<"Получен путь: \n";
      cout<<"1 "; // исходный город (начало пути коммивояжера)
      for(i=0; i<N-1; i++) // обычный вывод результирующего массива (по городам)
      cout<<mas_res[i]+1<<" ";
      cout<<"1 \n"; // возвращение коммивояжера к исходному городу
      cout<<"Получена сумма пути: \n";
      fout<<"Получен путь: \n";
      fout<<"1 "; // исходный город (начало пути коммивояжера)
      for(i=0; i<N-1; i++) // обычный вывод результирующего массива (по городам)
       fout<<mas_res[i]+1<<" ";
      fout<<"1 \n"; // возвращение коммивояжера к исходному городу
      fout<<"Получена сумма пути: \n";
      if(N>1)
      {
      sum+=mas[0][mas_res[0]]; 
      for(i=0; i<N-2; i++) // обычный вывод результирующего массива (по расстояниям)
      sum+=mas[mas_res[i]][mas_res[i+1]];
      sum+=mas[0][mas_res[N-2]];
      }
      cout<<sum<<" \n";
      fout<<sum<<" \n";
      fout.close();
    return 0;
}
Валерий, я очень прошу тебя помочь мне - моя задача такая же, только путь коммивояжера начинается со 2 города и придумать квадратную матрицу 5(i) на 5(j)(i-строка, j-столбец) (придумать матрицу-образец смотреть выше), следовательно путь и сумма пути будут другими. Программа также должна работать из файла input.txt(в этом файле создать матрицу). Очень прошу в каждой строке программы дать очень подробный комментарий-что это и что там такое. Буду благодарен.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.11.2012, 06:06     Жадный алгоритм для определения последовательности обхода городов. #25
Цитата Сообщение от alloyr Посмотреть сообщение
программа почти правильна, только должна работать не из клавиатуры, а из файла (создать input.txt - потом появится output.txt)(таково условие преподавателя).
Я понимаю эту фразу так, что вводить данные из файла input.txt , а выводить результат в файл output.txt.

Цитата Сообщение от alloyr Посмотреть сообщение
только путь коммивояжера начинается со 2 города и придумать квадратную матрицу 5(i) на 5(j)(i-строка, j-столбец) (придумать матрицу-образец смотреть выше)
Со второго так со второго. Насчет придумывания матрицы: это значит что Вы сами до запуска программы записываете матрицу в файл input.txt. И я так понимаю что матрица всегда размером 5*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
#include<iostream>
using namespace std;
#define n 5
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int N, mas[n][n]={0}, i, j, mas_res[n-1], res=0, min, tmp=0;
    bool mas1[n]={false};
    N=5;
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
        {           
            cin>>mas[i][j];         
        }
    mas1[1]=true;
    for(i=0; i<N-1; i++)
    {
        min=-1;
        for(j=0; j<N; j++)
            if(!mas1[j] && mas[tmp][j]>0)
            {
                if(min==-1) min=j;
                else
                {
                    if(mas[tmp][j]<mas[tmp][min])
                        min=j;
                }
            }
        mas_res[res++]=min;
        mas1[min]=true;
        tmp=min;
    }
    cout<<"Poluchen put:"<<endl;
    cout<<"2 ";
    for(i=0; i<N-1; i++)
        cout<<mas_res[i]+1<<" ";
    cout<<"2 "<<endl;
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2012, 18:58     Жадный алгоритм для определения последовательности обхода городов.
Еще ссылки по теме:

Жадный граф/алгоритм C++
Существует N городов для каждой пары городов (і, j) можно построить путь C++
C++ Жадный алгоритм С++

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

Или воспользуйтесь поиском по форуму:
alloyr
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 8
28.11.2012, 18:58     Жадный алгоритм для определения последовательности обхода городов. #26
valeriikozlov, ты сделай задачу так же, как я выложил в 24 пост, а то твое решение хоть и правильное, но преподавателю это не нравится - что такое и чем характеризуются: mas[n][n]={0}(оно не нужно по мнению преподавателя), res=0, tmp=0, min, bool mas1[n]={false}, #define n 5(оно не нужно по мнению преподавателя). Вообще сделай так как я выложил в 24 пост и прошу к каждой строке дать понятные комментарии и программа должна работать из файла и со второго города(смотреть мои условия в пост 24).
Yandex
Объявления
28.11.2012, 18:58     Жадный алгоритм для определения последовательности обхода городов.
Ответ Создать тему
Опции темы

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