Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2017-11-16 | 456 |
5.00
из
|
Заказать работу |
|
|
Самым важным и наиболее широко применимым методом проектирования эффективных алгоритмов является метод, называемый методом декомпозиции (или метод "разделяй и властвуй", или метод разбиения). Этот метод предполагает такую декомпозицию (разбиение) задачи размера n на более мелкие задачи, что на основе решений этих более мелких задач можно легко получить решение исходной задачи. Чтобы проиллюстрировать этот метод, рассмотрим хорошо известную головоломку "Ханойские башни". Имеются три стержня А, В и С. Вначале на стержень А нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше — диски последовательно уменьшающегося диаметра, как показано на рис.. Цель головоломки — перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались нанизанными на стержень В. Стержень С можно использовать для временного хранения дисков.
Для решения этой головоломки подходит следующий простой алгоритм. Представьте, что стержни являются вершинами треугольника. Пронумеруем все перемещения дисков. Тогда при перемещениях с нечетными номерами наименьший диск нужно перемещать в треугольнике на соседний стержень по часовой стрелке. При перемещениях с четными номерами выполняются другие допустимые перемещения, не связанные с наименьшим диском.
Задачу перемещения n наименьших дисков со стержня A на стержень B можно
представить себе состоящей из двух подзадач размера n – 1.Сначала нужно
переместить n – 1 наименьших дисков со стержня A на стержень C, оставив на
стержне A n-й наибольший диск. Затем этот диск нужно переместить с A на B.
|
Потом следует переместить n – 1 дисков со стержня C на стержень B. Это
перемещение n – 1 дисков выполняется путем рекурсивного применения указанного
метода. Поменьше тех, которые в перемещении не участвуют, не нужно
задумываться над тем, что находится под перемещаемыми дисками на стержнях A,
B или C.
Хотя фактическое перемещение отдельных дисков не столь очевидно, а
моделирование вручную выполнить непросто из-за образования стеков рекурсивных
вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост
для понимания и доказательства его правильности (а если говорить о быстроте
разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов
по методу декомпозиции обусловила огромную популярность этого метода; к тому
же во многих случаях эти алгоритмы оказываются более эффективными, чем
алгоритмы, разработанные традиционными методами.
Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из л строк и п — 1 столбцов; элементом на пересечении строки i и столбца j является номер игрока, с которым игрок i должен провести матч в у'-й день. Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда количество игроков будет сокращено до двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядок проведения встреч между ними. Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1 - 4 заполняет верхний левый угол (4 строки х З столбца) составляемого расписания. Нижний левый угол (4 строки х З столбца) этого расписания должен свести между собой игроков с более высокими номерами (5 - 8). Эта часть расписания получается путем прибавления числа 4 к каждому элементу в верхнем левом углу.
Итак, нам удалось упростить задачу. Теперь остается свести между собой игроков с низкими и более высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 - 4, с игроками 5-8 соответственно, а в последующие дни просто циклически переставлять номера 5 - 8. Этот процесс показан на рис. 10.3. Надеемся, теперь читатель сможет обобщить описанный алгоритм и составить расписание для 2* игроков при любом значении k.
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!