Добрый день, уважаемая аудитория. Сегодня мы с вами рассмотрим одну достаточно популярную задачу – поиск всех простых путей в графе от одной вершины до другой. В планах - постановка задачи, ссылки на некоторые источники, где говорится про её решение, а также синтез алгоритма, так сказать, собственными силами. Но, для начала, введение.
Введение.
На написание этой статьи я решился по одной простой причине – ни одного вразумительного ответа, как это делается, google мне не выдал. Задача эта не из тривиальных, и «в лоб» не решилась. Пришлось думать. Давайте для начала поговорим о самой задаче.
Для начала расскажу вам, как она звучала на практике. Есть карта, на которой указаны города. Города между собой сообщаются автомобильными дорогами. Т.е. имеется карта автомобильных дорог. На карте указаны длины дорог в километрах и время в пути от одного города до другого. Нужно найти все пути от одного города до другого, которые не имели бы циклов. Пути, не имеющие циклов, называются простыми. Я полагаю, что такое описание задачи вызвало вопросы, поэтому чтобы сделать его понятным каждому, приложу рисунок.
Предположим, нужно найти все пути из города 7 в город 5. Тогда первый путь будет выглядеть так:
А второй – так:
Из описания задачи становится понятно, что здесь каким-то образом можно использовать абстрактные типы данных (АТД) для работы с графами. Конкретнее – нужно выполнять обход графа и искать все пути от одной вершины до другой, в которых бы вершины не повторялись, т.к. циклы недопустимы.
Т.к. таких путей может быть несколько, в дальнейшем было бы хорошо как-то сравнивать эти пути между собой – выбирать самый короткий, самый быстрый (по времени). Возможны и более экзотические требования, например, отыскать путь, в который бы не входила вершина номер 8. Т.е. мы приходим к тому, что нам нужна подробная информация о пути, в частности, нужно хранить очерёдность посещение вершин.
Поиск решения в google
Теперь обратимся за помощью к гуглу, т.к. велосипеды изобретать не очень приятно.
http://forum.sources.ru/index.php?showtopic=230281
– начали за здравие, поставили задачу, потом появляется тип с ником Swetlana и алгоритмом на паскале. Процитирую понравившуюся мне фразу:
Для этого нужно отыскать допустимое X(i+1). X(i+1) считается допустимым, если или < X(1), …, X(i+1) > уже является решением, или относительно < X(1), …, X(i+1) > нельзя сразу сказать, что его невозможно расширить до полного решения.
Что этой фразой хотели сказать, я не понял, как ни старался. Что есть X(i+1) допустимое, что значит «если или < X(1), …, X(i+1) >», для меня так и осталось тайной. Как обычно, рабочий бинарник не прилагался. Потом приплели в эту тему алгоритмы Флойда и Дейкстры, а закончили тем, что задача NP-полная, и надо делать полный перебор. Правда, что автор понимал под полным перебором, и как его реализовывать, осталось неясно.
http://forum.algolist.ru/algorithm-g...i-v-grafe.html
- аналогичный вопрос, аналогичный нулевой результат. Вначале типа просят нормально сформулировать задачу, потом дают ссылку, где это, якобы, поясняется. Заканчивается всё тем, что надо использовать BFS с локальной пометкой вершин, и это – очень просто. Настолько просто, что советчик не удосужился написать код, который бы это сделал. Ладно, пойдём по приведенной там ссылке, где должно быть решение.
http://www.delphikingdom.ru/asp/answ...IDAnswer=56734
– описали задачу вполне прилично. Некто Хищник предложил рекурсивную реализацию на паскале (да что ж такое-то!). Не то, чтоб эта реализация не работала, но было несколько недостатков. Во-первых, обход был рекурсивным. Во-вторых, при обходе мы получали номера вершин, а это было неприемлемо, т.к. терялась вся, связанная с вершинами информация, также невозможно было выполнять сдвиги с содержимым массива (1 shl W и т.д.). Последнее, что мне не понравилось – не было абсолютно никакого описания, как оно должно работать в теории. В общем, задумка была мне неясна. Остальные, как часто бывает, мололи что попало. Приплели туда задачу коммивояжёра, хотя в википедии чётко говорится:
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город
Уже хоть бы прочли что-то перед тем, как советовать. Ладно, идём дальше.
http://forum.vingrad.ru/topic-46842.html
- тут тёрли-тёрли, толку ноль. Опять перебор, обход в ширину, вот «то» надо переделать и т.д.
http://habrahabr.ru/qa/42302/
- здесь всё заканчивается тем, что это невозможно. Ну, блин, это вообще грусть.
Правда, ради справедливости стоит отметить, что есть и кое-что полезное.
http://www.youtube.com/watch?v=x8_5NaF-Sss
– видео про количество путей из одной вершины в другую. Ничего не поясняется, граф очень простой, ищется только количество путей, информации про путь нет никакой. Есть один плюс – наглядно.
http://www.technical-recipes.com/201...o-given-nodes/
- эту ссылку мне любезно предоставил reversecode, за что ему спасибо. Ссылка была многообещающая, есть теория, но когда дело дошло до основного цикла обхода графа, тут «смешались в кучу кони, люди», проект для построения бинаря доступен только за бабло. Не знаю, то ли я такой ленивый, и мне лень разбираться в коде, который нарушает все возможные принципы «чистоты кода», то ли я просто тупой, раз не могу с ходу там ничего понять. Но, как бы там ни было, ниже вашему вниманию будет представлен велосипед собственной сборки.
Общее описание
Сразу скажу, что алгоритм, который далее будет описан, был придуман мной не сразу. Я сделал n-ое количество бесполезных неработающих реализаций, пока не получил то, что хотел. Вполне может быть, что до меня это уже кто-то придумал, просто этот кто-то никому об этом ничего не сказал. Также возможно и то, что данную задачу можно решить гораздо проще, быстрее и элегантнее, но нормального кода в интернете мне найти не удалось. Теперь перейдём к делу.
Я решил отталкиваться от обхода графа в глубину. Причём в контексте задачи рассматривался именно неориентированный граф, т.к. решать эту задачу для ориентированного немного легче (мне так показалось). Также мне хотелось получить нерекурсивную реализацию.
Давайте вернёмся к рисунку № 1. На рисунке видно, что, например, вершина № 1 является смежной для вершин № 2, 4, 5 и 6. Если мы переходим из первой вершины к вершине № 2, то оказавшись во второй вершине, мы не должны возвращаться в первую, иначе попадём в бесконечный цикл. Т.е. из вершины 1 пошли в вершину 2, из вершины 2 – опять в вершину 1, и т.д. Это – первая проблема.
Вторая проблема кроется в следующем. Допустим, из вершины 1 мы идём в вершину 5, потом в 8, потом в 4, потом в 1, но в один мы уже были, потому идёт назад. Но вершина под номером 4 остаётся помеченной как пройденная, и следующий обход из вершины 1 уже её не посетит.
Это всё порождает перед нами следующую задачу – задачу правильной отметки пройденных вершин. Иными словами, мы должны помечать пройденные вершины каким-то определённым образом. И снимать пометки в определённых случаях.
Я решил это следующим образом - ввёл три вспомогательных класса:
- стек пути;
- хранитель состояний обхода;
- хранитель зависимостей типа «дед-внук».
Каждый класс решает определённые задачи, давайте ознакомимся с ними более подробно.
Объект "стек пути" хранит информацию о текущем маршруте. Для его реализации используется список, но моделируется работа стека. Объект реализует следующие операции:
- добавить вершину в конец списка;
- удалить вершину из конца списка;
- прочитать вершину с конца списка без удаления из списка;
- вернуть маршрут;
- получить порядковый номер элемента в списке, если элемент отсутствует в списке, вернуть -1;
- проверить, пуст ли стек;
- вернуть ссылку на элемент (город) по указанному порядковому номеру.
Работа с порядковыми номерами нужна для получения зависимостей "дед-внук".
Объект «хранитель состояний обхода» представлен в виде Dictionary, в котором ключом является ссылка на город, а значением величина типа bool, которое равно истинне, если город посещался. При инициализации этого объекта он получает все города для создания ключей, значениям присваивается ложь. Реализует такие операции:
- проверить, посещалась ли указанная вершина;
- отмечает вершину как посещённую;
- снимает отметку о посещении.
Объект, отвечающий за реализацию зависимостей дедов от внуков, представлен в виде словаря (Dictionary), в котором ключом выступает ссылка на город, а значением является множество внуков. При инициализации такого объекта для каждого города создаётся пара из ссылки и пустого множества. Множество редактируется по мере добавления
и удаления зависимостей. Напомню, что во множестве не могут присутствовать одинаковые значения. Такой объект должен реализовывать такие операции:
- получить всех внуков для указанного города;
- добавить для указанного города внука;
- для указанного города пометить всех внуков как непосещённые.
Весь алгоритм можно условно разделить на инициализацию, когда создаются экземпляры трёх вышеупомянутых классов, и в стек помещается начало пути, и на основной цикл.
Основной цикл выглядит так:
PHP Code:
Пока стек не пуcтой
{
1. Прочитать содержимое вершины стека, не извлекая её.
2. Обновить зависимости "дед-внук".
3. Проверить, не достигли ли мы конца пути.
2.1. Если достигли:
3.1.1. Вывести маршрут по стеку пути.
3.1.2. Отметить конец пути как посещённый.
3.1.3. Удалить вершину из верхушки стека.
3.1.4. Извлечь следующую вершину из стека.
4. Пометить внуков как непосещённые.
5. Перечислить всех соседей.
5.1. Из полученного списка удалить все вершины, которые есть в стеке пути.
5.2. Из списка удалить все пройденные вершины.
6. Если список непуст, то из оставшихся в списке вершин выбрать первую и поместить в стек.
}
Теперь рассмотрим код каждого класса, и основной цикл более подробно. Данную реализацию я написал на языке C#, но, сами понимаете, алгоритм везде одинаков.
PHP Code:
class Visitor
{
private Dictionary<Town, bool> VisitedInformation = new Dictionary<Town,bool>();
public Visitor(IEnumerable<Town> Towns)
{
foreach (Town town in Towns)
VisitedInformation[town] = false;
}
public bool IsVisited(Town town) { return VisitedInformation[town]; }
public void SetVisited(Town town) { VisitedInformation[town] = true; }
public void SetUnvisited(Town town) { VisitedInformation[town] = false; }
}
Это - код класса, отвечающего за отметку пройденных вершин.
PHP Code:
class StackWay
{
private List<Town> CurrentWayInfo = new List<Town>();
public void push(Town town) { CurrentWayInfo.Add(town); }
public Town pop()
{
Town LastTown = CurrentWayInfo[CurrentWayInfo.Count - 1];
CurrentWayInfo.RemoveAt(CurrentWayInfo.Count - 1);
return LastTown;
}
public Town peek() { return CurrentWayInfo.Last(); }
public List<Town> GetWay() { return CurrentWayInfo; }
public int GetNumberByElement(Town town) { return CurrentWayInfo.LastIndexOf(town); }
public Town GetElementByNumber(int Number) { return CurrentWayInfo[Number]; }
public bool IsEmpty() { return CurrentWayInfo.Count == 0; }
}
А это - код класса стека пути.
PHP Code:
class RefKeeper
{
private Dictionary<Town, HashSet<Town>> Keeper = new Dictionary<Town, HashSet<Town>>();
public RefKeeper(IEnumerable<Town> Towns)
{
foreach (Town town in Towns)
Keeper[town] = new HashSet<Town>();
}
public List<Town> GetAllGrandchildren(Town town) { return Keeper[town].ToList<Town>(); }
public void AddDependence(Town Root, Town grandChild) { Keeper[Root].Add(grandChild); }
public void SetGrandChildUnvisitedForTown(Town town, Visitor visit)
{
List<Town> grandChildren = GetAllGrandchildren(town);
foreach (Town t in grandChildren)
visit.SetUnvisited(t);
}
}
Последний здесь - это класс зависимостей "дед-внук".
Я надеюсь, что к этому моменту вы поняли, в чём основная идея - она заключается в том, что на каждой итерации мы работаем с какой-то вершиной. Вершина, которая лежит в стеке через одну от текущей - её дед, но у самой текущей вершины тоже есть внуки. Так вот на этапе обработки текущей вершины её внуки помечаются как непосещённые.
А вот и реализация метода поиска всех маршрутов:
PHP Code:
public List<Path> FindWay(Town BeginWith, Town ArriveTo)
{
List<Path> result = new List<Path>();
Visitor visit = new Visitor(Towns);
StackWay WayHistory = new StackWay();
RefKeeper ChildDependecy = new RefKeeper(Towns);
WayHistory.push(BeginWith);
while (WayHistory.IsEmpty() != true)
{
Town Current = WayHistory.peek();
SetGrandchildDependency(WayHistory, ChildDependecy, Current);
if (Current == ArriveTo)
{
result.Add(new Path(new List<Town> (WayHistory.GetWay())));
visit.SetVisited(ArriveTo);
WayHistory.pop();
}
else
{
ChildDependecy.SetGrandChildUnvisitedForTown(Current, visit);
List<Town> NeighborsNotVisited = FilterNeighbors(WayHistory, visit, Current);
if (NeighborsNotVisited.Count > 0)
WayHistory.push(NeighborsNotVisited[0]);
else
WayHistory.pop();
visit.SetVisited(Current);
}
}
return result;
}
Вам, конечно же, хотелось бы получить весь проект, чтоб узнать, как там устроено всё до мелочей. Что ж - ваше право. Скачать его можно
Здесь
Заключение
Надеюсь, эта реализация кому-то поможет. В частности, на этом теперь не смогут наживаться такие люди, как
https://www.free-lance.ru/users/4VIY...p?prjid=839931. Всем всех благ.
Ах да, пользуясь случаем, хотелось бы передать привет замечательной девушке по имени Кристюлька (я уже вижу, как на форуме все тянут лыбы), и сказать, что она - лучше всех.
Алгоритм поиска простых путей в графе
Reply With Quote
Thanks
