ЗАДАЧА ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ
Математическая модель задачи
Рассмотрим ориентированный граф: , в котором конечное множество вершин, -конечное множество дуг, -весовая функция дуг, интерпретируется как длина участка.
Длина любого маршрута в графе равна сумме весов дуг, входящих в этот маршрут.
Дополнительно в графе фиксируются две вершины: начальная - , и конечная- . В предположении, что исходный граф связный, требуется определить маршрут минимальной длины из начальной вершины в конечную.
Вводим булевы переменные , которые интерпретируются следующим образом.
Переменная если входит в искомый маршрут минимальной длины, и в противном случае, т.е. если дуга не входит в оптимальный маршрут.
Тогда, целевая функция задачи принимает следующий вид:
- Курсовая работа
- Дипломная работа
- Контрольная работа
- Реферат
- Отчет по практике
- Магистерская работа
- Статья
- Эссе
- Научно-исследовательская работа
- Доклад
- Глава диплома
- Ответы на билеты
- Презентация
- Речь к диплому
- Тезисный план
- Чертёж
- Диаграммы, таблицы
- ВАК
- Перевод
- Научная статья
- Бизнес план
- Лабораторная работа
- Рецензия
- Решение задач
- Диссертация
- Доработка заказа клиента
- Аспирантский реферат
- Монография
- Дипломная работа MBA
- ВКР
- Компьютерный набор текста
