Разработка алгоритма

Мы решим эту задачу преобразованием к задаче циркуляции для потоковой сети G' с уровнями потребления и нижними границами, показанными на рис. 7.16. Чтобы получить граф G' из G, мы ориентируем ребра G от клиентов к продуктам, добав- ляем узлы 5 и t с ребрами (5, i) для каждого клиента i = 1, ..., n, ребрами (j, t) для каждого продукта j = 1, ..., к и ребром (t, 5).
Циркуляция в такой сети соответствует распределению вопросов. Поток в ребре (5, i) определяет количество продуктов, включаемых в анкету для клиента i, поэтому ребро будет иметь пропускную спо- собность с'. и нижнюю границу сПоток в ребре (j, t) соответствует количеству клиентов, которым задаются вопросы о продукте j, поэтому ребро будет иметь пропускную способность рj и нижнюю границу р. Каждое ребро (i, j), проходящее от клиента к купленному им продукту, имеет пропускную способность 1 с нижней границей 0. Поток, передаваемый ребром (t, 5), соответствует общему количеству заданных вопросов. Мы можем присвоить этому ребру пропускную способность и нижнюю границу У всех узлов уровень потребления равен 0.

Наш алгоритм должен просто построить сеть G' и проверить, существует ли в ней действительная циркуляция. Сформулированное ниже утверждение уста- навливает правильность этого алгоритма.

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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем