Избавление от продавца Алгоритм

Question

Мне трудно построить небольшой неориентированный граф G, у которого есть взвешенные ребра, которые перехитрили данный алгоритм, что означает, что алгоритм не будет выбирать оптимальное решение, независимо от начальной точки. Каждый узел подключается к каждому другому узлу.

Учитывая начальную точку, алгоритм итеративно выбирает ближайшую неиспользованную точку на графике и посещает ее до тех пор, пока она не вернется к начальной точке. Алгоритм выполняет грубую силу, работая с каждой точкой, являющейся начальной точкой, и выбирает самый короткий гамильтоновский цикл из всех выведенных циклов.

Я за жизнь меня не смог понять это, я нарисовал бесчисленные графики, прошел и решил их, и до сих пор не смог придумать график, что алгоритм не найдет оптимального решения для.

Это полностью теоретический и не имеет никакого кода. Любое руководство или указатели относительно того, как я должен подходить/думать об этом, очень ценится.

Answer 1

Рассмотрим следующий 4-вершин графа:

Мы имеем ребра AB и CD длины 2, ВС длины 1, АС и BD длиной 3 и AD длины бесконечности (или произвольно большой).

Если вы начинаете с A и следуете жадному подходу, вы переходите к B (длина 2), затем C (длина 1), затем D (длина 2), а затем застреваете, принимая DA (бесконечность длины). По симметрии графика вы получаете тот же результат, начиная с D (вы идете D -> C -> B -> A -> D, бесконечность длины).

Если вы начинаете с B и следуете жадному подходу, вы переходите к C (длина 1), затем D (длина 2), затем A (длина бесконечности - это единственный доступный ход, так как мы уже посетили B и C) и, наконец, B (длина 2). По симметрии графика вы получаете тот же результат, когда начинаете с C (вы идете C -> B -> A -> D -> C, бесконечность длины).

Короче говоря, независимо от того, где начинается жадный подход, в итоге получается бесконечная длина. Между тем путь A -> C -> D -> B -> A имеет длину 10.

Не только алгоритм грубой силы не оптимален независимо от начальной точки, но и работает безгранично плохо.