Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 40: | Строка 40: | ||
Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент <math>(1 - \varepsilon) \;</math>, время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над <math>\mathcal{D} \cup \mathcal{F}</math>): | Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент <math>(1 - \varepsilon) \;</math>, время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над <math>\mathcal{D} \cup \mathcal{F}</math>): | ||
<math>T \le log_{1 / (1 - \varepsilon)} \bigg( \frac{f(C_0)}{f(C_T)} \bigg) \le \frac{log \ | <math>T \le log_{1 / (1 - \varepsilon)} \bigg( \frac{f(C_0)}{f(C_T)} \bigg) \le \frac{log \Big( \frac{f(C_0)}{f(C_T)} \Big)}{\varepsilon} \le \frac{log(nD)}{\varepsilon}</math>, | ||
являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление <math>f(C) \;</math> для <math>C \in \mathcal{E}_t</math>. Оно является полиномиальным относительно размера входных данных, поскольку <math>|\mathcal{E}_t|</math> предполагается полиномиальным. | являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление <math>f(C) \;</math> для <math>C \in \mathcal{E}_t</math>. Оно является полиномиальным относительно размера входных данных, поскольку <math>|\mathcal{E}_t|</math> предполагается полиномиальным. | ||