Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

2:09p

Обобщение сортировки Пусть дан конечный набор чисел A1,...An, занумерованных в неком порядке.
Тогда, кажется, алгоритм сортировки можно рассматривать, как поиск перестановки, минизирующий функционал: F(p)=Сумма ( abs(Ap(i+1)- Ap(i))} сумма берется по i=1,n-1, здесь p -элемент группы перестановок n элементов

Задача:

Пусть дана матрица {A(i,j) i=1,..,n; j=1,..,m .Требуется найти пару перестановок (p,g), минимизирующих функционал:
F(p,g)=Сумма ( abs(A(p(i+1),g(j+1)-A(p(i),g(j))} сумма берется по i=1,n-1,j=1,..,m-1, p -элемент группы перестановок n элементов,g-элемент группы перестановок m элементов.