Читать курсовая по Отсутствует: "Решение задачи коммивояжера с помощью алгоритма Дейкстры" Страница 1

(Назад) (Cкачать работу)

Введение В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.

Задача коммивояжёра актуально и по сей день т.к. люди ищут кратчайшие пути и затраты на эти кратчайшие пути.

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

Задачи курсового проекта:

) Составить математическую модель;

) Разработать схему алгоритма;

) Составить программный код;

) Провести анализ полученных результатов.

1. Постановка задачи Определить длину (Q) кратчайшего маршрута (L) коммивояжера.

Расстояния (Qij) между шестью городами представлены в таблице 1. Таблица 1 - Условие задачи

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

2. Этапы решения задачи .1 Математическая модель Построим математическую модель:

n - число городов.

Xi j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.

Xi j - матрица переходов с компонентами:

Xi j = -1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1..N и i¹j.

Критерий: , (1)

где Сij - матрица стоимости переходов,

Xij - матрица переходов, где xij=0, если переход совершен и xij=1 в противном случае

Ограничения:, i = 1..N (2)

, j = 1..N (3)

Ui - Uj + N × Xi j £ N-1, i, j = 1..N, i ¹ j. (4)

, k= 1..N,t=k-1 (5)

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель; условие (5) - принцип треугольника: ранее выбранный путь оказался длиннее предыдущего. .2 Разработка алгоритма Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы. В данном курсовом проекте реализуется задача коммивояжера методом алгоритма Дейкстры.

В 1959 г. Голландский математик Дейкстра предложил

Похожие работы