VPF::Помогите понять код задачи коммивояжера

AlexeroN

Дата 24.4.2010, 19:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 10.11.2009
Где: Екатеринбург

Репутация: нет
Всего: нет

Всем доброго времени суток. Дали задание в универе по задаче коммивояжера. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый) и соответствующие матрицы расстояний, стоимости и т. п. Код нашел на DMTsoft.ru, самому написать было бы трудно, к вам обращаюсь за помощь помочь понять что и к чему, непонятки я обозначил "//?". Пжл, если согласитесь откоментировать укажите номер строки или диапазон

Код


#include <stdlib.h>
      #include <time.h>
      #include <stdio.h>
       
      int wpchk(int w, int *wpts)
      {
      int i=0;
      int flg=0;
      while(wpts[i]!=-1)//?
      {
      if(wpts[i]==w){flg=1;}//?
      i++;
      }
      if (flg==0) {return 0;} else return 1;
      }
      void main()
      {
      srand( (unsigned)time( NULL ) );//?
      //int prices[10][10];
      int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1};//?
      int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};//?
      int start=-1;
      int end=-1;
      int min;
      int imin;
       
                             // 0 1 2 3 4 5 6 7 8 9
      int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0
                                     0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1
                                     0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2
                                    0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3
                                    0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4
                                    0, 0, 20,4, 11,0, 0, 0, 0, 0, //5
                                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6
                                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7
                                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8
                                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9       
printf("Enter № of start location:");
scanf("%i", &start);
printf("Enter № of finish location : ");
scanf("%i", &end);
waypoint[0] =start;
int n = 0;
int w;
while(waypoint[n] != end)
{
min = 0;
w = waypoint[n];//?
for(int i = 0;i < 10;i++)
{ 
if (((min == 0) || ((prices[w][i] < min) && (prices[w][i] > 0))) && wpchk(i,waypoint) == 0)//?
{min = prices[w][i]; imin = i ;}
}
n++;
waypoint[n] = imin;}
printf("\nThe way is:\n");
int i = 0;
while (waypoint[i] != -1)
{
printf("%i", waypoint[i]);
i ++;
}
getchar();
getchar();
}

Это сообщение отредактировал(а) AlexeroN - 30.4.2010, 20:06

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »