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

Версия 16:22, 17 декабря 2012

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

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