Branch and Bound – Бонусная статья – Визуализация узлов

Branch and Bound - Бонусная статья - Превосходная визуализация узлов

Использование пакета NetworkX для визуализации алгоритма ветвей и границ в действии

Введение

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

Статьи в этой серии следующие:

• Ветвление и границы – Введение перед созданием алгоритма с нуля
• Ветвление и границы – Создание алгоритма с нуля

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

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

• Топ важных статей LLM на неделю с 23/10 по 29/10
• Метод разветвления и границ – написание алгоритма с нуля
• Обзор книги Определительное руководство по генеративным ИИ для промышленности от Cognite

Код визуализации

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

Мы будем раскрашивать узлы разными цветами, чтобы визуализировать те, которые были отсечены, для удобства справки.

Дополнение № 1 – Инициализация

import numpy as npfrom scipy.optimize import linprogimport networkx as nximport matplotlib.pyplot as pltoptimal_value = -np.infoptimal_solution = None# Дерево для хранения узлов и связейG = nx.DiGraph()node_counter = 0optimal_node = None

В этом коде мы добавили два пакета для импорта: matplotlib и networkx.

Кроме того, мы инициализируем три переменные, которые необходимы для нашего графа сети:

• G – или объект networkx
• node_counter – для названия узлов и их соединения.