перебор всевозможных топологических сортировок
не понял вопрос
что такое сортировка графа?
что такое сортировка графа?
А что понимается под эффективностью алгоритма? Вряд ли полиномиальная сложность от числа вершин, т.к. например, у графа, состоящего из 127 вершин и представляющего собой двоичное дерево, будет 2^64 возможных топологических сортировок.
Произвольное ли у тебя дерево, или оно является "удачно связанным", так что количество топологический сортировок невелико?
Произвольное ли у тебя дерево, или оно является "удачно связанным", так что количество топологический сортировок невелико?
В чем проблема модифицировать стандартный алгоритм для данной задачи?
вот, например: http://algolist.manual.ru/sort/top_sort.php
Ну не знаю, какая там будет сложность.
Интуитивно -- хочется, чтоб работало побыстрее.
Пока самое разумное, что пришло мне в голову -- взять алгоритм топологической сортировки, потом в тех местах, где есть свобода выбора (т.е. алгоритм действует не исходя из задачи, а исходя из мысли: всё равно как сделать, лишь бы как-нибудь, ну например делает обход ребёр слева направо, хотя можно было справа налево, из центра и т.д. начать варьировать. Потом результаты записать в массив. И из массива выкинуть повторяющиеся (а такие будут).
Интуитивно -- хочется, чтоб работало побыстрее.
Пока самое разумное, что пришло мне в голову -- взять алгоритм топологической сортировки, потом в тех местах, где есть свобода выбора (т.е. алгоритм действует не исходя из задачи, а исходя из мысли: всё равно как сделать, лишь бы как-нибудь, ну например делает обход ребёр слева направо, хотя можно было справа налево, из центра и т.д. начать варьировать. Потом результаты записать в массив. И из массива выкинуть повторяющиеся (а такие будут).
что ты имеешь ввиду?
если то, что я написал выше, то меня смыщуает, что некоторые результаты нужно будет потом выкидывать: мне кажется это говорит о том, что я делаю что-то не оптимально.
если то, что я написал выше, то меня смыщуает, что некоторые результаты нужно будет потом выкидывать: мне кажется это говорит о том, что я делаю что-то не оптимально.
> выкинуть повторяющиеся (а такие будут)
С чего бы это?
С чего бы это?
Если сделать корректное варьирование, то повторяющихся не будет.
Вводишь некий лексикографический порядок сортировок.
Далее варьирование должно каждый раз выдавать сортировку, следующую с точки зрения лексикографического порядка.
Далее варьирование должно каждый раз выдавать сортировку, следующую с точки зрения лексикографического порядка.
, ну вы понимаете, что это зависит от алгоритма?
помню, когда мне задали эту задачку: сделать топ. сортировку, я придумал два алгоритма.
сейчас один из них вспомнил, попробовал там поварьировать и у меня получались одинаковые сортировки.
может если второй взять, то там не будет.
в любом случае, я хочу сказать, что если в моём алгоритме повторяющиеся есть, то не очевидно, что в произвольном алгоритме их не будет. (
)
помню, когда мне задали эту задачку: сделать топ. сортировку, я придумал два алгоритма.
сейчас один из них вспомнил, попробовал там поварьировать и у меня получались одинаковые сортировки.
может если второй взять, то там не будет.
в любом случае, я хочу сказать, что если в моём алгоритме повторяющиеся есть, то не очевидно, что в произвольном алгоритме их не будет. (
)А ты можешь хоть примерно оценить, сколько там этих сортировок в твоем случае? Если тысяча, то тебе не нужен _эффективный_ алгоритм, если миллиард, то тебе не поможет _эффективный_ алгоритм. А поверь мне, между тысячей и миллиардом очень мало чисел!
> Если тысяча, то тебе не нужен _эффективный_ алгоритм
Спорное утверждение.
На графе, неэффективный алгоритм может быть и O(n^2 и O(n^3 и O(2^n и O(n! и O(n^n причем n - может быть как кол-во вершин, так и кол-во связей.
Для тысячи, алгоритмы с такой оценкой на современный компьютер плохо "влазят".
Спорное утверждение.
На графе, неэффективный алгоритм может быть и O(n^2 и O(n^3 и O(2^n и O(n! и O(n^n причем n - может быть как кол-во вершин, так и кол-во связей.
Для тысячи, алгоритмы с такой оценкой на современный компьютер плохо "влазят".
Ну неужели нет уже готового? Ведь задача-то не такая уж редкая, как мне кажется.
В общем, конкурс открыт по крайней мере до конца недели. А на следующий, уже скорее всего буду кодить.
В общем, конкурс открыт по крайней мере до конца недели. А на следующий, уже скорее всего буду кодить.
что такое лексикографический порядок - ты уже заботал?
и как он применяется в переборных задачах?
уже подумал, как можно лексикографический порядок положить на твою задачу?
и как он применяется в переборных задачах?
уже подумал, как можно лексикографический порядок положить на твою задачу?
не знаю, что ты имеешь ввиду под лексиографическим порядком, потому что в том виде, в котором я его понимаю, ботать там просто нечего.
а как он применяется? так же, как к натуральному числу в десятичной записи прибавляется единичка или как?
насколько я понимаю, твой совет ничего нового не даёт... это как в анекдоте:
ДОКАЗАЛ ТЕОРЕМУ ФЕРМА ТЧК НАДО ПЕРЕНЕСТИ ИКС В ЭННОЙ В ПРАВУЮ ЧАСТЬ ТЧК ПОДРОБНОСТИ ПИСЬМОМ (
)
а как он применяется? так же, как к натуральному числу в десятичной записи прибавляется единичка или как?
насколько я понимаю, твой совет ничего нового не даёт... это как в анекдоте:
ДОКАЗАЛ ТЕОРЕМУ ФЕРМА ТЧК НАДО ПЕРЕНЕСТИ ИКС В ЭННОЙ В ПРАВУЮ ЧАСТЬ ТЧК ПОДРОБНОСТИ ПИСЬМОМ (
)
#define MAX 1000
int count;
int childcount[MAX];
int childs[MAX][MAX];
int parents[MAX];
int gen[MAX];
int queue[MAX];
int queec;
int outed;
static void getParentsCount {
int i, ii, iii;
for (i = 0; i < count; i++)
parents[i] = 0;
for (i = 0; i < count; i++)
for (ii = 0; ii < childcount[i]; ii++)
parents[childs[i][ii]]++;
}
static void generateFirstQueue {
int i, ii, iii;
queec = 0;
for (i = 0; i < count; i++)
if (0 == parents[i])
queue[queec++] = i;
}
static void outData {
int i;
for (i = 0; i < count; i++)
printf("%d ", gen[i]);
printf("\n");
}
static void deledges(int vert) {
int i, cv;
for (i = 0; i < childcount[vert]; i++)
if (0 == (--parents[cv = childs[vert][i]]
queue[queec++] = cv;
}
static void addedges(int vert) {
int i, cv;
for (i = 0; i < childcount[vert]; i++)
++parents[childs[vert][i]];
}
static void Gorec {
int i, curvert, oldqueue;
if (0 == queec) {
outData;
return;
}
for (i = 0; i < queec; i++) {
gen[outed++] = curvert = queue[i];
queue[i] = queue[--queec];
oldqueue = queec;
deledges(curvert);
Gorec;
addedges(curvert);
queec = oldqueue;
queue[queec++] = queue[i];
queue[i] = curvert;
outed --;
}
}
int main(int argc, char **argv) {
int i, ii, iii;
/*Read input*/
scanf("%d", &count);
for (i = 0; i < count; i++) {
scanf("%d", i + childcount);
for (ii = 0; ii < i[childcount]; ii++)
scanf("%d", &(childs[i][ii];
}
getParentsCount;
generateFirstQueue(1,2,3);
outed = 0;
Gorec;
}
Вот пример кода. Он не может генерить одинаковые топологические сортировки графа. Доказательство: рассмотрим префикс сортировки, содержащийся в массиве gen. Покажем, что все вызовы функции Gorec имеют различные префиксы. Допустим, какие-то два вызова имеют одинаковый префикс, рассмотрим такой префикс наименьшей длины (длина префикса совпадает с глубиной вызовов).
1) Префикс нулевой длины. Но такое не бывает, Gorec вызывается один раз на верхнем уровне.
2) Префикс ненулевой длины P. Рассмотрим префикс P-1, имеющий длину на 1 меньше. Т.к. P имеет наименьшую длину, при которой Gorec вызывается более одного раза с одинаковым префиксом, то Gorec вызывается ровно один раз с префиксом P-1. Таким образом, из какого-то вызова Gorec мы два раза поставили на следующую позицию префикса одну и ту же вершину. Но такого не может быть, т.к. в очереди queue вершины содержатся не более одного раза (по алгоритму добавления вершин, если нужно, могу отписать подробнее). Противоречие. Таким образом, мы генерируем перестановки всего по одному разу.
Сложность алгоритма не более Ov+e)*c где v -количество вершин, e - количество ребер, c - количество различных сортировок
Лексикографическая сортировка - может и хорошо, но она требует время.
ну ты маньяк 
а словами можно?
а словами можно?
Можно и словами попробвать 
Рассмотрим сначала построение одного из вариантов топологической сортировки. Будем строить отсортированный массив записывая по одной вершине. Очевидно, что на очередном шаге записана может быть одна из вершин, у которой нет "родительских" вершин среди еще не выписанных. Родительская вершина - вершина, из которой ведет ребро в рассматриваемую. Заметим, что если вершина была кандидатом на запись на каком-то шаге, то она будет и кандидатом на всех последующих шагах до тех пор, пока мы ее таки не запишем. При записи же вершины могут появиться и новые кандидаты из числа оставшихся вершин, у которых не стало входящих ребер.
Следовательно в простейшем случае алгоритм такой:
1)Для каждой вершины считаем количество входящих ребер.
2)В изначальный набор кандидатов включаем все вершины, в которых нет входящих ребер
3)Пока в наборе кандидатов есть вершины выполняем следующие шаги
4)Выбираем произвольную вершину из кандидатов, записываем ее в ответ
5)Для всех вершин, в которые ведут ребра из только что записанной, уменьшаем количество входящих ребер (на число ребер между этими вершинами).
6) Если на шаге 5 образуются вершины, у которых 0 входящих ребер, добавляем их в очередь кандидатов.
Данный алгоритм будет выдавать некоторые варианты сортировки в зависимости от выбора на шаге 3. При этом любая последовательность, построенная по данному алгоритму, будет являться топологической сортировкой, а также любая сортировка может быть получена с помощью некоторой последовательности выборов на 3-м шаге (т.к. если вершины нет среди кандидатов на каком-то шаге, то значит есть ведущее в нее ребро из вершины, которая еще не выписана, и следовательно эту вершину нельзя записать в ответ прямо сейчас). Осталось правильно организовать перебор, чтобы построить все возможные перестановки без повторений.
Построение всех сортировок:
На 3-м шаге будем производить следующую процедуру.
1)Определяем некторый порядок перебора среди кандидатов.
2)Запоминаем текущее состояние решения (уже выписанную часть, кандидатов, количества входящих ребер для всех вершин)
3)Согласно порядка последовательно выбираем кандидата, пишем в ответ, уменьшаем количество ребер, обновляем множество кандидатов (как и ранее затем рекурсивно переходим к шагу 1
4)Восстанавливаем ранее запомненное состояние решения, после чего переходим к шагу 2) (т.е. опять запоминаем состояние, выбираем следующего кандидата и т.д.).
В приведенной выше программе восстановление состояния - произведение операций, обратных вносимому изменению.
Заметим, что среди кандидатов каждая вершина находится не более одного раза (т.к. вершины в это множество заносятся при "удалении" последнего ребра и, следовательно, не может быть занесена дважды). Таким образом, в данном узле дерева рекурсии мы выбираем на каждом шаге различные варианты продолжения. Т.е. ни один из результатов, полученных при выборе одного кандидата, не может совпасть ни с одним из вариантов, полученных при выборе другого кандидата на том же шаге. Ну и проводя такое рассуждение начиная от корневой вершины и доходя до конкретной листовой вершины в дереве рекурсии мы получаем, что все построенные результаты различны. При этом были построены все возможные топологические сортировки, т.к. были рассмотрены все возможные варианты выбора вершин на третьем шаге первого алгоритма, а каждый вариант сортировки может быть получен путем некоторого выбора вершин на его третьем шаге.
Рассмотрим сначала построение одного из вариантов топологической сортировки. Будем строить отсортированный массив записывая по одной вершине. Очевидно, что на очередном шаге записана может быть одна из вершин, у которой нет "родительских" вершин среди еще не выписанных. Родительская вершина - вершина, из которой ведет ребро в рассматриваемую. Заметим, что если вершина была кандидатом на запись на каком-то шаге, то она будет и кандидатом на всех последующих шагах до тех пор, пока мы ее таки не запишем. При записи же вершины могут появиться и новые кандидаты из числа оставшихся вершин, у которых не стало входящих ребер.
Следовательно в простейшем случае алгоритм такой:
1)Для каждой вершины считаем количество входящих ребер.
2)В изначальный набор кандидатов включаем все вершины, в которых нет входящих ребер
3)Пока в наборе кандидатов есть вершины выполняем следующие шаги
4)Выбираем произвольную вершину из кандидатов, записываем ее в ответ
5)Для всех вершин, в которые ведут ребра из только что записанной, уменьшаем количество входящих ребер (на число ребер между этими вершинами).
6) Если на шаге 5 образуются вершины, у которых 0 входящих ребер, добавляем их в очередь кандидатов.
Данный алгоритм будет выдавать некоторые варианты сортировки в зависимости от выбора на шаге 3. При этом любая последовательность, построенная по данному алгоритму, будет являться топологической сортировкой, а также любая сортировка может быть получена с помощью некоторой последовательности выборов на 3-м шаге (т.к. если вершины нет среди кандидатов на каком-то шаге, то значит есть ведущее в нее ребро из вершины, которая еще не выписана, и следовательно эту вершину нельзя записать в ответ прямо сейчас). Осталось правильно организовать перебор, чтобы построить все возможные перестановки без повторений.
Построение всех сортировок:
На 3-м шаге будем производить следующую процедуру.
1)Определяем некторый порядок перебора среди кандидатов.
2)Запоминаем текущее состояние решения (уже выписанную часть, кандидатов, количества входящих ребер для всех вершин)
3)Согласно порядка последовательно выбираем кандидата, пишем в ответ, уменьшаем количество ребер, обновляем множество кандидатов (как и ранее затем рекурсивно переходим к шагу 1
4)Восстанавливаем ранее запомненное состояние решения, после чего переходим к шагу 2) (т.е. опять запоминаем состояние, выбираем следующего кандидата и т.д.).
В приведенной выше программе восстановление состояния - произведение операций, обратных вносимому изменению.
Заметим, что среди кандидатов каждая вершина находится не более одного раза (т.к. вершины в это множество заносятся при "удалении" последнего ребра и, следовательно, не может быть занесена дважды). Таким образом, в данном узле дерева рекурсии мы выбираем на каждом шаге различные варианты продолжения. Т.е. ни один из результатов, полученных при выборе одного кандидата, не может совпасть ни с одним из вариантов, полученных при выборе другого кандидата на том же шаге. Ну и проводя такое рассуждение начиная от корневой вершины и доходя до конкретной листовой вершины в дереве рекурсии мы получаем, что все построенные результаты различны. При этом были построены все возможные топологические сортировки, т.к. были рассмотрены все возможные варианты выбора вершин на третьем шаге первого алгоритма, а каждый вариант сортировки может быть получен путем некоторого выбора вершин на его третьем шаге.
да на словах он еще больший маньяк
я тащусь
я тащусь
РЕСПЕКТ
ну чего, Вовка, покодил?
что получилось?
что получилось?
не, ещё не покодил... =)
другие дела пока: работа, форум....
ну в общем, должно получиться примерно то, что я и думал.
просто изначально надо было брать нормальный алгоритм сортировки, а я взял дурацкий.
другие дела пока: работа, форум....
ну в общем, должно получиться примерно то, что я и думал.
просто изначально надо было брать нормальный алгоритм сортировки, а я взял дурацкий.
Оставить комментарий
psihodog
Существует ли эффективный алгоритм перебора всевозможных топологических сортировок ацикличекого ориентированного графа?Если да, то где посмотреть?