Конференции ИВТ СО РАН

Тезисы докладов

В докладе рассматривается применение метода ветвления (факторизации) для вычисления некоторых характеристик связности ненадёжных сетей. Рассматриваются такие характеристики как вероятность связности выделенных вершин и математическое ожидание числа несвязных пар вершин. Первая задача относится к классическим, вторая является малоисследованной.

Расчёт обоих показателей представляет собой NP-трудные задачи. Для сужения облати перебора традиционно используется так называемый метод ветвления, основанный на рекурсивном применении формулы полной вероятности по альтернативным состояниям очередного ребра. Ветвь отсекается при возможности получения точного значения для соответствующего графа.

Метод ветвления достигает максимальной эффективности при выполнении следующих условий:

1. Имеются точные формулы расчёта для сетей возможно большей размерности.

2. Используются различные формулы уменьшения размерности задачи, например, за счёт декомпозиции.

3. По возможности не допускается повторный расчёт при получении сходных структур на различных ветвях.

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

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск