Вставьте узел в график в его лучшем месте, а не в конце графика

Предположим, у меня есть 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]

Можете ли вы дать более ясный пример того, что вы пытаетесь сделать? Итак, дайте нам полный ввод (предположительно, включая график) и каким должен быть результат?

Joel 14.03.2018 08:28

Я ищу самый быстрый способ алгоритма «Самая дешевая вставка» (или «Лучшая вставка»). Ниже я приведу пример размером с игрушку: 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]

MASOUD 14.03.2018 08:48

В networkx есть функция под названием (dijkstra_path_length). Есть ли какая-нибудь похожая функция для этого лучшего алгоритма вставки? Если нет, что было бы эффективным способом сделать это? (вместо вложенных циклов)

MASOUD 14.03.2018 08:52

Какова ваша функция затрат?

michaelg 14.03.2018 10:50

Функция стоимости - это расстояние между узлами. Итак, Cost[2,6,5,7] = Distance[2][6] + Distance[6][5] + Distance[5][7]

MASOUD 14.03.2018 11:27

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

Joel 15.03.2018 01:26

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

Joel 15.03.2018 01:29

Спасибо за отзыв, Джоэл. Редактировал главный вопрос. Надеюсь, вы это понимаете.

MASOUD 15.03.2018 07:24
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
8
94
0

Другие вопросы по теме