Найти гамильтонов цикл, не превышающий в два раза минимальную стоимость в O (m + n log n) в неориентированном графе с затратами, удовлетворяющими неравенству треугольника - PullRequest
0 голосов
/ 02 июня 2018

Итак, мне дали это задание, и я не знаю, как использовать информацию о расходах.Это требование, и у меня нет дополнительной информации.

1 Ответ

0 голосов
/ 04 июня 2018

Это должно быть решено алгоритмом аппроксимации двойного дерева для решения задачи TSP (задача коммивояжера) / цепи Гамильтона.Для этого необходимо выполнить два условия входного графа:

  • неравенство треугольника (у вас есть это)
  • полный граф (У вас есть это? Это значит, что должен быть грань междукаждые две вершины графа.)

Алгоритм работает следующим образом:

  • найти минимальное остовное дерево входного графа (для этого есть несколько алгоритмов; еслипредставление вашего графа является списком сопряженности, сложность O (e + v * log (v)))
  • Удвойте каждое ребро в связующем дереве - у вас будет мультиграф (O (e))
  • создайте путь Эйлера в этом графе - если вы встретите вершину во второй раз, пропустите ее и возьмите прямое ребро к следующей вершине (это ребро существует в графе, поскольку у вас есть полный граф) - это также должно быть что-то вродеO (e + некоторый логарифм)
  • Вы закончили - вы нашли цепь Гамильтона (и решили TSP)

Этот алгоритм 2-приблизительный (стоимость схемы составляетпри максимальном удвоении оптимальное решение - естьэто доказательство, которое я могу предоставить, если хотите).Худшая сложность - O (e + v log (v)) - e - это число ребер, v количество вершин ... это должно соответствовать вашему O (m + n log (n)).

На данный момент я не смог найти хорошую связь с объяснением алгоритма, постараюсь предоставить его позже.

...