Interview question

[Tatarin]

На работе мне задали вопрос чтобы я написал псевдо код для решения данной задачи.
Дано N генераторов которых могут вырабатывать мегаватты от мин и максимума. У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно. Надо найти нагруженность каждого генератора так чтобы нагрузка была распределена между N генераторами наиболее равномерно. Генератор может вырабатывать только в пределах данных мин и макс.

Как решить данную задачу?

Я за 45мин написал алгоритм но думаю неправильно.
Он заключается сначала в распределении нагрузки для генераторов для которых Х/N находится вне их пределов. Таким генераторам я присваивал их граничные значения (мин или макс)
После этого я пересчитывал новый Хremainder/Nnew где Nnew это количство неприсвоенных генераторов а Хremainder это не распределенная нагрузка. Короче я написал бред.
Не пинайте я. Я ЕЕ поэтому не силен в алгоритмах.
Спасибо.

[Komissar]

так это дали на текущей работе или на интервью?

[Tatarin]

да на текущей работе. it was a promotional interview.

[Komissar]

гоните в задницу такой промоушен. Все равно Вас скоро заменят сладкоречивым индусом.

[Tatarin]

ну это само собой:)

А по существу есть советы по алгоритму?

[Komissar]

скорее всего, там self-leveling regression. Типа, закидываете некие начальные параметры, а потом оно само должно устаканиться.

[Deynekin]

Я [...] написал алгоритм но думаю неправильно.

Какой-то очень странный стиль представления материала.
Речь сейчас не о безграмотном написании "думаю неправильно", возводящем вводное слово "думаю" в ранг полноценного сказуемого со смыслом, на который явно не рассчитывали: "[я] неправильно думаю", а о попытке заранее сделать себя кругом правым. Смысл этой "хитрости" — и свою мысль изложить, и тут же назвать её неправильной — очевиден: если алгоритм всё-таки будет признан верным, тогда получится вполне заслуженное: "Ага, я таки прав!" А если окажется неправильным — тогда: "Ага, я же сразу сказал, что это неправильно!" — и этим "я же сразу сказал" ...снова прав.
(Такой фортель только блондинкам прощается; у них ещё один похожий приём есть: "Я именно так с самого начала и думала, но почему-то сказала наоборот...")

А ведь всего-то и нужно было сказать: "я написал алгоритм, но не уверен, правильно ли это: ..." — и всё выглядело бы совершенно этично.

[helg]

Необходимо уточнить условие: как понимается "равномерно"? Можно словами функцию, которую оптимизируем, описать. А можно на примере. Есть два генератора. 1-10 и 1-100 МВт. Как в понимании заказчика правильно генерить 3, 10, 30 и 100 MBт?

[Физик-Лирик]

Необходимо уточнить условие: как понимается "равномерно"? Можно словами функцию, которую оптимизируем, описать. А можно на примере. Есть два генератора. 1-10 и 1-100 МВт. Как в понимании заказчика правильно генерить 3, 10, 30 и 100 MBт?

Тоже самое хотел спросить.
Воможно имеется в виду, что вариация распределения мощностей минимальна? Т.е есть N случайный чисел. Найти такую реализацию, при которой сумма равна Х, а вариация распределения минимальна?

[лопарь]

На работе мне задали вопрос чтобы я написал псевдо код для решения данной задачи.
Дано N генераторов которых могут вырабатывать мегаватты от мин и максимума. У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно. Надо найти нагруженность каждого генератора так чтобы нагрузка была распределена между N генераторами наиболее равномерно. Генератор может вырабатывать только в пределах данных мин и макс.

Как решить данную задачу?

Я за 45мин написал алгоритм но думаю неправильно.
Он заключается сначала в распределении нагрузки для генераторов для которых Х/N находится вне их пределов. Таким генераторам я присваивал их граничные значения (мин или макс)
После этого я пересчитывал новый Хremainder/Nnew где Nnew это количство неприсвоенных генераторов а Хremainder это не распределенная нагрузка. Короче я написал бред.
Не пинайте я. Я ЕЕ поэтому не силен в алгоритмах.
Спасибо.

Это задача выпуклой оптимизации.

[Физик-Лирик]

Может так.
Предположим вначале, что минимум нуль.
1) Если сумма максимумов меньше Х, тогда решения нет.
2) M = X/N.
3) Найдем все генераторы, для которых максимум меньше М. Запустим эти генераторы на максимум.
4) Перейти к пункту 2, где тепeрь N - число оставшихся генераторов (после пункта 3), а Х - оставшаяся мощность.

Если минимум не ноль:
1) Найти генераторы, для которых минимум больше М. Запустить их по минимуму.
2) Для оставшихся генераторов применить вышеизложенный алгоритм.

