Метод ветвей и границ для задачи коммивояжера

Автор работы: Пользователь скрыл имя, 24 Мая 2013 в 14:31, курсовая работа

Краткое описание

Дана задача коммивояжера в классической формулировке: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходный пункт. Кратчайший маршрут находится полным переборомбез учета повторяющихся путей (например, 1-2-3-1 и 2-3-1-2). При этом на плоскости полученный маршрут является границей многоугольника.

Содержание

1.Постановка задачи…………………………………………………..... 3
2. Математические основы решения задачи коммивояжера
2.1. Формулировка и некоторые свойства решений задачи коммивояжера…………………………………………………………….……
2.2. Постановка задачи коммивояжера как задачи на графе...…………………………………………..……………………………….
4
6
3. Постановка и описание алгоритма решения задачи
3.1. Алгоритм решения задачи…………………..……………….….
3.2. Оценка трудоемкости…………………………………………….
3.3. Результаты выполнения программы……………………………. 7
8
9
Приложение………………………………………………………………. 13
Литература………………………………………………………………… 17

Скачать в ZIP архиве (63.33 Кб) Сколько стоит заказать работу?
Вложенные файлы: 1 файл

Курсовая.docx

— 70.05 Кб (Скачать файл)

            [d_f,pi_1]=exchangе(pi0,d);% вызов метода ветвей и границ

            r_r=rand;

            if d_f<0

                pi0=pi_1;

            elseif exp(-d_f/t)>r_r

                pi0=pi_1;

            else

                pi0=pi0;

            end

        end

        f_temp=0;

        for k=1:(n-1)

            f_temp=f_temp+d(pi0(k),pi0(k+1));

        end

        f_temp=f_temp+d(pi0(n),pi0(1));

        if min_f>f_temp % выбор наикратчайшего пути

              min_f=f_temp;

              p_min=pi0;

          end

          t=a*t;

      end

      f=min_f;

      T=p_min;

    

 function [d_f,pi_r]=exchange(pi0,d)% метод ветвей и границ

      [m,n]=size(d);

      u=rand; % задаем произвольное число

      u=u*(n-2);

      u=round(u);% округляем число в сторону ближайшего целого

      if u<2

          u=2;

      end       

      if u>n-2

          u=n-2;

      end

      v=rand;

      v=v*(n-u+1);

      v=round(v);       

      if v<1

          v=1;

      end

      v=u+v;      

      if v>n

          v=n;

      end

      pi_1(u)=pi0(v);

      pi_1(v)=pi0(u);      

      if u>1

          for k=1:(u-1)

              pi_1(k)=pi0(k);

          end

      end       

      if v>(u+1)

          for k=1:(v-u-1)

              pi_1(u+k)=pi0(v-k);

          end

      end       

      if v<n

          for k=(v+1):n

              pi_1(k)=pi0(k);

          end

      end

      d_f=0;      

      if v<n % отсечение неоптимальных решений

          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));

          for k=(u+1):n

              d_f=d_f+d(pi0(k),pi0(k-1));

          end

          d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));

          for k=(u+1):n

              d_f=d_f-d(pi0(k-1),pi0(k));

          end

      else

          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));

          for k=(u+1):n

              d_f=d_f+d(pi0(k),pi0(k-1));

          end

          for k=(u+1):n

              d_f=d_f-d(pi0(k-1),pi0(k));

          end

      end

      pi_r=pi_1;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЛИТЕРАТУРА

 

  1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2004.-208с.
  2. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 с.
  3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002.-208с.
  4. Просветов Г.И. Математические методы в экономике: Учебно – методическое пособие. – М.: Издательство РДЛ, 2004.-160с.
  5. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.-479с.

 


Информация о работе Метод ветвей и границ для задачи коммивояжера