Множества
<<  Пособие: круг с ниткой Математика 21 - радикальная смена парадигмы: Модель, а не Алгоритм  >>
Картинок нет
Картинки из презентации «Исследование алгоритмов решения задачи k коммивояжеров» к уроку математики на тему «Множества»

Автор: renata. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока математики, скачайте бесплатно презентацию «Исследование алгоритмов решения задачи k коммивояжеров.ppt» со всеми картинками в zip-архиве размером 196 КБ.

Исследование алгоритмов решения задачи k коммивояжеров

содержание презентации «Исследование алгоритмов решения задачи k коммивояжеров.ppt»
Сл Текст Сл Текст
1Исследование алгоритмов решения задачи 7является последовательное разделение на 2
k коммивояжеров. Ю.Л. Костюк. Научный группы. Рассмотрены 2 метода выбора нового
руководитель, проф., д.т.н. Исполнитель, города для добавления: На основе минимума
аспирант. М.С. Пожидаев. Томский расстояний. На основе разности расстояний.
государственный университет. Факультет Качество работы выше. 7.
информатики. 1. 8Обменная оптимизация. После очередного
2Введение. Содержание работы - задача k разделения городов на 2 группы: 1.
коммивояжёров. Цель - минимизация Рассмотрим все возможные пары городов, где
стоимости объезда городов k первый город будет принадлежать первой, а
коммивояжёрами. На практике постановка второй - второй группе; 2. Для каждой
задачи k коммивояжёров имеет множество такой пары выполним пробный обмен
вариантов. В данной работе сформулирована городами. То есть первый город попадёт во
упрощенная постановка задачи без учета вторую группу, а второй - в первую. 3.
максимальной загрузки одного коммивояжёра, Выполнив обмен, подсчитаем сумму длин
задержки при посещении каждого города, рёбер минимального остова в каждой группе,
возможности существования нескольких баз и прибавив длину самого длинного ребра в
т. д. 2. нём. 4. Найдём оценку из шага 3 для всех
3Формальная постановка задачи. Среди возможных пар. Если минимальное значение
городов вводится база - город, где таких оценок меньше, чем в исходных
начинаются и заканчиваются все пути группах, то совершим обмен. Оптимизация
коммивояжёров. Стоимость переезда из проводится для всех городов в группах
города i в город j будет задаваться Оптимизация проводится для ограниченного
матрицей, где нужное значение будет множества городов. 8.
храниться на пересечении i-той строки и 9Угловая сортировка городов на
j-того столбца. Определим задачу так: 1. плоскости. 1. Для каждого города
На вход алгоритма поступает матрица вычисляются углы между ними и осью X. 2.
расстояний между n городами и множество Множество городов сортируются по
значений расстояний от каждого города до возрастанию углов. 3. Вычисляется
базы. 2. Необходимо найти k замкнутых количество городов для каждой будущей
маршрутов, где k > 1, со следующими группы. По результатам вычислений получаем
свойствами: 2.1. Через каждый город должен массив Ni. 4. Первые N1 городов из
проходить один и только один маршрут, отсортированного списка отнесём к первой
причём только один раз; 2.2. Все маршруты группе, последующие N2 городов - ко второй
должны проходить через базу; 2.3. Для и. т. д., к каждой группе добавим по базе.
любой пары полученных маршрутов количество 5. Для каждой полученной группы
городов в них не должно отличаться больше вычисляется минимальная оценка возможного
чем на единицу. 3. Суммарная длина решения. 6. Повторяем действия на шаге 4,
полученных маршрутов должна быть как можно но при построении отступаем на один город
меньше. 3. и находим оценку, описанную на шаге 5. 7.
4Рассматриваемые алгоритмы. Оптимальное Выбирается то разбиение, где оценка
разрезание общего маршрута по всем городам минимальна и выполняется поиск
Предварительное разделение на группы для окончательных маршрутов решением простой
каждого коммивояжёра Последовательное ЗК внутри каждой группы. 9.
деление на 2 группы Добавление городов на 10Алгоритм "разрезание готового
основе минимума расстояний Добавление маршрута" 10.
городов на основе разности расстояний 11Алгоритм "деление по
Последовательное деление на 3 группы минимуму" 11.
Обменная оптимизация Для всех городов Для 12Алгоритм "деление по
ограниченного множества городов. 4. разности" 12.
5Угловая сортировка городов на 13Алгоритм "угловая сортировка на
плоскости. Является исключением среди плоскости" 13.
рассматриваемых методов, поскольку не 14Вычислительный эксперимент. При
удовлетворяет формальной постановке тестировании описанных методов выполнялся
задачи. Использует информацию об углах многократный их запуск на случайно
между городами, если они расположены на сгенерированном множестве городов. При
плоскости. 5. генерации города располагались на
6Алгоритм разрезания "общего плоскости равномерно в единичном квадрате
" маршрута. 1. Решить задачу с независимыми координатами. Результаты
коммивояжёра 2. Найти количество городов приведены в отношении к нижней оценке
для каждого коммивояжёра 3. В точного решения задачи коммивояжёра.
предварительно построенном маршруте Обменная оптимизация проводилась только в
выбрать некоторый город в качестве частичном варианте, поскольку многократное
начального. 4. Городами для объезда 1-вым нахождение минимального остова занимает
коммивояжёром будут первые N[1] городов, слишком много времени. 14.
начиная с выбранного начального. 15Результаты обработки задачи на 64
Последующий отрезок маршрута из N[2] города на 4 коммивояжера. 15.
городов будет участком для 2-го 16Результаты обработки задачи на 512
коммивояжёра и т. д. В результате этого городов на 2 коммивояжера. 16.
этапа мы получим k незамкнутых 17Результаты обработки задачи на 512
последовательностей нужной длины. 5. К городов на 32 коммивояжера. 17.
каждой такой последовательности добавим 18Результаты обработки задачи на 1024
базу и замкнём её. 6. Запомним полученную городов на 4 коммивояжера. 18.
длину всех маршрутов и повторим операцию с 19Заключение. Сформулирована
шага 4, но начальный город сместим на один сбалансированная задача k коммивояжеров
относительно предыдущего. 7. Шаг 6 будем Предложены некоторые методы приближенного
повторять Nmin раз, где Nmin - это число её решения Поставлен вычислительный
на один меньше, чем длина самого короткого эксперимент для сравнения качества работы
пути среди коммивояжёров, полученных на предложенных алгоритмов и выполнен
шаге 2. 6. статистический анализ ранговым критерием
7Метод предварительного разделения Уилкоксона Подготовлена программная
городов на группы для каждого библиотека. 19.
коммивояжёра. Наиболее эффективным 20Спасибо за внимание. 20.
Исследование алгоритмов решения задачи k коммивояжеров.ppt
http://900igr.net/kartinka/matematika/issledovanie-algoritmov-reshenija-zadachi-k-kommivojazherov-99621.html
cсылка на страницу

Исследование алгоритмов решения задачи k коммивояжеров

другие презентации на тему «Исследование алгоритмов решения задачи k коммивояжеров»

«Формы представления алгоритма» - Целевые направления темы «Формы представления алгоритмов». Развивающий аспект - развитие алгоритмического мышления учащихся. Нужно ли соблюдать порядок в алгоритме? Цель: сформировать представление у учащихся о формах представления алгоритмов. Информатика и ИКТ: учебник для 9 класса . §12.3 Формы представления алгоритма.

«Исполнитель алгоритма» - Результативность. Понятие алгоритма. Правильность. Аль-Хорезми впервые описал правила выполнения четырёх арифметических действий. Исполнителя характеризуют: Элементарное действие. Дискретность (прерывность). Конечность. Слово «алгоритм» происходит от латинского написания имени арабского математика аль-Хорезми (Algorithmi).

«Команда алгоритма» - Циклический алгоритм. Серия. 1.Точность. Серия 2. Условие. Каждая команда алгоритма должна определять однозначное действие исполнителя. 2.Понятность. Серия 1. Запись блок-схем в ms worde. Команда 1. Линейный алгоритм. Алгоритм, в котором серия команд выполняется многократно называется… Алгоритм, в котором команды выполняются последовательно одна за другой, называется …

«Алгоритм задачи» - Линейный алгоритм. Надеть ведро на третий шар. Команда повторения. Какой алгоритм называют циклическим? Что необходимо для составления алгоритма? Какие существуют формы записи алгоритмов? Какой алгоритм называют линейным? Что такое блок-схема? Составить действия мальчика в виде блок-схемы. Как ты думаешь, что выберет Иван-царевич?

«Свойства и виды алгоритмов» - Виды алгоритмов. Циклическая алгоритмическая конструкция, в которой условие поставлено в начале цикла. Свойства алгоритмов: Последовательность выполнения действий. Условие выполнения действия. Начало, конец алгоритма. Выполняемое действие. Неполная форма разветвленного алгоритма. Полная форма разветвленного алгоритма.

«Схема алгоритма» - Линейный алгоритм. Обычно после школы я иду гулять, а когда возвращаюсь, делаю уроки. Обозначим время буквой t. Разветвляющийся алгоритм. Алгоритмы. Дома я поем, сделаю уроки и сяду играть на компьютере. Пример: Конец. Смотрю телевизор. Иначе придется идти на уроки. Разветвляющийся алгоритм (полная форма).

Множества

13 презентаций о множествах
Урок

Математика

71 тема
Картинки
900igr.net > Презентации по математике > Множества > Исследование алгоритмов решения задачи k коммивояжеров