Уровень алгоритма

Алгоритм аукциона: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
(Общее описание алгоритма)
 
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-a}}
 +
 
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
 
'''Алгоритм аукциона'''<ref>Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.</ref> предназначен для решения [[Задача о назначениях|задачи о назначениях]]. Алгоритм имитирует проведение аукциона, в ходе которого агенты повышают цену за назначение той или иной задачи. Алгоритм аукциона может быть реализован и в распределённой среде<ref>Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.</ref>, когда информации о текущих котировках поступают агентам с некоторым запаздыванием.
 
'''Алгоритм аукциона'''<ref>Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.</ref> предназначен для решения [[Задача о назначениях|задачи о назначениях]]. Алгоритм имитирует проведение аукциона, в ходе которого агенты повышают цену за назначение той или иной задачи. Алгоритм аукциона может быть реализован и в распределённой среде<ref>Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.</ref>, когда информации о текущих котировках поступают агентам с некоторым запаздыванием.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Информационный граф ===
 
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
+
 
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Auction algorithm]]

Текущая версия на 09:51, 7 июля 2022


1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм аукциона[1] предназначен для решения задачи о назначениях. Алгоритм имитирует проведение аукциона, в ходе которого агенты повышают цену за назначение той или иной задачи. Алгоритм аукциона может быть реализован и в распределённой среде[2], когда информации о текущих котировках поступают агентам с некоторым запаздыванием.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

  1. Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
  2. Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.