Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Генерация перестановок за минимальное число транспозиций.

При конструировании алгоритмов с использованием генерации перестановок, рассмотренные алгоритмы генерации в лексикографическом или антилексикографическом порядке иногда мало эффективны.

Пример. Пусть задана квадратная матрица вещественных чисел ||aij|| порядка n. Вычислить

åa[1,i1]×a[2,i2]×... ×a[n,in], (1)

где суммирование проводится по всем перестановкам <i1 i2 ... in> n-го порядка.

Выражение (1) называется перманентом [1] матрицы ||aij|| и весьма похоже на ее определитель. Заметим, что вычисление перманента или определителя непосредственно по определению имеет сложность O(n!), так как требуется генерация всех перестановок n-го порядка. Поэтому машинные алгоритмы вычисления определителей никогда не строятся непосредственно на его определении, а используют ряд его свойств, уменьшающих вычислительную сложность. Перманенты, однако, подобными свойствами не обладают, поэтому для их вычисления вполне приемлем подход, основанный на их определении. Остановимся на таком алгоритме подробнее.

Как уже отмечалось, подобный алгоритм требует генерирование всех перестановок n-го порядка. Однако генерация перестановок в лексикографическом или антилексикографическом порядке нецелесообразна. Здесь более желателен такой алгоритм генерирования, при котором каждая последующая перестановка отличалась бы от предыдущей на транспозиции только двух ее элементов.

Действительно, пусть последующая перестановка отличается от предыдущей на транспозиции [ik,ii], k¹j; тогда для того чтобы вычислить произведение, соответствующее последующей перестановке, не надо выполнять все n умножений, определяемые формулой (1), а достаточно, произведение, соответствующее, предыдущей, перестановке, умножить на a[j,ij]/a[k,ik], т. е. можно получить только за одно деление и умножение (считаем, что a[k,ik]¹0).

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

Пусть генерируемые элементы перестановки содержатся в массиве p[1],…,p[n] и имеется некоторая процедура PERM(m), генерирующая все перестановки элементов, хранящиеся в p[1],…,p[m], 1 £ m £ n, таким образом, что каждая последующая перестановка отличается от предыдущей одной транспозицией. Тогда генерирование перестановок n-го порядка может быть представлено как n обращений PERM(m-1), при условии, что при каждом очередном обращении элемент перестановки, хранящийся в p[n], заменяется на другой элемент из p[1],…,p[n-1] так, что элементы в p[n] не повторяются. В общем виде процедура PERM(m) может быть описана так:

procedure PERM(m: integer); {1 £ m £ n}

var i,k: integer;

{p, b – глобальные массивы}

begin

if m=1 then

{p[1], …, p[n] содержит новую перестановку}

for i:=1 to n do write (p[i])

else

for i:=1 to m do

begin PERM(m-1);

if i<m then

begin k:=p[m];

{*} p[m]:=p[b[m,i]];

p[b[m,i]]:=k

end

<== предыдущая лекция | следующая лекция ==>
LEC (1) | Тема 3. Генерация подмножеств множества
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 569; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.