Найти минимальные функции

Question

ОК, вот сделка. У меня есть набор линейных функций, * * + b.

Моя цель - ответить на следующий вопрос/вопрос: Какова минимальная функция при x = q?

Например: Если у меня есть функции f (x) = 3 * x + 2, g (x) = 5 * x - 6 и h (x) = 2 * x + 1, я отвечу, например:

• при х = 4, функция Н

• при х = 2, функция г

• при х = 1, функция г

Моя идея выглядит следующим образом:

1. Сортировать функции по коэффициенту х, в порядке убывания.

2. Сортировать запросы в порядке возрастания

3. Избавиться от параллельных функций, сохранить те, с наименьшим постоянным слагаемым (например: если я f (х) = 2 * х + 4 и г (x) = 2 * x + 2, f (x) никогда не будет меньше g (x), поэтому мне не нужно f (x)).

4. Прямо сейчас я нахожусь на интервале от -inf некоторого вещественного числа, назовем его w1, и я знаю, что на этом отрезке функция с наивысшим коэффициентом линейного является наименьшим

5. Найти w1, находя наименьшая x1-я f (x1) = g (x1), где f - моя текущая функция, и g проходит через все другие функции с меньшим линейным коэффициентом, w1 = x1

6. Повторяйте до тех пор, пока мой запрос находится в интервале (-inf, w1): вывести текущую функцию, а затем перейти к следующему запросу.

7. Если у меня все еще есть запросы, на которые нужно ответить, пусть текущая функция будет той, которая пересекает мою текущую текущую функцию в x = w1, а вместо -inf put w1 повторите те же шаги.

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

Заранее спасибо.

Answer 1

Вы не могли бы просто решить свои перекрестки и сохранить наибольшую функцию для каждого интервала в домене?

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

Вот сюжет ваших трех примерных функций.

интервалы (с соответствующей минимальной функции) этого графа будет

(-∞, 7/3]  => 5x - 6 
(7/3, ∞]  => 2x + 1 

Теперь, во время выполнения, а не «Какова минимальная функция при х = д» вы просто сделать «Какой интервал q принадлежит«.

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

Answer 2

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

На самом деле есть две фазы: «подготовка» и «запрос» (где указан конкретный x вы даете результат).

Какое у вас затруднение?

Естественно, что фаза «запроса» должна быть быстрой, вы должны упорядочить диапазоны в виде отсортированного массива, чтобы вы могли найти диапазон, охватывающий заданный x, медианным поиском (или подобным) в логарифмическом времени , Если это то, что вы сделали, и все же это недостаточно быстро - рассмотрите оптимизацию на уровне кода, поскольку с алгоритмической точки зрения это представляется наиболее оптимальным решением.

Если ваше узкое место является фазой «подготовки» - здесь есть возможности для оптимизации. Насколько я понимаю, вы находите пересечения всех пар ваших функций (после устранения параллельных). И это не обязательно.

Рассмотрите следующее. Сначала вы сортируете все свои функции по их коэффициенту (более высокие коэффициенты находятся в начале). Избавиться от параллельных функций. Затем создайте массив диапазонов, итерации через ваши функции.

Поскольку текущая функция имеет самый низкий коэффициент (среди тех, которые уже были проанализированы) - текущая функция будет самой маленькой, так как x переходит в бесконечность. Так что его диапазон должен быть от x0 до бесконечности. Найдите это x0. Возьмите последний диапазон из массива (принадлежащий ранее обработанной функции) и найдите x0 - пересечение этой функции с текущим. Первый диапазон сокращается до x0. Если этот диапазон становится недействительным (начало диапазона больше x0) - означает, что эта функция полностью закрыта. В таком случае - удалите этот диапазон и повторите процедуру.

Чтобы сделать более ясно, что я буду писать псевдо-код:

rangeArr является массивом пар F,X, тогда как F является описание функции, а X это начало диапазона функции. Конец диапазона функций считается началом следующего диапазона, а конец последнего диапазона функций - + бесконечность.

for each F sorted by coefficient 
{ 
    double x0; 

    while (true) 
    { 
     if (rangeArr is empty) 
     { 
      x0 = -inf; 
      break; 
     } 

     FPrev = rangeArr.back().F; 
     xPrev = rangeArr.back().X; 

     x0 = IntersectionOf(F, FPrev); 

     if (x0 > xPrev) 
      break; 

     rangeArr.DeleteLastRange(); 
    } 

    rangeArr.InsertRange(F, x0); 
}