Планирование опроса

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

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

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

Еще по теме Планирование опроса:

  1. Планирование телепередач
  2. Планирование, а не планы
  3. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  4. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  5. 10.2. Планирование и организация следственных действий
  6. 5.4. Планирование упражнений
  7. Искусство планирования спонтанного
  8. 5.9. Планирование социальных контактов
  9. 5.2.9. Планирование сроков достижения уже определённой цели
  10. Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
  11. 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)
  12. ОПРОС АНКЕТНЫЙ
  13. БЛИЦ-ОПРОС
  14. Первая беседа-опрос.
  15. Телефонный опрос