Как решить эту задачу?

Question

[PRIYD]

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

Есть граф с n вершин, в котором каждая вершина имеет определенное значение a_i. Также, каждая вершина объединена с каждой другой вершиной графа. Вес ребра между ними - |a_i1 - a_i2|. Как обойти все вершины графа и вернуться в исходную позицию, чтобы суммарный вес пройденных ребер был минимален?

Answer 1

[Wataru]

Представьте, что ваши вершины лежат на прямой OX в координатах (a_i, 0). Длины ребер тут будут тупо длинами отрезков. Теперь ваша задача обойти все точки на прямой и вернутся в начало, пройдя наименьшее расстояние.

Очевидно, что оптимальное решение тут, например, такое: начните в самой левой точке и идите по ним слева-направо. Дойдя до конца, вернитесь в самую левую точку. Это и будет оптимальное решение. Длина пути тут 2*(max(ai)-min(ai)).

Если нужна только длина пути - то можно тупо найти минимум и максимум и взять удвоенную разность. Если нужен сам путь, то сортируйте или пары {a_i, i} или сортируйте только индексы, используя собственную функцию сравнения, которая по двум целым числам сравнивает a[i1] и a[i2].

Comments

[PRIYD]

Громадное Вам спасибо! Я думал о варианте, который Вы описали, но не додумался отсортировать все значения, чтобы можно было это использовать действительно, как Ох. Спасибо!