Блог

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

В этом примере гамильтонов круг выглядит так ..., u1, v1, ..., u2, v2, ... . В соответствии с неравенством треугольника я могу заменить эти ребра следующим образом

чтобы получить круг с меньшим весом.

Как я могу удалить все пересечения таким образом, эффективно используя python? Края хранятся как дикт, но я думаю, что могу использовать другой метод хранения, если он более уместен.