2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение30.08.2015, 08:44 
Итак, чуть продвинулся вперед:
1) Доказал, что максимум произведения $PC_1\cdot PC_2$ достигается при $PC_1=PC_2=\frac{PC_0}{2}$. Подтверждаются Ваши слова: максимум 1 бит можно ожидать от сравнения двух чисел.
2) Доказал, что если взять два одинаковых дерева и сравнить их корни, то из них получится дерево, имеющее вдвое меньшее число перестановок $PC$. Примечательно, что это значение не обладает свойством случайности.
3) Изначально имеем $n$ одновершинных деревьев. Это базис индукции, шаг индукции был обозначен в п. 2. Для простоты принял, что число $n$ - является степенью двойки (32, 64, 128 и т.д.). По индукции определил, что за первые $(n-1)$ итераций оптимальный алгоритм должен построить хитрое дерево из $n$ вершин.
4) Это первый этап алгоритма, далее идет какой-то другой алгоритм, так как дерево осталось одно. Придется доказывать другие утверждения.
5) Количество итераций жадного алгоритма составляет не менее $n-1$ и такой алгоритм на некоторых особенных массивах будет проигрывать более удачливым алгоритмам типа быстрой сортировки (QUICK-SORT) и т.д. Первая часть алгоритма получается устойчивая, то есть количество итераций и время работы не зависит от значений чисел массива, которые нужно сортировать.
6) Очевидно алгоритм соответствует принципу "разделяй и властвуй". Алгоритм в каком-то смысле очень похож на алгоритм пирамидальной сортировки (HEAP-SORT), который также состоит из двух частей - первые $\left\lfloor\frac{n}{2}\right\rfloor$ итераций создается куча (heap), а во второй части алгоритма эта куча сортируется.
7) Пока не доказано, единственный ли такой алгоритм.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение30.08.2015, 10:35 
Mihaylo писал(а):
2) Доказал, что если взять два одинаковых дерева и сравнить их корни, то из них получится дерево, имеющее вдвое меньшее число перестановок $PC$. Примечательно, что это значение не обладает свойством случайности.

Доказал более общее утверждение:
Если сравнить корни двух произвольных деревьев с количеством вершин $n_1$ и $n_2$, то число перестановок $PC$ изменится в $\frac{n_1^2+n_2^2}{(n_1+n_2)^2}$ раз.

Отсюда следует, что, если сравнить произвольные деревья с одинаковым количеством вершин $n_1=n_2$, то число перестановок уменьшится вдвое. То, что надо.

После работы первой части алгоритма сортировки определяется максимальное (или минимальное) число массива. Это число уже отсортировано и его можно убрать из рассмотрения. В результате дерево из $n$ вершин рассыпается на $\log_2(n)$ деревьев с разным числом вершин: 1, 2, 4, 8, ..., $\frac{n}{2}$. В связи с этим прежний алгоритм сравнения корней не будет давать оптимальный результат. Не совсем пока ясно, существуют ли иные варианты сравнения, которые дают результат более близкий к 1 биту...

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение02.09.2015, 21:01 
Mihaylo писал(а):
Если сравнить корни двух произвольных деревьев с количеством вершин $n_1$ и $n_2$, то число перестановок $PC$ изменится в $\frac{n_1^2+n_2^2}{(n_1+n_2)^2}$ раз.

Если я не ошибся в своих дальнейших логических выводах, то удается доказать еще более полезное утверждение:
Если сравнить корень любого дерева, который получился в результате работы первой части жадного алгоритма, с произвольной вершиной другого дерева из этой группы, то число перестановок никогда не уменьшится ровно в два раза. То есть такие сравнения не дадут идеальный результат.

Это утверждение очень сильное, но пока недостаточное, чтобы успокоиться. :D Хотя, наверное, пора уже успокоиться и искать-таки решение, а не доказательства о несуществовании.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение05.09.2015, 15:33 
Аватара пользователя
Mihaylo в сообщении #1049997 писал(а):
Если сравнить корень любого дерева, который получился в результате работы первой части жадного алгоритма, с произвольной вершиной другого дерева из этой группы, то число перестановок никогда не уменьшится ровно в два раза. То есть такие сравнения не дадут идеальный результат.
1-ю часть я понимаю иначе: в результате $\sim\log_2n$ сравнений все элементы соберутся в одном дереве, вид которого мы знаем. Дальше можно уступить в "жадности", но добавить "системности", на каждом шаге 1)сохраняя регулярное (без срастаний) дерево 2)сравнивая элементы так. что вероятности исходов сравнения отличаются не более чем вдвое (а число перестановок в дереве уменьшится, как минимум в полтора раза)
И так можно, пока не получится линейное дерево, что значит: гарантированное упорядочение за не более чем $\log_{3/2}(n!)$ сравнений. Менее чем вдвое хуже по числу сравнений, чем теоретический минимум $\log_2(n!)$
Но в силу того, что мы описываем алгоритмы в совсем других терминах, чем описаны известные - затрудняюсь сказать, близок ли он к известным. Ну и по удобству реализации неясно, слежение за деревом или за матрицей смежности - это тоже время.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 01:09 
iancaple писал(а):
Но в силу того, что мы описываем алгоритмы в совсем других терминах, чем описаны известные - затрудняюсь сказать, близок ли он к известным. Ну и по удобству реализации неясно, слежение за деревом или за матрицей смежности - это тоже время.

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

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 07:47 
Mihaylo писал(а):
конечный результат сортировки не сильно важен

