Поиск оптимального маршрута. Постановка задачи.

В этот понедельник с утра ребята спешили на работу. Ещё бы, нужно было прийти к 12:00 на планирование спринта! Свободный график — это здорово, но гибкие методологии разработки, скрам и всё такое...

Собрание прошло как обычно. Все получили задачи и пошли, кто код писать, кто ревью делать, кто статьи на хабре читать, кто новую кофемашину тестировать. Работать, в общем.

Гоше досталось очень ответственное задание. То есть ответственное оно было по словам руководителя. Картинка: руководитель: мы хотим оптимизировать работу всех наших серверов. Нужно доставлять на них обновления софта оптимальным способом. Некоторые из них в конкретный момент времени могут не работать или просто быть слейвами, нужно распространять пакеты на мастер-сервера. Распространять софт нужно по цепочке. Если на каком-то шаге не получилось поставить обновление, откатываемся. Так как картина может очень быстро меняться, нужно использовать быстрый алгоритм.

Гоша: Да-да, конечно, Иннокентий Еремеевич, изи задачка! Пойду потроллю Риту, покормлю рыбок в аквариуме и буду код писать!

И в общем-то сегодня уже пятница. Обычно в этот день проводится ретро, на котором все рассказывают о своих успехах за неделю.

Иннокентий особенно поинтересовался, как идут дела у Георгия с его задачей. Георгий сказал, что уже давно закомитил код, и он в ревью. Руководитель открыл репозиторий и начал смотреть.

Иннокентий: Расскажи-ка нам, что ты тут такое понаписал и как пришёл к такому решению?!

Гоша: Ну, это долгая история... Первой версией, значит, было по очереди на все сервера отправлять пакет и в случае неудачи останавливать процесс. Но потом Тимофей написал комментарий, что главный сервер не соединён со всеми напрямую. Так что пришлось подумать. Ну подумал я и вот к чему пришёл. У всех серверов есть id. Начинаем с главного сервера, остальные сортируем по их id. Проходим, значит, по этому списку, если к следующему пути от текущего нет, добавляем его в очередь и переходим к следующему. И каждый раз, когда у нас новый сервер, проверяем, можно ли из него попасть в те, которые в очереди. Вроде работает, я проверял! Даже тест написал, целых два теста!

Иннокентий: И какая сложность у этого алгоритма?

Гоша: Ну... Если сравнивать с моим первым вариантом, то по десятибалльной шкале я бы поставил 9 или даже 9,5. Пришлось с ним повозиться конечно! Но он готов! Ура!

Иннокентий: Ты шутишь?

Гоша: Нет, не шучу, правда готов.

Тимофей: Георгий, вопрос про алгоритмическую сложность. «O» большое и всё такое.

Гоша: Ах, это! Я немного подзабыл эту академическую информацию. Я всегда думал, что программисты в наше время в основном другими задачами занимаются.

Иннокентий: Георгий, я говорил, что решение должно быть эффективным. К тому же у нас в планах выход в новые регионы, и, соответственно, подключение новых серверов. Это нужно переписать!

Гоша: Да-да, я понял, конечно!

И пошёл Гоша думать над новым решением. Что-то гуглил из стандартной библиотеки, исследовал GitHub, пробовал добавлять побольше очередей, искал что-то существующее в проекте... И вот так настал вечер пятницы.

Алла: Гоша, ты чего сидишь, мы же в бар собирались!

Рита: Сегодня пятница, хватит работать!

Гоша: Ребят, вы идите, а я ещё подумать над задачей хотел.

Все ушли, и остался Георгий наедине со своим неэффективным алгоритмом, ну и рыбками в аквариуме.

Интересно, думает Гоша, вот это плывёт рыбка — самка или рыбка — самец?

Чтобы понять, откуда получилось это число, разберёмся, что такое вероятность.

Вероятность — количественная оценка возможности наступления какого-то события.

Вероятность может находиться в отрезке от 0 до 1. Если известно, что событие точно наступит, то его вероятность равна 1. Если событие точно не наступит, то вероятность — 0.

Испытание — какое-то действие. Например, подбрасывание монеты.

Исход — результат испытания.

Исход называется благоприятным для события, если при таком исходе событие наступило. Например, если событие — выпадение чётного числа при бросании игральной кости, то выпадение двойки — благоприятный исход. Выпадение четверки и шестёрки — тоже. Выпадение любого другого числа — нет.

Чтобы вычислить вероятность события, нужно разделить число благоприятных исходов на общее число возможных исходов.

Событие: рыбка оказывается самкой.

Всего в аквариуме 12 рыбок. То есть общее число возможных исходов 12.

Среди них 4 самки. То есть число благоприятных исходов 4.

Получим, что вероятность события равна 4 / 12 = 0.33. Результат округлён до двух знаков после запятой.

Вы ещё будете сталкиваться с теорией вероятностей далее в курсе.

Сидел Гоша, смотрел на рыбок, и думал над задачей. Его начало клонить в сон. «Вообще, с закрытыми глазами иногда лучше думается», — решил он и прилёг у ноутбука.

С закрытыми глазами хорошо думается, но ещё лучше с закрытыми глазами спится! В общем, заснул Гоша. И начали ему сниться разные алгоритмические задачи.

А именно, задачи G, H и I: https://contest.yandex.ru/contest/18360/problems/G/