Предположим, у меня есть list=[2,5,7]
(представляющий порядок посещения городов). Я хочу вставить узел 6
в этот список (или в график); впрочем, ищу лучшее место для прошивки (по общей стоимости list
). Например, стоимость list1=[2,6,5,7]
ниже, чем стоимость list2=[2,5,7,6]
. Функция стоимости - это расстояние между узлами. Например, Cost[2,6,5,7] = Distance[2][6] + Distance[6][5] + Distance[5][7]
Есть ли быстрый способ сделать это? Есть ли в Networkx встроенная функция (например, nx.dijkstra_path_length(G, i, j, 'weight')
, которая вычисляет кратчайший путь перед вставкой) или любой другой пакет? Обратите внимание, что list=[2,5,7]
можно рассматривать как график и легко генерировать с помощью Networkx (2---5---7)
.
P.S: Ниже я приведу экземпляр размером с игрушку: a=[6,10]
и list=[2,5,7]
- мои входы. Я хочу добавить все узлы в a
(6 и 10) в лучшие места в list
(например, добавление узла в тур TSP). Есть два возможных положения для вставки 6 в list
.
A: между 2
и 5
B: между 5
и 7
.
Начиная с Cost[2,6,5,7] < Cost[2,5,7,6]
, вариант A обеспечивает самую низкую стоимость.
Сейчас list=[2,6,5,7].
Опять же, для вставки узла 10
необходимо проверить все три возможных места.
A: между 2
и 6
B: между 6
и 5
C: между 5
и 7
.
Результатом будет список вроде [2,6,5,10,7]
Я ищу самый быстрый способ алгоритма «Самая дешевая вставка» (или «Лучшая вставка»). Ниже я приведу пример размером с игрушку: a=[6,10]
и list=[2,5,7]
- мои входы. Я хочу добавить узлы 6
и 10
к list
(например, добавить узел в тур TSP). Есть два возможных положения для вставки A: от 2 до 5 B: от 5 до 7. Поскольку вариант A Cost[2,6,5,7] < Cost[2,5,7,6]
обеспечивает наименьшую стоимость. Теперь list=[2,6,5,7]
. Снова для вставки узла 10
должны быть проверены все три возможных места A: между 2 и 6 B между 6 и 5 C: между 5 и 7. output=[2,6,5,10,7]
В networkx есть функция под названием (dijkstra_path_length). Есть ли какая-нибудь похожая функция для этого лучшего алгоритма вставки? Если нет, что было бы эффективным способом сделать это? (вместо вложенных циклов)
Какова ваша функция затрат?
Функция стоимости - это расстояние между узлами. Итак, Cost[2,6,5,7] = Distance[2][6] + Distance[6][5] + Distance[5][7]
Измените дополнительную информацию в своем вопросе, чтобы вопрос был самодостаточным, без чтения комментариев. Комментарии можно удалить в любой момент.
Вы явно думаете об этом как о проблеме с графиком. Но в вашем вопросе или комментариях графика нет. Нам нужен минимальный воспроизводимый пример.
Спасибо за отзыв, Джоэл. Редактировал главный вопрос. Надеюсь, вы это понимаете.
Можете ли вы дать более ясный пример того, что вы пытаетесь сделать? Итак, дайте нам полный ввод (предположительно, включая график) и каким должен быть результат?