Я имею в виду следующее: прогнав массив данных через первую часть алгоритма, сортировка заканчивается и результат выводится. В первой части алгоритма каждый элемент массива поучаствовал в сравнении - это уже хорошо, получились "более-менее структурированные данные" с минимумом энтропии.

Я еще вот что думаю: принцип минимизации энтропии можно также применять для самообучающихся алгоритмов, в части генерирования гипотез. Самообучающийся алгоритм должен выбирать из множества гипотез такую, которая дает наименьшее математическое ожидание энтропии. Не знаю, есть ли работы в этом направлении.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 17:28 
Аватара пользователя
На этом примере никакой разницы между 1)минимизацией энтропии (максимизацией информации), 2)минимизации матожидания числа оставшихся вариантов и 3) обычным принципом минимакса (минимизировать время работы для наихудшего стечения обстоятельств) наблюдать не будем, т.к. мы имеем дело со сравнениями, у которых 2 исхода.
Но мне было интересно взглянуть на такую известную тему и с этих позиций

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 18:36 
Нигде в литературе в принципе не попадалось исследование энтропии рекурсивных алгоритмов. Измеряют только сложность алгоритма как время выполнения, объем используемой памяти. Сложность и энтропия не имеют прямой связи, хотя коррелируют.

Вообще для любого алгоритма можно вычислить изменение энтропии во времени, для рекурсивных алгоритмов это особенно интересно, у них получается зависимость "энтропия-итерация" вида $H(i)$. Вот, например, для алгоритма Евклида нахождения НОД двух чисел $a$ и $b$ справедлива зависимость $H(i)=\log[\max(r_i,1)]$, где $r_i$ - это остаток от деления, полученный в $i$-й итерации; при этом считать $r_0=\infty$, $r_1=\min(a,b)$, итерация $i=0$ соответствует моменту времени до начала выполнения алгоритма.

Самое интересное, что если функция $H(i)$ зависит только от $i$, то тогда алгоритм является устойчивым - время его работы не зависит от входных данных. Иначе алгоритм неустойчивый. Если при определенных входных данных энтропия $H(i)$ при некотором $i$ принимает нулевое значение, значит алгоритм способен выполнить задачу. Это, правда, не означает, что алгоритм останавливается... Короче, этот факт лишь подтверждает, что энтропия и сложность - это разные понятия. :-)

Некоторое время не мог придумать какую-нибудь полезную отдачу от вычисления $H(i)$... Не знаю, может в этом кроется какой-нибудь гораздо более мощный инструмент, чем кажется?

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 19:25 
Mihaylo в сообщении #1050833 писал(а):
Я имею в виду следующее: прогнав массив данных через первую часть алгоритма, сортировка заканчивается и результат выводится. В первой части алгоритма каждый элемент массива поучаствовал в сравнении - это уже хорошо, получились "более-менее структурированные данные"
Для «почти сортировки» разве поле алгоритмов не распахано, если уже не поперёк, то хотя бы вдоль? Кажется, краем уха что-то на эту тему слышал.

Сортировки «до конца» с минимумом сравнений хотя бы у Кнута в «Искусстве…» (том 3) рассматриваются, хотя особо не вчитывался, чтобы сравнить.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение06.09.2015, 19:52 
Что касается алгоритма сортировки: первая часть алгоритма настолько жадная, что трудно придумать разумно устроенную вторую часть алгоритма - граф сортировки хоть и может сохранять свойство "дерево", но структура леса становится столь нерегулярной - сильно зависит от входных данных. При любом дальнейшем алгоритме придется использовать дополнительную память для хранения истории сравнений (=структура графа сравнения).
Предлагаю придерживаться алгоритма со следующими свойствами:
1. Сравнивать между собой только корни деревьев - это позволит поддерживать свойство структуры данных "лес".
2. Структуру графа сравнения хранить в массиве $T[i]$, где $i$ - это номер элемента в сортируемом массиве $A[i]$. $T[i]$ - это число вершин, входящих в поддерево $i$-го элемента. Чтобы перейти к следующему дереву или поддереву, достаточно увеличить $i$ на величину $T[i]$. Если происходит выход за пределы, то значит деревьев и поддеревьев больше нет.
3. Сравнивать корни двух крайних левых деревьев леса. Пусть $i$ - это номер корня самого левого дерева.
3.1. Если корень самого левого дерева больше следующего ($A[i]>A[i+T(i)]$), то достаточно изменить $T[i]$ этого корня: $T[i]:=T[i]+T[i+T[i]]$ - это операция сращивания двух левых деревьев. :D
3.2. Иначе придется обменивать самое левое дерево с корнем дерева правее. Довольно затратная операция, но все же. После обмена также изменить $T[i]$ по формуле выше (операция сращивания).

