Статья опубликована в рамках: XX Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 15 мая 2014 г.)

Наука: Математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Зенг В.А. МЕТОД МОНТЕ-КАРЛО ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XX междунар. студ. науч.-практ. конф. № 5(20). URL: http://sibac.info/archive/technic/5(20).pdf (дата обращения: 17.10.2019)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

МЕТОД  МОНТЕ-КАРЛО  ДЛЯ  РЕШЕНИЯ  ЗАДАЧИ  КОММИВОЯЖЁРА

Зенг  Валерия  Андреевна

студент  3  курса,  кафедра  «Дизайн  и  технологии  медиаиндустрии»  ОмГТУ,  РФ,  г.  Омск

E -mailvaleriyazeng@mail.ru

Степанов  Владимир  Николаевич

научный  руководитель,  канд.  физ.-мат.наук,  доцент  каф.«Высшая  математика»  ОмГТУ,  РФ,  г.  Омск

 

Задача  коммивояжёра  является  классической  задачей  дискретной  оптимизации  и  имеет  многочисленные  приложения:  транспортные  задачи,  задачи  соединения  пунктов  линией  электропередач  и  т.  д.  Задача  коммивояжера  состоит  в  следующем:  он  должен  объехать  ряд  населенных  пунктов,  пробыв  в  каждом  пункте  только  один  раз  и  вернуться  в  исходный  пункт.  Какой  маршрут  должен  выбрать  коммивояжёр,  чтобы  пройденный  путь  был  наименьшей  длины?  [1,  с.  59].

Решение  задачи  коммивояжера  методом  Монте-Карло  строится  на  случайном  выборе  каждого  следующего  города,  через  который  будет  проходить  путь.  При  использовании  программы  ответ  носит  вероятностный  характер  и  может  сильно  отличаться  от  правильного  решения  задачи  коммивояжера.  Но  при  увеличении  числа  испытаний  погрешность  ответа  уменьшается  [2,  с.  395].

 

Рисунок  1.  Внешний  вид  программы

 

Пусть  имеется  полный  граф  с  n  вершинами,  заданный  матрицей  расстояний  С  =  ||сij||.  Вершину  v1  примем  за  начальную  и  случайным  образом  выберем  остальные  вершины  [1,  с.  80]  В  программе  это  выглядит  так: 

        {

                int  N;

                  public  Form1()

                {

                        InitializeComponent();

                }

private  void  numericUpDown1_ValueChanged(object  sender,  EventArgs  e)

                {

                        N  =  (int)numericUpDown1.Value;

                        dataGridView1.RowCount  =  N;

                        dataGridView1.ColumnCount  =  N;

                        for  (int  i  =  0;  i  <  N;  i++)

                        {

                                dataGridView1.Rows[i].HeaderCell.Value  =  ""  +  (i  +  1);

                                dataGridView1.Columns[i].HeaderText  =  ""  +  (i  +  1);

                        }

                }

private  void  button1_Click(object  sender,  EventArgs  e)

{

                        Random  r  =  new  Random();

                        for  (int  i  =  0;  i  <  N;  i++)

                                for  (int  j  =  0;  j  <  N;  j++)

                                        dataGridView1[i,  j].Value  =  r.Next(0,  10);

                }

private  void  button2_Click(object  sender,  EventArgs  e)

                {

                        double[,]  A  =  new  double[N,  N];

                        for  (int  i  =  0;  i  <  N;  i++)

                                for  (int  j  =  0;  j  <  N;  j++)

                                        A[i,j]  =  Convert.ToDouble(dataGridView1[j,  i].Value);

 

                        textBox1.Text  =  "";

                        Random  r  =  new  Random();

                        int  M  =  (int)numericUpDown2.Value;

                        progressBar1.Maximum  =  M-1;

                        double  sumbest  =  double.PositiveInfinity;

                        int[]  pbest  =  new  int[N];

                        for  (int  m  =  0;  m  <  M;  m++)

{

                                int[]  p  =  new  int[N];

                                for  (int  i  =  0;  i  <  N;  i++)

                                        p[i]  =  i;

for  (int  i  =  1;  i  <  N;  i++)

                                {

                                        int  j  =  r.Next(1,  N);

                                        int  t  =  p[i];

                                        p[i]  =  p[j];

                                        p[j]  =  t;

                                }

Предположим,  что  остальные  вершины  появились  в  порядке  i1  i2  i3  in  где  ik  —  номер  вершины  при  k-ом  выборе.  Получим  гамильтонов  контур:

 

 

Посчитаем  длину  этого  контура  и  запомним  ее.  Повторим  эту  процедуру  еще  раз  и  сравним  полученные  результаты,  выбрав  наименьший,  и  запомним  только  его  [1,  с.  80].  В  нашей  программе  это  выглядит  так:

if  (sum  <  sumbest)

                                {

                                        sumbest  =  sum;

                                        pbest  =  p;

                                }

progressBar1.Value  =  m;

                        }

                        textBox1.Text  =  textBox1.Text  +  "Минимальный  путь:  1";

                        for  (int  i  =  1;  i  <  N;  i++)

                                textBox1.Text  =  textBox1.Text  +  "->"  +  (pbest[i]  +  1);

                        textBox1.Text  =  textBox1.Text  +  "\r\nСуммарное  расстояние:  "  +  sumbest  +  "\r\n";

                }

private  void  Form1_Load(object  sender,  EventArgs  e)

                {

                        numericUpDown1_ValueChanged(sender,  e);

                        button1_Click(sender,  e);

                }

        } 

                                double  sum  =  0;

                                for  (int  i  =  0;  i  <  N  -  1;  i++)

                                        if  (A[p[i],  p[i  +  1]]  ==  0  ||  sum  >  sumbest)

                                        {

                                                sum  =  double.PositiveInfinity;

                                                break;

                                        }

                                        else

                                                sum  =  sum  +  A[p[i],  p[i  +  1]];

if  (A[p[N  -  1],  p[0]]  ==  0)

                                        sum  =  double.PositiveInfinity;

                                else

                                        sum  =  sum  +  A[p[N  -  1],  p[0]];

                                if  (sum  <  sumbest)

                                {

                                        sumbest  =  sum;

                                        pbest  =  p;

                                }

В  заключение,  хотелось  бы  добавить,  что  вышеприведенный  алгоритм  был  протестирован  по  следующим  параметрам:  количество  городов,  количество  попыток  и  количество  верных  ответов  при  прохождении  программы  100  раз. 

Данные  занесены  в  таблицу: 

Таблица  1.

Результаты  тестирования  алгоритма

Номер  варианта

Количество  городов

Количество  попыток

Количество  правильных  ответов,  %

1

6

10

9

100

48

1000

100

2

10

8

100

65

1000

100

3

10

11

100

63

1000

100

 

Основываясь  на  результатах,  представленных  в  таблице,  можно  сделать  вывод  о  том,  что  применение  метода  Монте-Карло  дает  оптимальное  решение  в  большинстве  случаев,  если  количество  попыток  превосходит  1000. 

 

Список  литературы:

1.Акимов  О.Е.  Дискретная  математика.  Логика,  группы,  графы.  М.:  Лаборатория  базовых  знаний,  2003.  —  376  с.

2.Степанов  В.Н.  Дискретная  математика:  графы  и  алгоритмы  на  графах.  Омск:  Издательство  ОмГТУ,  2010.  —  116  с. 

Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий