Алгоритм Дикстры

Шаблон:Не путать

Алгоритм Дикстры — метод нахождения точки из пересечения выпуклых множеств. Является вариантом метода поочерёдного проецирования, известного также как метод проецирования в выпуклые множества. В простейшем варианте метод находит точку из пересечения двух выпуклых множеств путём итеративного проецирования в каждое из них. Метод отличается от метода поочерёдного проецирования наличием промежуточных шагов. Параллельную версия алгоритма разработали Гафке и Матар.

Метод назван именем Ричарда Л. Дикстры, предложившего его в 1980-х годах.

Ключевое отличие между алгоритмом Дикстры и методом стандартного поочерёдного проецирования возникает в случае, когда пересечение двух множеств состоит из более чем одной точки. В этом случае метод поочерёдного проецирования даёт некоторую произвольную точку в пересечении, в то время как алгоритм Дикстры даёт вполне определённую точку — проекцию точки r в пересечение, где r — данная алгоритму начальная точка.

Алгоритм

Алгоритм Дикстры находит для каждой точки $r$ единственную точку в $\bar{x} \in C \cap D$ , такую что:

‖ \bar{x} - r ‖^{2} ⩽ ‖ x - r ‖^{2},

для всех

x \in C \cap D,

где $C, D$ являются выпуклыми множествами. Эта задача эквивалентна поиску проекции точки $r$ во множество $C \cap D$ , которую мы обозначим $𝒫_{C \cap D}$ .

Чтобы использовать алгоритм Дикстры, нужно знать, каким образом находить проекцию точки во множества $C$ и $D$ по отдельности.

Сначала рассмотрим метод поочерёдного проецирования (типа POCS) (который исследовал первоначально для случая, когда множества $C, D$ являются линейными подпространствами, Джон фон Нейман Шаблон:Sfn). Метод стартует с точки $x_{0} = r$ и создаёт последовательность

x_{k + 1} = 𝒫_{C} (𝒫_{D} (x_{k}))

.

Алгоритм Дикстры имеет аналогичный вид, но использует дополнительные переменные. Метод начинает с $x_{0} = r, p_{0} = q_{0} = 0$ и обновляет переменные по формулам