<<
>>

Задача

Рассмотрим следующий сценарий: имеется множество S из n мест — допустим, n маленьких городков в сельской части штата Нью-Йорк. Требуется выбрать к мест для строительства больших торговых комплексов.
Предполагается, что население каждого из n городков будет посещать один из торговых комплексов, поэтому ме- ста для строительства к торговых комплексов должны находиться в центральных точках.

Начнем с формального определения входных данных нашей задачи. Имеется целое число к, множество S из n мест (соответствующих городкам) и функция рас- стояния. Для экземпляров задачи, в которых местами являются точки на плоскости, функция расстояния будет стандартным евклидовым расстоянием между точками, а любая точка на плоскости может рассматриваться для размещения центра. Тем не менее разработанный нами алгоритм может применяться и для более общей концепции расстояния. На практике под расстоянием часто понимается расстояние по прямой, но также может пониматься время перемещения от точки 5 в точку z или расстояние вдоль дороги и даже расходы на перемещение.

Допускается лю- бая функция расстояния, обладающая следующими естественными свойствами:

♦ dist(s, s) = 0 для всех s ^ S;

♦ симметричность: dist(s, z) = dist(z, s) для всех s, z S;

♦ неравенство треугольника: dist(s, z) + dist(z, h)>dist(s, h).

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

Затем необходимо прояснить, что же подразумевается под размещением «в центре». Пусть C — множество центров. Предполагается, что жители каждого городка посещают ближайший торговый комплекс. Это подсказывает, что рассто- яния от места s до центров должны определяться в виде dist(s, C) = min ^ist(s,с). Множество C образует r-покрытие, если каждое место находится на расстоянии не более r от одного из центров, то есть если dist(s,C) < r для всех мест s S. Ми-

нимальное значение r, для которого C образует r-покрытие, называется радиусом покрытия C и обозначается r(C). Другими словами, радиус покрытия множества центров C определяется как максимальное расстояние, которое необходимо про- ехать, чтобы попасть к ближайшему центру. Нашей целью является выбор множе- ства C из k центров, для которых величина r(C) минимальна.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения