Каков алгоритм динамического программирования для нахождения гамильтонова цикла в графике?
Для того, чтобы глупо сохранить и служить other-servers-data.
В последние недели я играл с lifestream приложением, которое опрашивает мою подачу (восхитительный, flickr, GitHub, Твиттер...) и хранит их в couchdb. Красота couchdb состоит в том, что он позволяет мне сохранить исходные данные в его исходной структуре без издержек. Я добавил поле 'класса' к каждому документу, храня исходный сервер, и записал класс рендеринга JavaScript для каждого источника.
Обобщение, каждый раз, когда Ваш сервер связывается с другим сервером бессхемное устройство хранения данных, является лучшим, поскольку Вы не имеете никакого контроля над схемой. В качестве награды couchdb использует собственные протоколы серверов и клиентов - JSON для представления и HTTP REST для транспорта.
2 ответа
Действительно существует алгоритм динамического программирования O (n2 n ). для нахождения гамильтоновых циклов. Общая идея, которая может уменьшить количество подходов с возвратом O (n!) К O (n 2 2 n ) или O (n2 n ) (за счет использования большего объема памяти), заключается в рассмотрении подзадач, которые представляют собой наборы с указанными "конечными точками" .
Здесь, поскольку вам нужен цикл, вы можете начать с любой вершины. Итак, исправьте одно, назовите его x . Подзадачи могут быть следующими: «Для данного набора S и вершины v в S существует ли путь, начинающийся с x и проходя через все вершины S , заканчиваются на v ? » Назовите это, скажем, Poss [S] [v] .
Как и в случае с большинством задач динамического программирования, после определения подзадач все остальное очевидно: переберите все 2 n устанавливает S вершин в любом "возрастающем" порядке, и для каждого v в каждом таком S вы можете вычислить Poss [S] [v] как:
Poss [S] [v] = (существует некоторое
uв S такое, что возможно [S− {v}] [u] истинно и существует реброu-> v)
Наконец, существует гамильтонов цикл тогда и только тогда, когда существует вершина v такая, что существует ребро v-> x и Poss [S] [v] истинно, где ] S - это набор всех вершин (кроме x , в зависимости от того, как вы его определили).
Если вам нужен реальный гамильтонов цикл вместо того, чтобы просто решать, существует он или нет, сделайте возможности [S] [v] сохранить фактический u , который сделал это возможным, вместо просто правда или ложь; таким образом вы сможете проследить путь в конце.
Я не могу выделить этот конкретный алгоритм, но больше о гамильтоновых циклах можно найти на Гамильтоновой странице , чем вам, вероятно, когда-либо понадобится. :)
Эта страница должна быть исчерпывающий перечень бумаг, исходный код, препринты, технические отчеты и т. д., доступные на Интернет о гамильтоновом цикле и гамильтоновы проблемы пути, а также как некоторые связанные проблемы.