Несложно о сложности. Примеры алгоритмов/Задачи/ex-network-reliability — различия между версиями
Материал из DISCOPAL
| Строка 4: | Строка 4: | ||
Решение (SteninSergey): | Решение (SteninSergey): | ||
| − | Необходимо максимизировать произведение вероятностей прохождения сигнала на каждом маршруте от данного узла до всех остальных. Алгоритм Дейкстры умеет находить пути с максимальной суммой весов. Сведем нашу задачу к задаче кратчайшего пути (SPP). Для этого вес (вероятность), записанную на каждом ребре заменим на минус логарифм этой вероятности. Тогда вместо максимизации | + | Необходимо максимизировать произведение вероятностей прохождения сигнала на каждом маршруте от данного узла до всех остальных. Алгоритм Дейкстры умеет находить пути с максимальной суммой весов. Сведем нашу задачу к задаче кратчайшего пути (SPP). Для этого вес (вероятность), записанную на каждом ребре заменим на минус логарифм этой вероятности. Тогда вместо максимизации произведения надо будет минимизировать сумму расстояний, то есть применИм алгоритм Дейкстры. Минус логарифмом нуля формально будем считать плюс бесконечность. |
[[Category:На проверку]] | [[Category:На проверку]] | ||
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
Версия 09:52, 12 сентября 2014
Решение (SteninSergey): Необходимо максимизировать произведение вероятностей прохождения сигнала на каждом маршруте от данного узла до всех остальных. Алгоритм Дейкстры умеет находить пути с максимальной суммой весов. Сведем нашу задачу к задаче кратчайшего пути (SPP). Для этого вес (вероятность), записанную на каждом ребре заменим на минус логарифм этой вероятности. Тогда вместо максимизации произведения надо будет минимизировать сумму расстояний, то есть применИм алгоритм Дейкстры. Минус логарифмом нуля формально будем считать плюс бесконечность.