Несложно о сложности. Примеры алгоритмов/Задачи/ex-network-reliability — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 15 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
</latex>
 
</latex>
  
−
Решение (SteninSergey):
 
−
Необходимо максимизировать произведение вероятностей прохождения сигнала на каждом маршруте от данного узла до всех остальных. Алгоритм Дейкстры умеет находить пути с максимальной суммой весов. Сведем нашу задачу к задаче кратчайшего пути (SPP). Для этого вес (вероятность), записанную на каждом ребре заменим на минус логарифм этой вероятности. Тогда вместо максимизации суммы надо будет минимизировать расстояния, то есть применИм алгоритм Дейкстры. Минус логарифмом нуля формально будем считать плюс бесконечность.
 
  
−
[[Category:На проверку]]
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
 +
 +
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

Источник — «https://discopal.ispras.ru/index.php?title=Несложно_о_сложности._Примеры_алгоритмов/Задачи/ex-network-reliability&oldid=11062»