Хотя тут воможны ньюансы. Надо еще подумать.

[Физик-Лирик]

Это задача выпуклой оптимизации.

Для какой функции?

[лопарь]

Это задача выпуклой оптимизации.

Для какой функции?

Для функции "чтобы нагрузка была распределена между N генераторами наиболее равномерно" при условиях "У каждого генератор свои мин и макс и не обязательно одинаковые. Дано Х это нужное количество мегаватт которое должно генерироваться всеми генераторами вместе суммарно".

Какая конкретно функция минимизируется - зависит от того, что понимать под "распределена наиболее равномерно" (если неравномерно, то какова мера этой неравномерности?)

[Физик-Лирик]

Ну так давайте примем за данную функцию вариацию. Drugimi slovami:

L(G_1, ..., G_N) = SUM[G_i - X/N]^2 ;
Найти argmin L при условии:
SUM G_i = X; min_i <= G_i <= max_i.

Очевидно, что L = SUM G_i^2 - X^2/N. (последний член можно убрать).
Если убрать одну степень свободы, т.е. G_N = X - SUM' G_i, где теперь SUM' означает суммирование до N-1.
L' = SUM'(G_i^2) + (SUM' G_i)^2 - 2 X SUM' G_i. Теперь остались ограничения между min и max.

Похoже тепрь можно функцию Лагранжа выписывать и добавлять KKT условия.

[Физик-Лирик]

Похоже алгоритм, что я описал, должен сработать, если в качестве фукнции оптиизации взять вариацию.
У нас есть N величин. Их срeднее задано и равно Х/N.
1) Если все максимумы меньше среднего или если все минимумы больше среднего - решения нет.
2) Если все максимумы выше серднего, а все минимумы ниже среднего - ставим каждый генератор на среднее. Вариация нулевая. Задача решена.
3) Если часть минимумов выше среднего, ставим на минимум. Если часть максимум ниже серднего - ставим на максимум. Для оставшихся генераторов берем новое среднее значение с учетом того, что мы уже поставили часть генераторов на максимум и/или минимум (т.е. среднее для всех генераторов должно оставаться Х/N).
4) Повторяем пункт 3 для оставшихся генераторов.

Похоже получится типа рекурсивной функции.

[helg]

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

Рассмотрим идеальный случай, когда требуемая суммарная мощность больше суммарной минимальной мощности всех генераторов - то есть для решения задачи не надо никого выключать. Определим понятие "нагрузка сети" - от 0 до 100%. Когда требуемая мощность равна минимальной суммарной, нагрузка - 0%, когда она равна максимальной сумарной - 100%, посередине всё линейно. Точно таким же образом опеределим понятие нагрузки для каждого генератора. Очевидно, что если каждый из генераторов нагружен на X%, вся сеть нагружена на X%.

По требуемой мощности вычисляем процент нагрузки сети, и даём команду запустить каждый генератор на этот самый процент. Все генераторы загружены одинаково, да и алгоритм управления предельно прост.

Формально функцией, которая оптимизируется данным алгоритмом, будет минимальное суммарное квадратичное относительное изменение генерируемой мощности по всем генераторам при изменении нагрузки.

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

[Физик-Лирик]

Т.е. если я правильно понял, определим процент загрузки для генератора i как
P_I = (G_i - min_i) / (max_i - min_i).
Предположим, что процент загрузки одинаков, i.e. P_i = P. Отсюда G_i = P *(max_i - min_i) + min_i.
X = SUM G_i = P * SUM(max_i - min_i) + SUM min_i. Отсюда P = (X - SUM min_i) / SUM(max_i - min_i).
Т.к 0 <= P <= 1 получаем, что решений нет, если X < SUM min_i или X > SUM max_i.

Правильно ли я Вас понял в рамках Вашего определения равномерности?

Одим коммент. В моем алгоритме надо возвращаться из пункта 4 в пункт 1, т.е. снова проверять условия минимум и максимума.

[Tatarin]

В интервью вопрос звучал как "even distribution". Я понял это как разброс с минимальным среднеквадратичным отклонением. Подумав пару дней я пришел к выводу что можно было на интервью написать просто тупой перебор с N вложенными циклами вот так например. Обидно что я не догадался. Мне эта вакансия очень нравилась.

Code: Select all

max_std_dev=10^10;

