Вот ты выберешь b, хотя глобально оптимально выбрать c

после б ты выберешь с, потому что д глобально имеет больше вес, чем с

Проголосовал за "посты в блоге", хотя формат видео я одобряю, и, полагаю, для тех, кто не сидит на литкоде сутками, именно видео с живой речью будет полезнее.

Сергей Сема запугал всех в FAANG Interview, что все в своих сообщениях пишут в конце: “не выгоняйте, пожалуйста, если сочтёте за офтоп, государь милостивый” 😅

Сергей Сема запугал всех в FAANG Interview, что все в своих сообщениях пишут в конце: “не выгоняйте, пожалуйста, если сочтёте за офтоп, государь милостивый” 😅

мне кажется, что и во FLOOD банят за флуд ;D

Алгоритм дейкстры на каждом этапе берет еще непосещенную вершину с минимальной меткой. То есть на первом шаге ты пойдешь в b и поставишь метку 1 для b, пойдешь в вершину c и поставишь метку c. На втором шаге ты пойдешь из вершины b в d и поставишь вершине d метку 11. На третьем шаге ты возьмешь вершину c (потому что у тебя в очереде 2 вершины с метками 2 - c и 11 - d) и пойдешь из нее в вершину d и поставишь метку 3. Конец алгоритма. Конец алгоритма в дейкстре считается момент, когда все вершины были посещены.

Оба варианта хорошие

то есть жадный алгоритм не в том смысле, что тупо идёшь туда где меньший вес, а в том что сперва готовишь «оптимальный переход» и принимаешь уже жадное решение после.

Собственно без разницы, как формируется оптимальный переход. Хоть в один шаг, хоть в 10. Суть же в принятии жадного решения, которое может не являться глобально оптимальным

Ведь ситуация когда не все вершины посещены, но ответ уже есть, очень даже реален

А как проверить, что то, что у тебя есть - минимального веса?

так в любом случае ты их должен посетить, чтобы проверить, что у них метка больше, чем у тебя есть

Ведь ситуация когда не все вершины посещены, но ответ уже есть, очень даже реален

Но момент, когда ответ уже есть, не отследить

Если выбирать всегда наименьшую непосещенную вершину, то отследить

Ты выбираешь минимум и релаксируешь значения у соседей

Ну вот если у тебя минимум в конечной точке, то это и есть ответ, даже если ты посетил не все вершины

Когда всех соседей перебрал

Но как можно получить значение меньше, если все остальные вершины уже больше?

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

Так я про это и говорю, ты не можешь получить меньше, ведь из всех оставшихся вершин значение уже больше того, что в конечной точке

А конечная в нашем случае это какая вершина?

Конечная это конечная

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

под посты можно музычку слушать

в видосах я уже вставил музычку на фоне за тебя 😂

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

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

в видосе разбираются примеры и показывается как проектировать алгоритм, блог это другое - здесь используем магию тут возьмем единорога и вот готовый код с решением каждому свое, но мне лучше на данном этапе развития видосы

нужна помощь: а какие классические задачи на жадный алгоритм можно привести и какие есть примеры наоборот, где жадный алгоритм не очевиден, но очень отлично ложится на решение?

а если нужен пример где просится жадинка, но на самом деле не работает, то это классическая задача на дп про размен монет.

а чем блог отличается? я примерно вот про такие посты говорю https://vitkarpov.me/posts/longest-inc-path-in-a-matrix/

на примере, ссылки ты показываешь как ты решаешь задачу, здесь скелет и код, здесь рекусрия и код с решение + дополния в видое, ты разбираешь примеры и показываешь как спроектировать алгоритм дальше уже можно на основании этих двух частей решить/решать самому, хоть на js, хоть на питоне, хоть на чем знаешь ведь главнее же навык решения задач, чем посмотреть как она решается, имхо

@vitkarpov а ты сис. диз проходил в aws? Готовлюсь к сис. дизу (не в aws), вот думаю посмотреть cockroach, TiDB, vitess и подобные, тоже самое по batch processing. Это оверкил для интервью или стоит?

Не API, а абстракт описание систем, почему, как и зачем, алгоритмы консенсуса и т.д.

Я для себя нашел блог eng.uber.com Это какой-то кладезь сис. диза

возможно сис. диз. будет просто нарисовать ручки своего реста 😄