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

Решение Савинова Николая, отличное от решения Бессарабова Никиты (которое неверно в том виде, в котором я понимаю задачу).

Насколько я понимаю, вероятность успешной доставки сообщения между 2 точками равна произведению вероятностей надежности ребер. Мы хотим максимизировать эту величину. Прологарифмируем произведение, получим сумму отрицательных \ln(p_e). Значит, нужно минимизировать сумму уже положительных -\ln(p_e). А с такой задачей Дейкстра справится. То есть запускаем его на графе с весами -\ln(p_e).

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.