for (i1=Gmin[1];i<=Gmax[1]; i1=i1+gstep)
  for (i2=Gmin[2];i<=Gmax[2]; i2=i2+gstep)
    for (i3=Gmin[3];i<=Gmax[3]; i3=i3+gstep)
     .... etc
         { 
            sum=i1+i2+....+iN;
            mean =sum/N;
            if (sum >X-delta)and(sum<X)                 //проверка если сумма нагрузок=Х
               {
                   std_dev=(i1-mean)^2+(i2-mean)^2+....+(iN-mean)^2   //standard deviation
                   if (std_dev<max_std_dev)               // сравниваем если разброс лучше
                      {
                        max_std_dev=std_dev;              // если да то обновляем рекорд 
                        // сохранить текущую нагрузку генераторов как лучшую

                }

[лопарь]

> Подумав пару дней я пришел к выводу что надо было на интервью написать просто тупой перебор с N вложенными циклами

N фиксировано и невелико? Что-то мне кажется, что вам бы такое решение не зачли. Хоть бы простейший градиентный спуск сделали, что ли. Заодно решили бы вопрос с произвольностью gstep.

У вас если есть, допустим, всего лишь 10 генераторов, а шаг вы выбрали довольно грубый - в десятую долю диапазона, то всего придётся сделать 10^10 итераций.

[Tatarin]

В нашей шараге где-то 12 генераторных станций разного вида поэтому наверное тупой перебор долго бы искал оптимальный разброс нагрузок генераторов.

Я только сейчас понял что я пытался решить эту задачу с точки зрения нагрузок наиболее близких к среднему числу Х/N. Но ведь even distribution можно понять как например разброс нагрузок когда каждый генератор нагружен так чтобы ближе к своему среднему пределу! Это наверное будет полезно для равномерного старения генераторов ведь тот который работает на пределе сломается раньше того который работает на минимуме, скорее всего.

Короче у меня соблазн появился написать двум интервьюрирам то что вопрос их был не совсем корректен. Это нормально будет описать если написать им до оглашения их выбора? Или просто подождать чтобы огласили выбор.

[лопарь]

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

[Физик-Лирик]

Нет, решение с циклами как-то не очень. Как правильно заметили, оно потребует много времени. Вы как бы делаете маленькие шажки для каждой переменной. Даже при умеренных N вычислительно неэффективно. Здесь еще могут быть проблемы, т.к у Вас есть "точность" делта и шаг цикла. Возможны неоднозначные решения (вопрос, конечно, решается).

Если равномерность определяется процентом загрузки, то решение уже выписано в "аналитической" форме.

[helg]

Короче у меня соблазн появился написать двум интервьюрирам то что вопрос их был не совсем корректен. Это нормально будет описать если написать им до оглашения их выбора? Или просто подождать чтобы огласили выбор.

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

Для того, чтобы показать заинтересованность, после интервью принято слать "thank you letter". Вот в этом письме про другое решение и сказать.

[Физик-Лирик]

По-моему, даже в случае минимизации среднеквадратического отклонения (т.е. вариации) есть аналитическое решение.
Обозначим через x_i - генераторы, e = X/N, диапазон работы генераторов: m_i = min_i, M_i = max_i.

f(x_1, ..., x_N) = SUM (x_i - e)^2 -> min,
условия:
SUM(x_i) =X, m_i <= x_i <= M_i.
Запишем функцию Лагранжа:
L = f(x_1, ..., x_N) - a * SUM(x_i - e)^2 - SUM b_i (x_i - m_i) - SUM g_i (M_i - x_i).
Первое необходимое условие миниума (условия Каруша-Куна-Такера):
dL/dx_k =0, т.е. x_k = 0.5 *(a + b_k - g_k + 2e);
SUM(x_k) = X
b_k *(x_k - m_k) =0
g_k * (x_k-M_k) = 0
b_k >= 0
g_k >= 0.
Собственно далее идет переборка, которую как раз мoжно делать в цикле.
Например, если x_k != m_k, x_k != M_k, тогда получим x_k = 0.5 * a + e. Далее X = SUM x_k = 0.5*a*N + e*N +> a = 0. Т.е. x_k = e = X/N, что очевидно сразу.
Допустим x_1 = m_1. Тогда x_1 = m_1 = 0.5*(a+b_1+2e); x_k = 0.5*a + e, k>1. X = m_1 + SUM' x_k. Из последних двух условий находим b_1 и a. При этом необходимо проверить, что b_1 >= 0. a_1 = 2(e-m_1)/(N-1). Про этом b_1 = 2(m_1-e)(1+1/(N-1)).
Т.к. b_1 должен быть >=0 имеем m_1 >= e. T.e сажаем x_1 на минимум, x_k = (X-m_1)/(N-1).

У нас есть цикл по b_i и g_i. По формулам находим все коэффициенты и решение. Проверям, что необходимые условия выполнены.

[goldenstate]

Я понимаю загрузку генератора как процент от 0 до 100% соответствующий его мин и мах. Так что 50% это к примеру (мах-мин)/2.

Если так, то уравнение получится: min1+delta1*P + min2+delta2*P + ... + minN+deltaN*P = X. Откуда находится неизвестное P (процент загрузки).