🗊Презентация Задача коммивояжера

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Задача коммивояжера, слайд №1Задача коммивояжера, слайд №2Задача коммивояжера, слайд №3Задача коммивояжера, слайд №4Задача коммивояжера, слайд №5Задача коммивояжера, слайд №6Задача коммивояжера, слайд №7Задача коммивояжера, слайд №8Задача коммивояжера, слайд №9Задача коммивояжера, слайд №10Задача коммивояжера, слайд №11Задача коммивояжера, слайд №12Задача коммивояжера, слайд №13Задача коммивояжера, слайд №14Задача коммивояжера, слайд №15Задача коммивояжера, слайд №16Задача коммивояжера, слайд №17Задача коммивояжера, слайд №18
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задача коммивояжера. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


ЗАДАЧА КОММИВОЯЖЕРА Лекция 10
Описание слайда:
ЗАДАЧА КОММИВОЯЖЕРА Лекция 10

Слайд 2


СОДЕРЖАНИЕ Текущий контроль знаний. Задача коммивояжера и ее решение перебором.
Описание слайда:
СОДЕРЖАНИЕ Текущий контроль знаний. Задача коммивояжера и ее решение перебором.

Слайд 3


Текущий контроль знаний
Описание слайда:
Текущий контроль знаний

Слайд 4


Содержательные постановки задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу, и затратив: - минимум средств на путешествие либо - минимум средств на максимальный переход. 2. Замкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу и вернуться в город из которого стартовал, затратив -минимум средств на путешествие либо - минимум средств на максимальный переход.
Описание слайда:
Содержательные постановки задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу, и затратив: - минимум средств на путешествие либо - минимум средств на максимальный переход. 2. Замкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу и вернуться в город из которого стартовал, затратив -минимум средств на путешествие либо - минимум средств на максимальный переход.

Слайд 5


Графовая интерпретация замкнутой задачи коммивояжера
Описание слайда:
Графовая интерпретация замкнутой задачи коммивояжера

Слайд 6


Обозначения и определения
Описание слайда:
Обозначения и определения

Слайд 7


Формальная постановка аддитивной замкнутой задачи коммивояжера
Описание слайда:
Формальная постановка аддитивной замкнутой задачи коммивояжера

Слайд 8


Формальная постановка аддитивной разомкнутой задачи коммивояжера
Описание слайда:
Формальная постановка аддитивной разомкнутой задачи коммивояжера

Слайд 9


Формальная постановка минимаксной разомкнутой задачи коммивояжера
Описание слайда:
Формальная постановка минимаксной разомкнутой задачи коммивояжера

Слайд 10


Графовая интерпретация разомкнутой задачи коммивояжера
Описание слайда:
Графовая интерпретация разомкнутой задачи коммивояжера

Слайд 11


Переход от разомкнутой к замкнутой задаче коммивояжера
Описание слайда:
Переход от разомкнутой к замкнутой задаче коммивояжера

Слайд 12


Решение разомкнутой задачи коммивояжера перебором всех перестановок
Описание слайда:
Решение разомкнутой задачи коммивояжера перебором всех перестановок

Слайд 13


ПРИНЦИП РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК
Описание слайда:
ПРИНЦИП РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК

Слайд 14


АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК
Описание слайда:
АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК

Слайд 15


ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ПЕРЕСТАНОВОК Достоинства: Генерация всех n! перестановок. Простота алгоритма. Легкость программной реализации. Низкие требования к объему памяти компьютера Недостатки: В ходе работы алгоритма генерируется более n! сочетаний различных чисел: алгоритм избыточен. Сложность распараллеливания алгоритма.
Описание слайда:
ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ПЕРЕСТАНОВОК Достоинства: Генерация всех n! перестановок. Простота алгоритма. Легкость программной реализации. Низкие требования к объему памяти компьютера Недостатки: В ходе работы алгоритма генерируется более n! сочетаний различных чисел: алгоритм избыточен. Сложность распараллеливания алгоритма.

Слайд 16


Выделение всех контуров на орграфе алгоритмом Неметри
Описание слайда:
Выделение всех контуров на орграфе алгоритмом Неметри

Слайд 17


РЕШИТЬ САМОСТОЯТЕЛЬНО Найти перебором решение минимаксной разомкнутой задачи коммивояжера на графе G(X,U) при условии, что стартовой является вершина «5».
Описание слайда:
РЕШИТЬ САМОСТОЯТЕЛЬНО Найти перебором решение минимаксной разомкнутой задачи коммивояжера на графе G(X,U) при условии, что стартовой является вершина «5».

Слайд 18


САМОСТОЯТЕЛЬНО: Составить блок-схемы алгоритмов решения замкнутой и разомкнутой задач коммивояжера, включающие генератор перестановок. Программно реализовать построенные алгоритмы. Построить графики зависимости времени счета T от размерности задачи n. Пользуясь методом наименьших квадратов найти аналитические зависимости T(n).
Описание слайда:
САМОСТОЯТЕЛЬНО: Составить блок-схемы алгоритмов решения замкнутой и разомкнутой задач коммивояжера, включающие генератор перестановок. Программно реализовать построенные алгоритмы. Построить графики зависимости времени счета T от размерности задачи n. Пользуясь методом наименьших квадратов найти аналитические зависимости T(n).

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию