1631124435-59a81a8a1084f5170bbbb6e23ee88408 (848542), страница 5
Текст из файла (страница 5)
Повторяя аналогичные операции, находим все моментызапуска производства.26.2. Записать задачу РАЗБИЕНИЕ («О камнях») как частный случай задачи о ранце.РАЗБИЕНИЕ. («Задача о камнях».) Задано множество A = {a1, …, an}, каждый элемент которого имеет весs(ai) ∈ Z+, и26.3. НЕТ!!!!!!!! Привести пример матричной игры, которая решается (не решается) в чистыхстратегиях.Два игрока «выбрасывают» произвольное количество пальцев одной руки. Первый игроквыигрывает +1, если сумма пальцев четная и проигрывает -1, в противном случае.Существует ли решение игры в чистых стратегиях? (НЕТ)Два игрока бросают по 1 кости каждый. Выигрыш 1 игрока равен разнице между числом,выпавшим на его кости, и числом, выпавшим на кости соперника.
Имеет ли игра решение вчистых стратегиях? (ДА)27.1. Приближенные алгоритмы. Априорный и апостериорный анализ. Аппроксимационныесхемы.Большинство практических задач дискретной оптимизации является NP-трудными и для нихсуществование полиномиальных алгоритмов маловероятно. Применение методов неявного перебора, какправило, сопряжено с большими временными затратами. Поэтому в настоящее время для решения сложныхоптимизационных задач часто применяют приближенные алгоритмы, которые строят допустимые решенияза полиномиальное время.
Ниже приведены наиболее часто используемые схемы для построенияприближенных решений: жадный алгоритм, локальный поиск, поиск с запретами, имитация отжига,генетический алгоритм, анализ точности приближенных алгоритмов, задача о ранце, задача коммивояжера.Для анализа точности приближенного решения можно выделить два основных подхода.Апостериорный анализ. Решается достаточно большое количесво индивидуальных задач и вычисляетсяотклонение функционала на построенных приближенным алгоритмом решениях от оптимального значенияцелевой функции или оценки оптимума.Априорный анализ. Ищется гарантированная оценка погрешности, которая справедлива для всехиндивидуальных задач и, следовательно, известна заранее, т.
е. до применения алгоритма (априори).Определение 9.1. Алгоритм A является аппроксимационной схемой (Apx) для задачи P, если для любойиндивидуальной задачи27.2. Двойственная связь паросочетания и вершинного покрытия.Пусть задан неориентированный граф G = (V, E).Определение 6.1. Подмножество ребер M ⊆ E называется паросочетанием в графе G, есликаждой вершине v ∈ V инцидентно не более одного ребра из M.Паросочетание, покрывающее все вершины графа, называется совершенным.Определение 6.2. Вершинным покрытием графа называется такое подмножество вершин R⊆ V, что каждое ребро графа e ∈ E инцидентно по крайней мере одной вершине из R.Между паросочетанием и вершинным покрытием графа существует (двойственная)взаимосвязь.
А именно, для любых паросочетания M и вершинного покрытия R, имеет местонеравенство |M| ≤ |R|.Действительно, пусть M = {(i1 , j1), …, (ik , jk )} паросочетание. Тогда в вершинном покрытии Rдолжна быть хотя бы одна из вершин каждой пары {is , js }, s = 1, …, k. Следовательно, |R| ≥ k= |M|.27.3. Отношение доминирования в матричной игре. Примеры упрощения пла-тёжной матрицыСтрока i доминирует строку k, если aij ≥ akj, для всех j = 1, …, n, и существует столбец d такой,что aid > akdЕсли из платежной матрицы убрать все доминируемые строки, то решение игры сполученной матрицей совпадает с решением исходной игры.
Таким образом, иногда можноуменьшить размерность платежной матрицы путем удаления доминируемых строк.Аналогично доминирование определяется и для столбцов.Столбец j доминирует столбец k, если aij ≤ aik, i = 1, …, m, и существует строка d такая, что adj <adkПлатежная матрица может быть упрощена также с помощью удаления доминируемыхстолбцов.28.1. Приближенные алгоритмы с оценками. Класс APX. Полиномиальные приближенныесхемы.Большинство практических задач дискретной оптимизации является NP-трудными и для нихсуществование полиномиальных алгоритмов маловероятно.
Применение методов неявного перебора, какправило, сопряжено с большими временными затратами. Поэтому в настоящее время для решения сложныхоптимизационных задач часто применяют приближенные алгоритмы, которые строят допустимые решенияза полиномиальное время. Ниже приведены наиболее часто используемые схемы для построенияприближенных решений: жадный алгоритм, локальный поиск, поиск с запретами, имитация отжига,генетический алгоритм, анализ точности приближенных алгоритмов, задача о ранце, задача коммивояжера.28.2. НЕТ!!! При каком предположении задача коммивояжера не может быть решена заполиномиальное время?Возможно глава 928.3. НЕТ!!! !!!!!!Можно ли свести задачу построения max паросочетания в двудольном графе кзадаче построения потока max мощности?29.1.
Алгоритм решения задачи о назначениях.Перейти на Шаг 1.29.2. НЕТ!!!!Упростить платежную матрицу3020-112-14-2-124-5029.3. НЕТ!!!!Сводится ли за полиномиальное время задача о ранце к задаче коммивояжера?30.1. НЕТ!!!!Построение математических моделей оптимизационных задач. Их характеристики.Примеры. Определение вполне полиномиальной приближенной схемы.30.2. Записать задачу РАЗБИЕНИЕ («О камнях») как частный случай задачи о ранце.РАЗБИЕНИЕ. («Задача о камнях».) Задано множество A = {a1, …, an}, каждый элемент которого имеет весs(ai) ∈ Z+, и30.3. НЕТ!!!!Сводится ли за полиномиальное время задача Гамильтонов цикл к задаче о ранце?31.1. Приближенные алгоритмы. Алгоритмы локального поиска. Генетический алгоритм.Большинство практических задач дискретной оптимизации является NP-трудными и для нихсуществование полиномиальных алгоритмов маловероятно.
Применение методов неявного перебора, какправило, сопряжено с большими временными затратами. Поэтому в настоящее время для решения сложныхоптимизационных задач часто применяют приближенные алгоритмы, которые строят допустимые решенияза полиномиальное время.
Ниже приведены наиболее часто используемые схемы для построенияприближенных решений: жадный алгоритм, локальный поиск, поиск с запретами, имитация отжига,генетический алгоритм, анализ точности приближенных алгоритмов, задача о ранце, задача коммивояжера.31.2. НЕТ!!!!!!!Записать математическую постановку следующей задачи. Имеется n исполнителейи n работ. Исполнитель i выполняет работу j за tij часов. Требуется назначить по одномуисполнителю на каждую работу т.о., чтобы все работы были выполнены за минимальное время.31.3.
Является ли NP-трудной в сильном смысле задача РАЗБИЕНИЕ?Нет, потому что для разбиения есть псевдополиномиальный алгоритм.32.1. Приближенные алгоритмы. Анализ точности приближенных алгоритмов. Приближенноерешение линейной задачи о ранце.Глава 932.2. НЕТ!!!!!!!!Является ли NP-трудной в сильном смысле задача о ближайшем соседе?32.3. НЕТ!!!!Является ли достаточным (необходимым) условие целочисленности пропускныхспособностей ребер для реализации алгоритма Форда-Фалкерсона для нахождения потокамаксимальной мощности?33.1. Приближенные алгоритмы. Анализ точности приближенных алгоритмов. Приближенноерешение задачи коммивояжера.Глава 933.2.
Является ли NP-трудной в сильном смысле задача о ранце?Нет. Она может быть решена псевдополиномиальным алгоритмом, следовательно неявляется NP-полной в СС, а значит не является NP-трудной в СС.33.3. НЕТ!!!!Упростить платежную матрицу102-1313-11-2-12450.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
