Архив категории ‘Методы разработки алгоритмов’

Метод Лагранжевых релаксаций

    На этом шаге мы рассмотрим метод Лагранжевых релаксаций.     В начале 70-х годов была высказана идея[1, 2], которая в последствии оказалась очень продуктивной при решении дискретных экстремальных задач. Многие NP-трудные задачи можно представить как "легкие" задачи с дополнительными отягощающими ограничениями. Лагранжевы релаксации получаются путем перехода к двойственной задаче относительно этого множества дополнительных ограничений. Релаксированная […]

Метод балансировки

    На этом шаге мы рассмотрим метод балансировки.     При проектировании некоторых алгоритмов приходиться идти на различные компромиссы, т.е. по возможности сбалансировать вычислительные затраты на использование различных частей алгоритмы. Метод балансировки рассматривается как балансировка деревьев. Дерево - важная структура данных, применяемая для хранения, обработки и предоставления информации. Дерево состоит из элементов, обычно называемых вершинами или […]

Динамическое программирование

    На этом шаге мы рассмотрим динамическое программирование.     Наиболее общей формой называют процесс пошагового решения задач, когда на каждом шаге выбирается одно значение из множества допустимых на этом шаге, причем такое, которое оптимизирует заданную цель. В основе программирования лежит принцип оптимальности Беномена. Суть метода:     Часто не удается разбить задачу на небольшое количество подзадач, […]

Эвристические методы разработки алгоритмов

    На этом шаге мы рассмотрим эвристические методы разработки алгоритмов.     Под эвристическими понимаются методы, правильность которых не доказана. Они выглядят правдоподобными, кажется, что в большинстве случаев они должны давать верное решение. Иногда не удается построить контрпример, демонстрирующий ошибочность или неуниверсальность метода. Но не удается доказать математическими средствами и правильность метода. Тем не менее, практика […]

Решение обратной задачи и метод полного перебора

    На этом шаге мы рассмотрим решение обратной задачи и метод полного перебора. Решение обратной задачи     Иногда обратная задача, т. е. задача, соответствующая функции f-1(Y)=X, решается значительно более просто, чем исходная задача. Тогда имеющийся алгоритм решения обратной задачи R иногда можно использовать для построения алгоритма решения прямой задачи Р. Метод полного перебора     Когда […]

Методы разработки алгоритмов. Сведение задачи к самой себе (рекурсия) и метод последовательных приближений

    На этом шаге мы рассмотрим сведение задачи к самой себе (рекурсия) и метод последовательных приближений. Сведение задачи к самой себе (рекурсия)     Задача также, как и в предыдущем методе сводится к более простой. Но эта более простая задача имеет ту же формулировку, что и исходная, с той лишь разницей, что решаться она должна для […]

Разложение задачи в последовательность однородных подзадач (итерация)

    На этом шаге мы рассмотрим разложение задачи в последовательность однородных подзадач.     Важный частный случай предыдущего метода, приобретающий, однако, новое качество за счет того, что задача P сводится к n экземплярам более простой задачи R и к простой задаче Q, объединяющей n решений.     Очень простой пример: вычисление скалярного произведения двух векторов A и […]

Разложение задачи в последовательность разнородных подзадач

    На этом шаге мы рассмотрим разложение задачи в последовательность разнородных подзадач.     Этот метод называют иногда методом "разделяй и властвуй".     В этом методе обычно выделяется относительно небольшое число подзадач. Например: задача - выполнить программу на ЭВМ; подзадачи - ввести исходный текст программы; транслировать программу в машинные команды; присоединить к машинному коду стандартные процедуры […]