Возможно данный алгоритм очень даже оптимальный по нашему критерию?

-- 06.09.2015, 22:02 --

arseniiv писал(а):
Для «почти сортировки» разве поле алгоритмов не распахано, если уже не поперёк, то хотя бы вдоль? Кажется, краем уха что-то на эту тему слышал.

Может речь шла о сортировке частично сортированных массивов? Про такие алгоритмы я слышал, например, алгоритм TimSort применяется в ОС Android.
arseniiv писал(а):
Сортировки «до конца» с минимумом сравнений хотя бы у Кнута в «Искусстве…» (том 3) рассматриваются, хотя особо не вчитывался, чтобы сравнить.

Спасибо, еще раз загляну в этот труд.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение07.09.2015, 04:51 
Mihaylo в сообщении #1050998 писал(а):
при этом считать $r_0=\infty$, $r_1=\min(a,b)$,

Извините, поторопился. Конечно же достаточно считать $r_0=\min(a,b)$, никаких бесконечностей.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение07.09.2015, 17:55 
Mihaylo в сообщении #1051036 писал(а):
Может речь шла о сортировке частично сортированных массивов?
Да вроде бы и о частичной сортировке любых.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение08.09.2015, 05:40 
Пролистал рунет и англоязычный интернет - все частично сортируют с помощью ограничения количества итераций уже известных алгоритмов полной сортировки. Это ограничение для некоторых алгоритмов иногда небанально, поэтому тут умудряются делать достаточно сложные расчеты, сравнение...
Может имеется спецлитература по алгоритмам сортировки?

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение08.09.2015, 13:07 
У меня, увы, нет.

 
 
 
 Re: Количество размещений "кактуса" по n (комбинаторная задача)
Сообщение08.09.2015, 18:06 
Mihaylo писал(а):
Предлагаю придерживаться алгоритма со следующими свойствами:
1. Сравнивать между собой только корни деревьев - это позволит поддерживать свойство структуры данных "лес".
2. Структуру графа сравнения хранить в массиве $T[i]$, где $i$ - это номер элемента в сортируемом массиве $A[i]$. $T[i]$ - это число вершин, входящих в поддерево $i$-го элемента. Чтобы перейти к следующему дереву или поддереву, достаточно увеличить $i$ на величину $T[i]$. Если происходит выход за пределы, то значит деревьев и поддеревьев больше нет.
3. Сравнивать корни двух крайних левых деревьев леса. Пусть $i$ - это номер корня самого левого дерева.
3.1. Если корень самого левого дерева больше следующего ($A[i]>A[i+T(i)]$), то достаточно изменить $T[i]$ этого корня: $T[i]:=T[i]+T[i+T[i]]$ - это операция сращивания двух левых деревьев. :D
3.2. Иначе придется обменивать самое левое дерево с корнем дерева правее. Довольно затратная операция, но все же. После обмена также изменить $T[i]$ по формуле выше (операция сращивания).

Поразмышлял и придумал следующую вторую часть алгоритма:
1. Сравнить корни двух крайних деревьев.
2. Если правый корень больше левого корня, то произвести обмен (swap) двух деревьев.
3. Срастить левое дерево с правым (при этом корень левого дерева должен взять в потомки корень правого дерева).
4. Если есть еще деревья, то перейти к п.1.
5. Отбросить корень единственного дерева из рассмотрения - мегадерево снова распадется на несколько деревьев.
6. Если есть еще вершины, то перейти к п. 1.
7. Конец сортировки.

В таком алгоритме имеются следующий инварианты:
1. Каждый раз сохраняется лес деревьев (об этом уже говорил).
2. Каждый раз деревья располагаются по неубыванию $T[i]$ корней, поэтому сравнение двух соседних деревьев получается достаточно эффективным по уменьшению энтропии.

Попробую написать алгоритм в Mathcad и потестировать его.

 
 
 [ Сообщений: 78 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group