Попробуем написать функцию, которая поиском в глубину найдет все циклы, начиная от заданной вершины
IEnumerable<Stack<int>> FindAllCycles(int[,] edges, int currentV, HashSet<int> alreadyVisited, Stack<int> currentPath)
{
if (alreadyVisited.Contains(currentV))
{
var ret = new Stack<int>();
ret.Push(currentV);
foreach (var v in currentPath)
{
ret.Push(v);
// Крутим путь только до начала цикла
if (v == currentV) break;
}
yield return ret;
}
else
{
alreadyVisited.Add(currentV);
currentPath.Push(currentV);
for (int i = 0; i < edges.GetLength(1); i++)
if (currentV != i && edges[currentV, i] == 1)
foreach (var cycle in FindAllCycles(edges, i, alreadyVisited, currentPath)) yield return cycle;
alreadyVisited.Remove(currentV);
currentPath.Pop();
}
}
Далее, надо будет запустить эту функцию для каждой вершины и, по сути, получить все циклы, из полученных циклов вернуть цикл максимальной длины.
var vertices = new Dictionary<int, char>() { { 0, 'А' }, { 1, 'Б' }, { 2, 'В' }, { 3, 'Г' }, { 4, 'Д' } };
var edges = new int[,] {
{0, 1, 1, 0, 0},
{0, 0, 1, 0, 1},
{0, 0, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
};
var allCycles = vertices.Keys.SelectMany(x => FindAllCycles(edges, x, new HashSet<int>(), new Stack<int>()));
Stack<int> maxCycle = null;
foreach(var cycle in allCycles){
if (maxCycle == null || maxCycle.Count < cycle.Count)
maxCycle = cycle;
}
if (maxCycle == null)
Console.WriteLine("No cycles!");
else
Console.WriteLine(String.Join('-', maxCycle.Select(m => vertices[m])));
Вывод в консоль
А-Б-В-Д-Г-А
Сразу скажу, алгоритм далек от идеала и тут есть что улучшать, но он вроде работает на ваших данных. На большом графе с кучей ребер и кучей циклов со скоростью будет не важно.
Максимальный цикл в графе
- Подписаться на тему
- Сообщить другу
- Скачать/распечатать тему
|
|
|
|
Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе. |
|
Морской Ёж |
|
|
Senior Member
Рейтинг (т): 17 |
Какая сложность? Можно back tracking’ом. Больше пока ничего на ум не приходит. |
|
kl |
|
|
Совершенно очевидно, что это NP-complete задача, ибо если бы за полиномиальное время можно было бы найти максимальный простой цикл, то мы бы автоматически решили бы и TSP (задачу коммивояжера). Просто путем проверки, гамильтонов ли цикл. |
 shadeofgray |
|
|
Moderator
Рейтинг (т): 30 |
Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто «немного длинные» |
|
kl |
|
|
Цитата shadeofgray @ 25.04.06, 12:29 Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто «немного длинные»
Ага, именно так, спасибо |
Я извиняюсь, у меня иногда возникают сложности с объяснением на русском того, что я на русском никогда не изучал… |
vek21 |
|
|
Цитата kl @ 25.04.06, 11:59 Просто путем проверки, гамильтонов ли цикл. А при чём здесь гамильтонов цикл? Гамильтонов цикл — это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный. |
|
mo3r |
|
|
Цитата vek21 @ 26.04.06, 06:07 А при чём здесь гамильтонов цикл? Гамильтонов цикл — это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.
Скажем, так: Цитата vek21 @ 24.04.06, 20:20 Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе. Если граф эйлеров, то максимальным циклом, не проходящим по ребру дважды в одном направлении, будет эйлеров цикл. |
|
Морской Ёж |
|
|
Senior Member
Рейтинг (т): 17 |
Цитата mo3r @ 26.04.06, 06:55 Гамильтонов цикл — это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный. Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка — гамильтонов цикл всегда минимален для данного графа. |
|
kl |
|
|
Цитата Arsuit @ 27.04.06, 13:08 Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка — гамильтонов цикл всегда минимален для данного графа.
Гамильтонов цикл здесь очень даже причем. mo3r достаточно ясно показал, то о чем я говорил в первом посте, а именно, как задача нахождения гамильтонова цикла сводится к исходной задаче. Сводится по Куку. Отсюда автоматически следует, что либо вам удается показать, что P = NP, либо вы не сможете решить свою задачу точно и за приемлемое время. Вот и все. |
|
kl |
|
|
Цитата Arsuit @ 27.04.06, 13:08 гамильтонов цикл всегда минимален для данного графа. Это почему? |
|
Морской Ёж |
|
|
Senior Member
Рейтинг (т): 17 |
по опредилению вроде. |
|
kl |
|
|
Цитата Arsuit @ 06.05.06, 12:31 по опредилению вроде. Прочитай определение еще разок. |
|
esperanto |
|
|
математик
Рейтинг (т): 50 |
Цитата kl @ 25.04.06, 11:59 Совершенно очевидно, что это NP-complete задача, Судя по вашим словам, совершенно очевидно, что задача NP=HARD. Добавлено 07.05.06, 03:36 |
|
kl |
|
|
Да, я согласен, что термин NP-complete тут надо употреблять аккуратнее, потому что он строго определен только для decision problems (а TSP в классической формулировке таковой не является). Тем не менее ее можно перевести в класс decision problems. Но мне не хотелось вдаваться в эти детали, я просто имел в виду, что задача поиска максимального цикла — как минимум так же сложна как и TSP. И наоборот. |
|
KAV_Invariant |
|
|
Вот мне надо как-то было найти минимальный цикл в графе. Была у меня идея пробежаться по всем вершинам и для каждой вершины найти кратчайший путь из нее в нее же. Только вот я не знаю, как это сделать |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
- Предыдущая тема
- Алгоритмы
- Следующая тема
[ Script execution time: 0,0400 ] [ 15 queries used ] [ Generated: 25.05.23, 16:01 GMT ]
- В этой теме 1 ответ, 2 участника, последнее обновление 1 год, 5 месяцев назад сделано .
-
Сообщения
-
-
Дан неориентированный граф. Написать программу, которая находит в графе максимальный цикл и выдает его в виде списка вершин. Если в графе нет циклов, функция должна сообщать об этом. Примерный граф прикреплю ниже.
-
Вот тут можно взять функцию, рассчитывающую все циклы в графе. При этом цикл возвращается в виде списка узлов. Все что вам остается сделать — найти список с максимальной длиной. Сделать это можно так:
longest_list(List, Longest):- member(Longest, List), length(Longest, MaxLen), + ( member(Other, List), length(Other, OtherLen), OtherLen > MaxLen ).Тут мы записали правило — список является самым длинным если не существует другого списка, длина которого больше.
Остается лишь вызвать готовые функции чтобы получить решение вашей задачи.
-
-
Автор
Сообщения
- Для ответа в этой теме необходимо авторизоваться.
$begingroup$
I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can calculate the number of minimum times it will search through the array using both the binary search and sequential search. Here is what I have done so far.
Maximum Number of Times with Binary Search: Maximum: $log_2(1,048,576)= 20$ times
Maximum Number of Times with Sequential Search: Maximum: $1,048,576 + 1 ÷ 2= 524,289$ times
But I am confused about how I can obtained a solution with Minimum number for each algorithm. Any suggestions?
fade2black
9,7071 gold badge23 silver badges35 bronze badges
asked Sep 8, 2017 at 22:23
$endgroup$
0
$begingroup$
I assume your input is random and your array of size $N$, $A[1..N]$.
In case of binary search if the number you are searching for is located at $(1+N)/2$, i.e. right in the middle of the input array then you will find it after the first if-statement.
Similarly in case of sequential search, if number your are searching for is the first element of the array then you stop after the first if-statement.
In both cases you do only one comparison.
answered Sep 8, 2017 at 22:32
fade2blackfade2black
9,7071 gold badge23 silver badges35 bronze badges
$endgroup$
0
Форум программистов Vingrad
|
Поиск: |
  
|
 поиск цикла максимальной длины |
Опции темы |
| magicfa |
|
||
|
Новичок Профиль Репутация: нет
|
Никто не подскажет как в неориентированном графе можно найти цикл максимальной длинны, включающий заданную вершину? |
||
|
|||
Загрузка …
| Silent |
|
||
|
Опытный Профиль Репутация: 1
|
Ну дык… поиск в глубину из этой вершины… |
||
|
|||
| SoWa |
|
||
Харекришна Профиль Репутация: 6
|
Действительно, это стандартный алгоритм на графах, описаный в любой книге по данной тематике. Вот, если не ошибаюсь, примеры: ——————— Всем добра |
||
|
|||
| maxdiver |
|
||
|
Опытный Профиль
Репутация: 16
|
SoWa Silent Не говоря уже о том, что на графах с существующим гамильтоновым циклом, задача нахождения длиннейшего цикла эквивалентна нахождению этого гамильтонова цикла, и вы предлагаете его дфсом искать |
||
|
|||
| Earnest |
|
||
Эксперт Профиль
Репутация: 7
|
maxdiver, насколько я помню, задача о поиски максимального цикла, в отличие от поиска минимального, не является тривиальной задачей, а является как раз np-полной. Говоря по-русски, пахнет полным перебором. Не всегда же есть гамильтонов цикл. ——————— … |
||
|
|||
| maxdiver |
|
||
|
Опытный Профиль
Репутация: 16
|
Earnest, ну так и я о том же Добавлено @ 17:37
Я подумал, что этой фразы достаточно, чтобы ни у кого не осталось сомнений в том, что задача ТС является NP-полной. (хотя сначала я сам чуть не поверил в алгоритм с дфсом Это сообщение отредактировал(а) maxdiver — 19.12.2008, 17:38 |
||
|
|||
| Earnest |
|
||
|
Эксперт Профиль
Репутация: 7
|
Ага, так бывает, когда заявляют с таким апломбом, а ты помнишь смутно… ——————— … |
||
|
|||
)
|
|
| Правила форума «Алгоритмы» | |
 |
Форум «Алгоритмы» предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) |
| 0 Пользователей: |
| « Предыдущая тема | Алгоритмы | Следующая тема » |