Проталкивание предпотока (для программистов)
Мне кажется, что я вполне хорошо понимаю схему алгоритма проталкивания предпотока. Однако, мне совершенно непонятно, как такой алгоритм можно было придумать. Для того, чтобы алгоритм работал корректно, необходимо было придумать функцию высоты и её хитрое свойство, которое поддерживается инвариантым на протяжение всего алгоритма. Как интуиция может помочь до этого догадаться? Может быть, были уже какие-то похожие работы?
С другой стороны, алгоритм должен ещё и работать быстро. Для этого нужно, чтобы оценка на количество ненасыщающих проталкиваний была хорошей. Она такой и получается, конечно, если хитрым образом подобрать потенциальную функцию для оценки. Неужели это можно было предусмотреть заранее? Или это просто везение, что удалось так хорошо оценить?
В общем, у меня есть ощущение, что либо в корменовском изложении пропущено какое-то историческое звено, либо этот алгоритм был изобретён каким-то непостижижым insight'ом.
P.S. Если ответ не найдётся, то видимо можно попробовать спросить у самого Андрея Гольдберга, как же ему удалось такое придумать.
С другой стороны, алгоритм должен ещё и работать быстро. Для этого нужно, чтобы оценка на количество ненасыщающих проталкиваний была хорошей. Она такой и получается, конечно, если хитрым образом подобрать потенциальную функцию для оценки. Неужели это можно было предусмотреть заранее? Или это просто везение, что удалось так хорошо оценить?
В общем, у меня есть ощущение, что либо в корменовском изложении пропущено какое-то историческое звено, либо этот алгоритм был изобретён каким-то непостижижым insight'ом.
P.S. Если ответ не найдётся, то видимо можно попробовать спросить у самого Андрея Гольдберга, как же ему удалось такое придумать.