Полное построение алгоритма. Часть 2. Задача коммивояжера

Сентябрь 7, 2022

Главная
Алгебра
Полное построение алгоритма. Часть 2. Задача коммивояжера

Содержание

2. Реализация алгоритма. На этом этапе следует ответить на вопросы: Каковы основные переменные? Каких они типов? Сколько
3. Реализация алгоритма. Другой аспект построения программной реализации - это программирование "сверху - вниз". Необходимо разбить задачу
4. Реализация алгоритма. Процедура генерации всех возможных перестановок. Процедура вычисления стоимости каждого полученного пути. Процедура сравнения различных
5. Реализация алгоритма. На первом этапе пункт 1 может быть осуществлен вручную, с помощью ввода данных с
6. Реализация алгоритма. 2. Процедура вычисления стоимости каждого полученного пути. Вход: Выход: Описать назначение и структуру данных
7. Анализ алгоритма и его сложности В начале проводится оценка ресурсов: Как будет использовать алгоритм ресурсы машины,
8. Анализ алгоритма и его сложности Пусть А - алгоритм для решения некоторого класса задач. N -
9. Анализ алгоритма и его сложности Пусть fA(n) - рабочая функция, дающая верхнюю границу для максимального числа
10. Анализ алгоритма и его сложности Введем обозначения: Функцию f(n) обозначим как О[g(n)] и будем говорить, что
11. Анализ алгоритма и его сложности Примеры: Полином f(n)=2n5+6n4+6n2+18 есть О(n5) Функция f(n)=2n есть о(n!), так как
12. Анализ алгоритма и его сложности Итак, алгоритм А полиномиальный, если fА(n)=O(Pk(n)) или fА(n)=о(Pk(n)), где Pk(n)- некоторый
13. Анализ алгоритма и его сложности "Задача коммивояжера" Размерность задачи - n. Оценка времени работы алгоритма O(n!),
14. Анализ алгоритма и его сложности Пусть размерность n=20 время выполнения одной операции: (сравнение, сложение, поиск элемента
15. Проверка программы Эксплуатации программы предшествует её отладка. Отладка программы - экспериментальное подтверждение того факта, что программа
16. Проверка программы Особенности ОС, которые могли не учесть. (Пример с фирмой МS). Проверка качества алгоритма. Какие
17. Проверка программы Многие программы для некоторых входных данных работают хорошо, а для других плохо. Характеристика работы
18. Проверка программы Из формулировки задачи вытекает необходимость проверки работы программы по крайней мере на двух тестах.
19. Проверка програмы Далее, всякий раз, когда в алгоритме, решающем задачу, происходит разветвление, набор тестов необходимо пополнить
20. Пример тестирования Пусть требуется построить программу, которая печатает сообщение N--ПРОСТОЕ, если натуральное число N является простым,
21. Составление документации: Описание алгоритма на языке, понятном для человека, не связанного с предметной областью Описание исходных
22. Описание алгоритма и данных Самое главное - оформлять в том виде, в котором хотелось бы читать.
23. Описание алгоритма При составление больших программ (систем) возникает необходимость разбивать задачу на подзадачи, чтобы над каждой
24. Особенности функционирования Указать условия функционирования и ограничения. Указать также, в каких случаях программа работает, а в
25. Задание к практической работе: Решение задачи коммивояжера Программирование исчерпывающего алгоритма для задачи коммивояжера. Дополнить задачу коммивояжера
27. Скачать презентацию

Слайд 2

Реализация алгоритма.
На этом этапе следует ответить на вопросы:
Каковы основные переменные?
Каких

они типов?
Сколько нужно массивов, и какой размерности?
Имеет ли смысл пользоваться связными списками?
Какие нужны подпрограммы (возможно, уже записанные в памяти)
Каким языком программирования пользоваться.
Пункты 1-4 - построение структур данных.
Пункты 5-6 – непосредственное использование языка программирования.
Конкретная реализация может существенно влиять на требования к памяти и на скорость работы алгоритма.

Слайд 3

Реализация алгоритма.
Другой аспект построения программной реализации - это программирование "сверху

- вниз".
Необходимо разбить задачу на элементарные шаги (процедуры), т.е.
преобразовать алгоритм в такую последовательность все более конкретизированных алгоритмов, что окончательный вариант будет представлять собой программу

Слайд 4

Реализация алгоритма.
Процедура генерации всех возможных перестановок.
Процедура вычисления стоимости каждого полученного

пути.
Процедура сравнения различных путей и выбора минимального.

Слайд 5

Реализация алгоритма.
На первом этапе пункт 1 может быть осуществлен вручную,

с помощью ввода данных с клавиатуры.
Необходимо определить, что будет на входе и на выходе каждой процедуры.
Для генерации перестановок:
Вход: количество городов (К)
Выход: массив всех перестановок
(от 1 до К, матрица всех возможных путей).

Слайд 6

Реализация алгоритма.
2. Процедура вычисления стоимости каждого полученного пути.
Вход:
Выход:
Описать назначение и

структуру данных
3. Процедура сравнения различных путей и выбора минимального
Алгоритм формирования перестановок «вручную»

Слайд 7

Анализ алгоритма и его сложности
В начале проводится оценка ресурсов:
Как будет использовать

алгоритм ресурсы машины, например, память (получение оценок или границ для объема памяти).
Полезно оценить время работы до отладки и программирования.
Необходимо иметь абсолютный (количественный) критерий для сравнения двух алгоритмов, претендующих на решение одной и той же задачи. Более сложный алгоритм должен быть улучшен или отброшен
Когда можно считать решение задачи оптимальным? Когда алгоритм настолько хорош, что его невозможно значительно улучшить.

Слайд 8

Анализ алгоритма и его сложности
Пусть А - алгоритм для решения некоторого

класса задач.
N - размерность отдельной задачи из этого класса.
Может быть:
просто скаляр, равный числу вершин графа;
размер массива или длина вводимой
последовательности.

Слайд 9

Анализ алгоритма и его сложности
Пусть fA(n) - рабочая функция, дающая верхнюю

границу для максимального числа основных операций (сложение, сравнение), которые должны быть выполнены алгоритмом А для решения задачи размерности n.
Критерий оценки качества алгоритма А основан на времени работы в худшем случае:
Алгоритм А - полиномиальный, если fA(n) растет быстрее, чем полином от n.
В противном случае алгоритм А называется экспоненциальным (ехр)
Последовательные или параллельные машины более или менее способны воспринимать полиномиальные алгоритмы для задач большой размерности, а на экспоненциальных задачах они довольно быстро "задыхаются".

Слайд 10

Анализ алгоритма и его сложности
Введем обозначения:
Функцию f(n) обозначим как О[g(n)] и

будем говорить, что она порядка g(n) для больших n, если
lim f(n)/g(n)=const≠0
Функцию f(n) обозначим как o[z(n)] и будем говорить, что она порядка z(n) для больших n, если
lim f(n)/z(n)=0
Если f(n)=О[g(n)], то эти две функции возрастают с одинаковой скоростью при n→∞, то есть эти два алгоритма одного класса, они одинаково растут.
Если f(n)=o[z(n)], то z(n) растет горазда быстрее, чем f(n).

Слайд 11

Анализ алгоритма и его сложности
Примеры:
Полином f(n)=2n5+6n4+6n2+18 есть О(n5)
Функция f(n)=2n есть о(n!),

так как 2n/n!→0
f(n)=O(2n+1)
f(n)=o(5n+1)
__
f(n)=1000√n f(n)=O(n)

Слайд 12

Анализ алгоритма и его сложности
Итак, алгоритм А полиномиальный, если fА(n)=O(Pk(n)) или

fА(n)=о(Pk(n)), где Pk(n)- некоторый многочлен от переменной n произвольной фиксированной степени k.
В противном случае алгоритм является экспоненциальным.

Слайд 13

Анализ алгоритма и его сложности
"Задача коммивояжера"
Размерность задачи - n.
Оценка времени работы

алгоритма O(n!), так как количество перестановок первых n-1 положительных целых чисел (n-1)!,
т.е., эта часть алгоритма потребует O(n-1!) шагов. В каждой перестановке можно найти путь и его стоимость за O(n) шагов (т. к. n сумм.)
fА(n)=O[n⋅(n-1)!]=O(n!) - верхняя граница для общего времени работы.

Слайд 14

Анализ алгоритма и его сложности
Пусть размерность n=20
время выполнения одной операции:

(сравнение, сложение, поиск элемента матрицы) - 10-7 сек.
Тогда 20!≈2⋅1018
(по формуле Стирлинга n!=2⋅10n-2)
С⋅2⋅1018⋅10-7=С⋅2⋅1011 (70 веков),
где С - константа.
Замечание: Умные люди все это вычисляют на стадии разработки алгоритма, а не после того, как запрограммируют.

Слайд 15

Проверка программы
Эксплуатации программы предшествует её отладка.
Отладка программы - экспериментальное подтверждение

того факта, что программа делает именно то, что должна.
Проверка вручную: рассматривается задача небольшой размерности и все просчитывается на бумаге, если есть сравнение - пример на каждую ветвь (таблица истинности).
Тестирование каждого участка программы, т.е., множество выводов всех возможных крайних случаев
если все случаи проверить практически невозможно, то проверить только те, которые встретятся с наибольшей вероятностью

Слайд 16

Проверка программы
Особенности ОС, которые могли не учесть. (Пример с фирмой МS).
Проверка

качества алгоритма.
Какие были сделаны допущения.
Учесть все возможные варианты.
Работает ли алгоритм лучше в среднем, чем в худшем случае. (→п.6)
Тестирование для определенных вычислительных ограничений.
Анализ среднего функционирования.

Слайд 17

Проверка программы
Многие программы для некоторых входных данных работают хорошо, а для

других плохо.
Характеристика работы алгоритма должна меняться плавно от хорошей к плохой при переходе от входных данных, на которых алгоритм работает хорошо, к входным данным на которых это не так.
"Задача коммивояжера"
При n≤6 работает хорошо.
При 6≤n≤15 плохо.
При n≥15 просто ужасно.

Слайд 18

Проверка программы
Из формулировки задачи вытекает необходимость проверки работы программы по крайней

мере на двух тестах.
Пусть, например, в задаче требуется подсчитать количество окружностей, каждая из которых проходит хотя бы через три различные точки из заданного множества, в котором не меньше трех точек.
Тогда в качестве тестов заведомо необходимо взять:
множество точек, лежащих на одной прямой (с ожидаемым сообщением об отсутствии искомых окружностей),
множество, в котором не все точки лежат на одной прямой
в этом случае тест должен содержать ответ -- сколько требуемых окружностей должна обнаружить программа с учетом приближенности вычислений, о которых говорилось ранее).

Слайд 19

Проверка програмы
Далее, всякий раз, когда в алгоритме, решающем задачу, происходит разветвление,

набор тестов необходимо пополнить так, чтобы иметь возможность пройти каждую из ветвей.
Аналогично, если встречается оператор цикла с условием продолжения, то в наборе должен появиться тест, на котором тело цикла не выполняется ни разу, а также тест, на котором тело цикла выполняется хотя бы один раз

Слайд 20

Пример тестирования
Пусть требуется построить программу, которая печатает сообщение
N--ПРОСТОЕ, если

натуральное число N является простым, и сообщение
N--СОСТАВНОЕ в противном случае.

Слайд 21

Составление документации:
Описание алгоритма на языке, понятном для человека, не связанного с

предметной областью
Описание исходных и выходных данных
Описание программы (алгоритма)
Руководство по вводу либо корректировке данных
Особенности функционирования программы (особые случаи, ограничения)
Контрольный пример (примеры расчетов)

Слайд 22

Описание алгоритма и данных
Самое главное - оформлять в том виде, в

котором хотелось бы читать.
Следует учесть, что ваше описание должны понять люди, не владеющие предметной областью.
Описать план алгоритма «сверху – вниз».
Описать форматы данных и требования к вводу - выводу.

Слайд 23

Описание алгоритма
При составление больших программ (систем) возникает необходимость разбивать задачу на

подзадачи, чтобы над каждой могла работать отдельная группа людей.
Разные группы должны контактировать между собой, так как выход из одной задачи это вход в другую.
Основная ошибка - что-то неправильно описали.

Слайд 24

Особенности функционирования
Указать условия функционирования и ограничения. Указать также, в каких случаях

программа работает, а в каких не работает или работает плохо.
Привести доказательство правильности функционирования алгоритма.
Приложить описание тестовых примеров и результаты тестирования.
Описать порядок настройки программы на конкретные условия функционирования.

Слайд 25

Задание к практической работе: Решение задачи коммивояжера
Программирование исчерпывающего алгоритма

для задачи коммивояжера.
Дополнить задачу коммивояжера (исчерпывающий алгоритм) процедурой генератора перестановок
Докажите, что если матрица стоимостей в задаче коммивояжера с n городами симметрична, то число разных по стоимости путей (гамильтоновых циклов) равно (n-1)!/2

Полное построение алгоритма. Часть 2. Задача коммивояжера

Содержание

Реализация алгоритма. На этом этапе следует ответить на вопросы:Каковы основные переменные?Каких

Реализация алгоритма. Другой аспект построения программной реализации - это программирование "сверху

