Классы алгоритмов - часть 3

Используя монету 0, о которой известно, что она настоящая, можно получить приведенное на рис. 1.3 дерево решений (полное двухъярусное тернарное дерево), которое и в худшем, и в среднем случае требует двух сравнений.

Рис. 1.3. Оптимальное дерево решений для задачи о четырех монетах

Рассматриваемый класс алгоритмов решения задачи о фальшивой монете есть множество тернарных деревьев решений (примеры на рис.1.1, рис.1.2,

рис.1.3), обладающих следующими свойствами:

каждый узел помечен сравнением
$S_{1} :S_{2}$
, где
$S_{1}$
и
$S_{2}$
- непересекающиеся непустые подмножества множества
$S = \{0,1,2,\ldots,n\}$
всех монет;
каждый лист либо не помечен, что соответствует невозможному исходу в предположении существования не более чем одной фальшивой монеты, либо помечен одним из исходов iл, iT, н, означающим соответственно, что все монеты настоящие. Четко определив подлежащий дальнейшему рассмотрению класс алгоритмов, можно исследовать свойства, которыми должно обладать каждое дерево из этого класса, и определить, как найти алгоритмы, являющиеся в некотором смысле оптимальными. Решим эту проблему в начале для четырех монет, а затем перейдем к общему случаю.

Поскольку в задаче о четырех монетах требуется различить девять возможных исходов, любое дерево решений для этой задачи должно иметь, по крайней мере, девять листьев и, следовательно, не менее двух ярусов. Поэтому дерево на рис.1.3 является оптимальным и для худшего случая, и для среднего. Существуют ли другие оптимальные деревья? Для ответа на этот вопрос нужно рассмотреть множество всех деревьев решений для задачи о четырех монетах. Попытаемся исключить из дальнейшего рассмотрения какую-либо часть этого множества. Прежде всего видно, что путем любой перестановки множества

$\{ 1,2,\ldots,n\}$

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

Рассмотрим затем, существует ли оптимальное дерево среди тех, у которых в корне не используется монета с номером n.

Содержание Назад Вперед