Картинки на тему «Исследование алгоритмов решения задачи k коммивояжеров» |
| Множества | ||
| << Пособие: круг с ниткой | Математика 21 - радикальная смена парадигмы: Модель, а не Алгоритм >> |
Картинок нет |
Автор: 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 | |||
Исследование алгоритмов решения задачи k коммивояжеров
«Формы представления алгоритма» - Целевые направления темы «Формы представления алгоритмов». Развивающий аспект - развитие алгоритмического мышления учащихся. Нужно ли соблюдать порядок в алгоритме? Цель: сформировать представление у учащихся о формах представления алгоритмов. Информатика и ИКТ: учебник для 9 класса . §12.3 Формы представления алгоритма.
«Исполнитель алгоритма» - Результативность. Понятие алгоритма. Правильность. Аль-Хорезми впервые описал правила выполнения четырёх арифметических действий. Исполнителя характеризуют: Элементарное действие. Дискретность (прерывность). Конечность. Слово «алгоритм» происходит от латинского написания имени арабского математика аль-Хорезми (Algorithmi).
«Команда алгоритма» - Циклический алгоритм. Серия. 1.Точность. Серия 2. Условие. Каждая команда алгоритма должна определять однозначное действие исполнителя. 2.Понятность. Серия 1. Запись блок-схем в ms worde. Команда 1. Линейный алгоритм. Алгоритм, в котором серия команд выполняется многократно называется… Алгоритм, в котором команды выполняются последовательно одна за другой, называется …
«Алгоритм задачи» - Линейный алгоритм. Надеть ведро на третий шар. Команда повторения. Какой алгоритм называют циклическим? Что необходимо для составления алгоритма? Какие существуют формы записи алгоритмов? Какой алгоритм называют линейным? Что такое блок-схема? Составить действия мальчика в виде блок-схемы. Как ты думаешь, что выберет Иван-царевич?
«Свойства и виды алгоритмов» - Виды алгоритмов. Циклическая алгоритмическая конструкция, в которой условие поставлено в начале цикла. Свойства алгоритмов: Последовательность выполнения действий. Условие выполнения действия. Начало, конец алгоритма. Выполняемое действие. Неполная форма разветвленного алгоритма. Полная форма разветвленного алгоритма.
«Схема алгоритма» - Линейный алгоритм. Обычно после школы я иду гулять, а когда возвращаюсь, делаю уроки. Обозначим время буквой t. Разветвляющийся алгоритм. Алгоритмы. Дома я поем, сделаю уроки и сяду играть на компьютере. Пример: Конец. Смотрю телевизор. Иначе придется идти на уроки. Разветвляющийся алгоритм (полная форма).
