Рандомизированный алгоритм для нахождения гамильтонова пути в ориентированном графе
Из этой статьи Wikipedia:
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
Рандомизированный алгоритм для гамильтонова пути, который быстр на большинстве графиков, следующий: Запустите со случайной вершины и продолжите, если существует сосед, которого не посещают. Если там больше не не посещаются соседи, и сформированный путь не является гамильтоновым, выберите соседа однородно наугад и поверните использование, которые граничат как центр. (Таким образом, добавьте край к тому соседу и удалите один из существующих краев от того соседа, чтобы не сформировать цикл.) Затем продолжите алгоритм в новом конце пути.
Я не вполне понимаю, как этот процесс поворота, как предполагается, работает. Кто-то может объяснить этот алгоритм более подробно? Возможно, мы можем в конечном счете обновить статью Wiki с более четким описанием.
Редактирование 1: Я думаю, что понимаю алгоритм теперь, но на него кажется, что только работает на неориентированных графов. Кто-либо может подтвердить это?
Вот то, почему я думаю, что это только работает на неориентированных графов:
сопроводительный текст http://www.michaelfogleman.com/static/images/graph.png
Притворитесь, что вершины пронумерованы как так:
123
456
789
Скажем, мой путь до сих пор: 9, 5, 4, 7, 8. 8's соседей все посетили. Скажем, я выбираю 5 для удаления края из. Если я удаляю (9, 5), я только заканчиваю тем, что создал цикл: 5, 4, 7, 8, 5, таким образом, кажется, что я должен удалить (5, 4) и создать (8, 5). Если граф является неориентированным, это прекрасно, и теперь мой путь равняется 9, 5, 8, 7, 4. Но если Вы воображаете те края направленными, это - не обязательно допустимый путь, так как (8, 5) край, но (5, 8) не мог бы быть.
Редактирование 2: Я предполагаю для ориентированного графа, я мог создать (8, 5) соединение и затем позволить новому пути быть справедливым 4, 7, 8, 5, но это кажется счетчиком, продуктивным, так как я должен обрубить все, что ранее привело к вершине 5.
3 ответа
В основном, как только ваш случайный выбор узлов построит график таким образом, что последняя вершина A не имеет несравненных соседних вершин, вам необходимо сделать вершину доступной для продолжения.
Для этого: выберите соседнюю вершину случайным образом, удалите один из своих существующих ребер (в гамильтоновом пути могут быть только два края из любой одной вершины), затем нарисуйте новый край из вашей текущей вершины до настоящего времени. случайным образом выбран один. Затем вы прослеживаете от случайно выбранной вершины до конца графа (первая вершина, которая имеет только один край, оставляющий его) и продолжить алгоритм.
Во всех видах ужасающего PSuedo-Code:
Graph graph;
Vertex current;
Path path;
while(!IsHamiltonian(path))
{
if(HasUnvisitedNeighbor(current, path))
{
Vertex next = SelectRandomUnvisited(current, path);
DrawEdgeTo(next, current, path);
current= next;
}
else
{
Vertex next = SelectRandomNeighbor(current, path);
RemoveRandomEdgeFrom(next, path);
DrawEdgeTo(next, current, path);
path = FindEnd(next, current, path); //Finds the end of the path, starting from next, without passing through current
}
}
Вы понимаете, что такое край? Если вершины v1, v2, .. vn, то край представляет собой пару (v1, v2) - представьте себе рисунок линии между v1 и v2, и это край.
Итак, в основном вы делаете базовый алгоритм холма холма (продолжайте добавлять края и посещать неслышные узлы), подверженные ограничения, которое вы не посещаете узел более одного раза.
И если вы обнаружите, что вы не можете продолжать больше (не можете достичь большего количества невизимых узлов из текущей вершины), то вы выбираете случайную вершину, которая подключена (существует край между этой вершиной и одним Из вершин, которые вы уже посетили) и добавляют в край между этой вершиной и посещаемыми узлами, которые еще не на пути.
Это может (и, возможно, должно, оставить это до математиков) создать цикл. Вы можете удалить петлю, удалив другой край от краев на пути.
В основном это алгорит холма, с небольшим количеством рандомизированного возмущения, когда вы застряли. Когда вы застряли, вы в основном добавляете в другой край и удалите один из графика и попробуйте продолжить. Если бы вы были совершенно неправильными, вы все еще можете добраться до решения, потому что в теории вы можете добавить во все правильные края и удалить все ваши оригинальные неверные варианты.
Изоляция моментальных снимков должна быть более эффективной для чтения, чем другие уровни изоляции. При разделении данных на моментальные снимки транзакции не требуется получать блокировки на строках, что предотвращает блокировку и взаимоблокировку.
Однако в базу данных tempdb необходимо записывать информацию об управлении версиями строк. Поэтому для каждой транзакции следует ожидать некоторое время записи.
Как и все остальное, ваши обстоятельства будут диктовать, будет ли это для вас более или менее результативным. Если приложение имеет стиль OLTP, это может привести к значительному повышению производительности, если транзакции подвержены блокировке.
-121--4746647-Объекты .Net не уничтожаются вручную. Вот что такое управляемая среда.
На самом деле, если объект действительно доступен, то есть у вас есть ссылка, которую вы можете использовать, чтобы сообщить GC, какой объект вы хотите уничтожить, сбор этого объекта будет невозможен. GC никогда не будет собирать объекты, которые по-прежнему доступны.
Можно вызвать GC.Collect () для принудительного создания общей коллекции. Однако это почти никогда не хорошая идея.
Вместо этого, вероятно, лучше просто сделать вид, что любой объект, который не использует неуправляемые ресурсы и недоступен для любого другого объекта в вашей программе, немедленно уничтожается. Я знаю, что этого не происходит, но в данный момент объект является просто блоком памяти, как любой другой; вы не можете вернуть его, и он в конечном итоге будет собран, так что он может быть так же мертв для вас.
Последнее примечание о IDisposable . Его следует использовать только для типов, объединяющих неуправляемые ресурсы: сокеты, подключения к базе данных, объекты gdi и т.д., а также периодическую подписку на событие/делегат.
Это действительно очень неясное объяснение, и алгоритм, похоже, не исходит ни из одной из перечисленных ссылок.
Идея, кажется, чтобы сначала сделать случайный путь, выбирая начальный узел наугад и происхождение этого, выбирая случайных соседей столько, сколько это возможно. Когда больше соседей не может быть выбрано, или путь гамильтонов, или это не. Если это не, у этого последнего узла на пути есть некоторый сосед уже на пути (см. ниже), таким образом, поворотное средство делает край от последнего узла к соседу, уже находящемуся на пути, и удаляет одну из линий связи из соседа, которые были выбраны для пути. Затем происходит новый конец пути, с которого процесс продолжается.
Этот алгоритм предполагает, например, что отсутствуют узлы только с одним краем. Эти легко прикрыть, хотя: если есть один из них, просто начните с того, если их два, начните с одного из них и попытайтесь в итоге оказаться на другом, а если их больше двух, гамильтонова тропа быть не может.