Визначення найкоротшого маршрутe руху автомобіля від поштового відділення до пункту призначення
Розробка менеджером по організації поштових перевезень найкоротшого маршрут руху автомобіля від поштового відділення А до В, використовуючи мережу автомобільних шляхів, яка задана у вигляді графа. Визначення довжини дуги відповідно до відрізка дороги.
| Рубрика | Математика |
| Вид | задача |
| Язык | украинский |
| Дата добавления | 08.08.2009 |
| Размер файла | 46,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Задача
Менеджер по організації поштових перевезень повинен розробити найкоротший маршрут руху автомобіля від поштового відділення А до В, використовуючи мережу автомобільних шляхів, яка задана у вигляді графа. Довжина дуги визначається довжиною (в кілометрах) відповідно до відрізка дороги.
Застосуємо алгоритм Дейкстри до графа, для знаходження на ньому найкоротшого шляху між вершинами А і В.
Спочатку виконання помічена тільки вершина А. Крім того d(A)=0 i d(S)=? для всіх вершин, що відмінні від А.
Крок 1:
y=A; d(A)=0; d(X)=0
d(C)=min{d(C), d(A)+a(A,C)}=min{?, 0+2}=2
d(D)=min{d(D), d(A)+a(A,D)}=min{?, 0+1}=1
d(E)=min{d(E), d(A)+a(A,E)}=min{?, 0+3}=3
d(B)=min{d(B), d(A)+a(A,B)}=min{?, 0+?}=?
d(F)=min{d(F), d(A)+a(A,F)}=min{?, 0+?}=?
Крок 2:
y=D
d(C)=min{d(C), d(D)+a(D,C)}=min{2, 1+7}=2
d(F)=min{d(F), d(D)+a(D,F)}=min{?, 1+6}=7
d(E)=min{d(E), d(D)+a(D,E)}=min{3, 1+3}=3
d(B)=min{d(B), d(D)+a(D,B)}=min{?, 1+?}=?
Крок 3:
y=C
d(C)=2
d(F)=min{d(F), d(C)+a(C,F)}=min{7, 2+?}=5
d(E)=min{d(E), d(C)+a(C,E)}=min{3, 2+4}=3
d(B)=min{d(B), d(C)+a(C,B)}=min{?, 2+?}=?
Крок 4:
y=E
d(E)=3
d(F)=min{d(F), d(E)+a(E,F)}=min{?, 3+5}=5
d(B)=min{d(B), d(E)+a(B,F)}=min{?, 3+1}=4
Найкоротший шлях, що сполучає вершину А з вершиною В, складається з дуг (А,Е) і (Е,В) і має довжину 3+1=4
Подобные документы
Побудування графа та матриці інцидентності. Перетворення графа у зважений за допомогою алгоритму Дейкстри, знаходження довжини найкоротшого шляху між двома вершинами та побудування дійсного шляху. Обхід дерева у прямому та зворотному порядках.
курсовая работа [144,1 K], добавлен 03.07.2014Обчислення довжини дуги для просторової кривої, що задана параметрично. Варіант розрахунку у випадку задання кривої в полярній системі координат. Формули для обчислення площі поверхні обертання. Вираз площі циліндричної поверхні через елементарні функції.
научная работа [103,7 K], добавлен 12.05.2010Основні правила нанесення розмірів. Рекомендації з виконання креслень. Проведення паралельних і перпендикулярних ліній. Розподіл відрізка прямої на рівні частини. Побудова і розподіл кутів. Пошук центра окружності чи дуги і визначення їхніх радіусів.
практическая работа [2,4 M], добавлен 03.03.2016Метод найменших квадратів. Задача про пошуки параметрів. Означення метода найменших квадратів. Визначення параметрів функціональних залежностей. Вид нормальної системи Гауса. Побудова математичної моделі, використовуючи метод найменших квадратів.
реферат [111,0 K], добавлен 25.12.2010Зразки вирішення задач по дискретній математиці. Обчислювання череди функцій універсальних множин методами дискретної математиці. Визначення ймовірності послідовного вибору з колоди певних карт. Використання відомих алгоритмів для обчислення шляхів графа.
контрольная работа [42,1 K], добавлен 22.10.2009Суть функції багатьох змінних, її означення і символіки. Границя і неперервність функції багатьох змінних. Визначення відкритої та замкненої області. Множина точок площини, для яких задана формула має зміст, як область визначення. Функція двох змінних.
реферат [289,8 K], добавлен 01.05.2011Сутність інтерполяційних поліномів. Оцінка похибок інтерполяційних формул, їх застосування. Програма обчислення наближених значень функції у випадку, коли функція задана таблично, використовуючи інтерполяційні формули для рівновіддалених вузлів.
курсовая работа [956,4 K], добавлен 29.04.2011Розв'язання задач з теорії множин та математичної логіки. Визначення основних характеристик графа г (Х,W). Розклад функцій дискретного аргументу в ряди по базисним функціям. Побудова та доведення діаграми Ейлера-Вена. Побудова матриці інцидентності графа.
курсовая работа [988,5 K], добавлен 20.04.2012Вивчення властивостей підгрупи Фиттинга. Умова існування доповнень до окремих підгруп. Визначення нильпотентної довжини розв'язної групи. Доведення ізоморфності кінцевої нерозв'язної групи з нильпотентними додаваннями до непонадрозв'язних підгруп.
дипломная работа [198,6 K], добавлен 17.01.2011Методика визначення всіх коренів нелінійного рівняння різними способами: відрізка пополам, хорд, дотичних та ітерацій. Особливості та принципи застосування комп’ютерних технологій в даному процесі. Аналіз отаманих результатів і їх інтерпретація.
лабораторная работа [263,9 K], добавлен 15.12.2015
