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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Решение Савинова Николая, отличное от решения Бессарабова Никиты (которое неверно в том виде, в котором я понимаю задачу).)
 
(→‎Решение Савинова Николая, отличное от решения Бессарабова Никиты (которое неверно в том виде, в котором я понимаю задачу).)
 
Строка 1: Строка 1:
−
== Решение Савинова Николая, отличное от решения Бессарабова Никиты (которое неверно в том виде, в котором я понимаю задачу). ==
 
  
−
 
−
 
−
Насколько я понимаю, вероятность успешной доставки сообщения между 2 точками равна произведению вероятностей надежности ребер. Мы хотим максимизировать эту величину. Прологарифмируем произведение, получим сумму отрицательных \ln(p_e). Значит, нужно минимизировать сумму уже положительных -\ln(p_e). А с такой задачей Дейкстра справится. То есть запускаем его на графе с весами -\ln(p_e).
 
−
[[Category:На проверку]]
 

Текущая версия на 18:27, 17 декабря 2012

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