Часть 1. Общие проблемы теории интеллектуальных систем

Достаточные условия минимальности сетей типа звезда в гиперпространствах

А. М. Тропин

МГУ

Аннотация: Задача Ферма-Штейнера заключается в поиске такой точки метрического пространства $ Y $ , что сумма расстояний от нее до точек некоторого конечного фиксированного подмножества $ A \subset Y $, называемого границей, минимальна. Минимальную сумму расстояний мы будем называеть длиной минимальной астросети. Мы рассматриваем эту задачу в гиперпространстве $ Y = H(X) $ непустых, замкнутых и ограниченных подмножеств ограниченно компактного метрического пространства $ X $; причем на $ H(X) $ введена метрика Хаусдорфа. В силу ограниченной компактности $ X $ все элементы $ H(X) $ являются компактами. Каждое решение задачи Ферма-Штейнера будем называть астрокомпактом Штейнера; их множество разбивается на классы одинаковой взвешенности, каждый из которых соответствует своему вектору расстояний до граничных компактов. В настоящей статье доказаны три достаточных условия того, что для данной границы предъявленный компакт является астрокомпактом Штейнера. Также эти условия гарантируют единственность класса астрокомпактов Штейнера одинаковой взвешенности. Данная теория применяется для полного решения задачи Ферма-Штейнера для некоторых симметричных выпуклых трехэлементных границ в $ \mathbb {R}^2 $, что демонстрируется примерами.

Ключевые слова: задача Ферма-Штейнера, сеть типа звезда, минимальная астросеть, астрокомпакт Штейнера, гиперпространство, расстояние Хаусдорфа, метрическая проекция, функция расстояния от точки до множества, первая вариация.