<<
>>

Разработка и анализ алгоритма назначения цены

Запрет на использование одного ребра двумя путями — крайний случай; в боль- шинстве практических применений ребра могут использоваться несколькими пу- тями. Сейчас мы разработаем аналогичный алгоритм, базирующийся на методе на- значения цены, для случая, когда любое ребро может использоваться в c > 1 путей.
В только что рассмотренном случае без пересечений все ребра рассматривались как равные, а предпочтение отдавалось коротким путям. Эту схему можно представить как простую разновидность алгоритма назначения цены: пути должны «платить» за использование ребер, и у каждого ребра имеется стоимость. Сейчас будет рас- смотрена схема назначения цены, в которой ребра считаются более дорогими, если они использовались ранее, а следовательно, у них осталось меньше свободной про- пускной способности. При таком подходе алгоритм будет распределять свои пути вместо того, чтобы «сваливать» их на одно ребро. Мы будем называть стоимость ребра е его длиной ф, а длина пути определяется как сумма длин содержащихся в нем ребер: С(Р) = Jr . Параметр-множитель β используется для увеличения длины ребра при каждом его использовании очередным путем.

Greedy-Paths-with-Capacity:

Присвоить I = 0

Присвоить длину ребра e = 1 для всех e e E Пока удается найти новые пути

Пусть Pi - кратчайший путь, для которого при добавлении P. в множество путей ни одно ребро не используется более c раз, и соединяющий пару (s, t.), которая еще не была соединена Добавить i в I и выбрать путь P. для соединения s. с t.

Умножить длину всех ребер пути P. на β Конец Пока

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

Еще по теме Разработка и анализ алгоритма назначения цены:

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