ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Рішення задачі про найкоротший маршрут
         

     

    Інформатика, програмування
    Рішення задачі про найкоротший маршрут методом Форда

    1. Постановка мережевий транспортної задачі.

    На практиці часто зустрічається задача визначення найкоротшого маршруту по заданій мережі з початкового пункту до кінцевого пункту маршруту. Транспортна мережа може бути представлена у вигляді графа (рис. 1), дуги якого - транспортні магістралі, а вузли - пункти відправлення та призначення. Графічно транспортна мережа зображується у вигляді сукупності n пунктів P1, P2 ,..., Pn, причому деякі впорядковані пари (Pi, Pj) пунктів призначення з'єднані дугами заданої довжини r (Pi, Pj) = lij. Деякі чи всі дуги можуть бути орієнтовані, тобто по них можливий рух тільки в одному напрямку, зазначеному стрілками.

    На рис.1 побудована орієнтована транспортна мережа, що містить шість пунктів P1, P2 ,..., P6, які пов'язані між собою вісьмома транспортними шляхами.

    Необхідно визначити найкоротший маршрут з пункту P1 в P6. Визначення найкоротшого маршруту полягає у вказівці послідовності проходження маршруту через проміжні пункти та сумарної довжини маршруту.

    Наприклад маршрут з пункту P1 в пункт P6: P1P2P4P6; L = l12 + l24 + l46 = 10.

    Постановка завдання набуває сенсу в тому випадку, якщо є кілька варіантів маршруту з початкового пункту в кінцевий. У цьому випадку фізичний зміст функції мети завдання полягає в мінімізації загальної довжини маршруту, тобто у визначенні найкоротшого шляху з P1 в Pn.

    2. Опис методу і алгоритму рішення.

    Метод Форда бал розроблений спеціально для вирішення мережевих транспортних задач і заснований, по суті, на принципі оптимальності.

    Алгоритм методу Форда містить чотири етапи (схема 1). На першому етапі проводиться заповнення вихідної таблиці відстаней від будь-якого i-го пункту в будь-який інший j-й пункт призначення. На другому етапі визначаються для кожного пункту деякі параметри l i і l j за відповідними формулами. Далі на третьому етапі визначаються найкоротші відстані. Нарешті, на четвертому етапі визначаються найкоротші маршрути з пункту відправлення Р1 в будь-який інший пункт призначення Рj, j = 1,2 ,..., n.

    Розглянемо докладніше кожний з цих чотирьох етапів.

    2.1 Перший етап: Складання вихідної таблиці відстаней.

    Дана таблиця містить n +1 рядків і така ж кількість шпальт; Pi - пункти відправлення; Pj - пункти призначення. У другому рядку і другому стовпчику проставляється значення параметрів l i іl j, визначення значень яких виробляються на другому етапі рішення задачі. В інших клітинах таблиці проставляються значення відстаней lij з i-го пункту в j-й пункт. Причому заповнюємо клітини таблиці, що лежать вище головної діагоналі. Якщо пункт Pi не з'єднаний відрізком шляху до пункту Pj, то відповідна клітка таблиці не заповнюється.

    2.2 Другий етап: Визначення l i і l j.

    Визначається значення параметрів відповідно до формули:

    l j = min (l i + lij); i = 1,2 ,..., n; j = 1,2 ,..., n, (1)

    де l 1 = 0.

    Ці значення заповнюються в другому рядку і в другому стовпчику.

    2.3 Третій етап: Визначення довжини найкоротших шляхів.

    Можливі два випадки визначення довжини найкоротших шляхів з пунктів Pi в пункти Pj, i = 1,2 ,..., n; j = 1,2 ,..., n.

    У першому випадку, якщо виконуються нерівність:

    l j - l i

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status