Реализация алгоритма. Процедура генерации всех возможных перестановок.Процедура вычисления стоимости каждого полученного

Реализация алгоритма. На первом этапе пункт 1 может быть осуществлен вручную,

Реализация алгоритма. 2. Процедура вычисления стоимости каждого полученного пути.Вход:Выход:Описать назначение и

Анализ алгоритма и его сложностиВ начале проводится оценка ресурсов:Как будет использовать

Анализ алгоритма и его сложностиПусть А - алгоритм для решения некоторого

Анализ алгоритма и его сложностиПусть fA(n) - рабочая функция, дающая верхнюю

Анализ алгоритма и его сложностиВведем обозначения:Функцию f(n) обозначим как О[g(n)] и

Анализ алгоритма и его сложностиПримеры:Полином f(n)=2n5+6n4+6n2+18 есть О(n5)Функция f(n)=2n есть о(n!),

Анализ алгоритма и его сложностиИтак, алгоритм А полиномиальный, если fА(n)=O(Pk(n)) или

Анализ алгоритма и его сложности"Задача коммивояжера"Размерность задачи - n.Оценка времени работы

Анализ алгоритма и его сложностиПусть размерность n=20 время выполнения одной операции:

Проверка программыЭксплуатации программы предшествует её отладка. Отладка программы - экспериментальное подтверждение

Проверка программыОсобенности ОС, которые могли не учесть. (Пример с фирмой МS).Проверка

Проверка программыМногие программы для некоторых входных данных работают хорошо, а для

Проверка программыИз формулировки задачи вытекает необходимость проверки работы программы по крайней

Проверка програмыДалее, всякий раз, когда в алгоритме, решающем задачу, происходит разветвление,

Пример тестирования Пусть требуется построить программу, которая печатает сообщение N--ПРОСТОЕ, если

Составление документации:Описание алгоритма на языке, понятном для человека, не связанного с

Описание алгоритма и данныхСамое главное - оформлять в том виде, в

Описание алгоритмаПри составление больших программ (систем) возникает необходимость разбивать задачу на

Особенности функционированияУказать условия функционирования и ограничения. Указать также, в каких случаях

Задание к практической работе: Решение задачи коммивояжера Программирование исчерпывающего алгоритма

Похожие презентации