Указатель на узел, являющийся корнем дерева



Дата16.11.2016
Размер35.1 Kb.
Вариант 1

1. С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся. В бинарном дереве из каждой вершины выходит не более двух дуг. В сильноветвящемся дереве количество дуг может быть произвольным.

Бинарные деревья достаточно просто могут быть представлены в виде списков или массивов. Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков. При таком способе представления дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве.

2. Все алгоритмы, рассматривавшиеся нами ранее, имели поли­номиальную сложность. Главное, то, что мы могли найти точное решение этих задач за разум­ный промежуток времени. Все эти задачи относятся к классу Р — клас­су задач полиномиальной сложности. Такие задачи называются также практически разрешимыми.

Есть и другой класс задач: они практически неразрешимы и мы не знаем алгоритмов, способных решить их за разумное время. Эти задачи образуют класс NP — недетерминированной полиномиальной сложности. Отме­тим только, что сложность всех известных детерминированных алго­ритмов, решающих эти задачи, либо экспоненциальна, либо факториальна. Сложность некоторых из них равна 2N, где N — количество входных данных.

Словосочетание «недетерминированные полиномиальные», характе­ризующее задачи из класса NP, объясняется следующим двухшаговым подходом к их решению. На первом шаге имеется недетерминирован­ный алгоритм, генерирующий возможное решение такой задачи — что-то вроде попытки угадать решение; иногда такая попытка оказывается успешной, и мы получаем оптимальный или близкий к оптимальному ответ, иногда безуспешной (ответ далек от оптимального). На вто­ром шаге проверяется, действительно ли ответ, полученный на первом шаге, является решением исходной задачи. Каждый из этих шагов по отдельности требует полиномиального времени. Проблема, однако, в том, что мы не знаем, сколько раз нам придется повторить оба эти шага, чтобы получить искомое решение. Хотя оба шага и полиноми­альны, число обращений к ним может оказаться экспоненциальным или факториальным. К классу NP относится задача о коммивояжере.

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

Мы показываем, что задача является NP-полной, указывая способ сведения к ней всех остальных задач класса NP. На практике эта де­ятельность выглядит не столь уж устрашающе — нет необходимости осуществлять редукцию для каждой NP задачи. Вместо этого для того, чтобы доказать NP-полноту некоторой NP задачи А, достаточно све­сти к ней какую-нибудь NP-полную задачу В. Редуцировав задачу В к задаче А, мы показываем, что и любая NP задача может быть сведена к А за два шага, первый из которых — ее редукция к В.

3. Ричард Беллман ввел понятие динамическое программирование для характеристики алгоритмов, действующих в зависимости от меняю­щейся ситуации. Ключевым в его подходе является использование по­линомиальных по времени алгоритмов вместо экспоненциальных.

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

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

Метод динамического программирования - один из наиболее мощных и широко известных математических методов современной теории управления, был предложен в конце 50-х годов американским математиком Р. Беллманом и быстро получил широкое распространение. Р. Беллман сформулировал принцип оптимальности:

Каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага.

Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом.



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

Условия применения динамического программирования:

  1. Небольшое число подзадач. Уменьшение числа подзадач происходит из-за многократного их повторения (т.н. перекрывающиеся подзадачи)

  2. Дискретность (неделимость) величин, рассматриваемых в задаче.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница