Graph mining для решения транспортной задачи

Графами удобно моделировать задачи оптимизации. Для этого существует множество графовых алгоритмов, таких как Дейкстры, Крускала, Прима и многие другие. Рассматриваемый алгоритм Прима является наиболее легко реализуемым. Его смысл заключается в том, что нам необходимо каждый раз наращивать остов, прибавляя к нему наиболее оптимальное ребро, это свойство определяет принадлежность алгоритма к «жадным». Данный алгоритм подходит для решения транспортной задачи, т.к. новое присоединяемое ребро должно исходить из конечной точки предыдущего.

Перед тем, как приступить к написанию кода создадим датасет из матрицы A×B для примера. В нем будут содержаться вымышленные координаты точек для посещения и расстояния между ними, на основе которых нам необходимо составить оптимальный маршрут.

Nodes = [[120,60],[80,100],[80,160],[160,200],[160,260],[220,160],[220,120]]#координаты пунктов назначения Edges = [[0,1,56],[0,6,116],[1,2,60],[1,6,141],[2,0,107], [2,3,89],[2,4,128],[3,4,60],[3,5,72],[4,5,116],[5,6,40]]#нумерация ребер и расстояния между ними

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

for i in range(len(Nodes)): x_coordinates = Nodes[i][0] y_coordinates = Nodes[i][1] canv.create_oval(x_coordinates -3,y_coordinates -3,x_coordinates +3,y_coordinates +3, fill='red') canv.create_text(x_coordinates,y_coordinates,text=str(i),anchor='s') for k in range(len(Edges)): weight, start, end = Edges[k] x_start,y_start = Nodes[start] x_end,y_end = Nodes[end] canv.create_line(x_start,y_start,x_end,y_end,fill='gray')

Graph mining для решения транспортной задачи

Так как для реализации будем использовать матрицу смежности, создадим ее с использованием ранее созданных Nodes и Edges.

INF = 10 ** 9 W = [] for i in range(N): W.append(N*[INF]) for i in range(N): W[i][i] = 0 for i in range(M): weight, start, end = Edges[i] W[start][end] = weight W[end][start] = weight

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

distance = [INF] * N MST = {} used_nodes = [False] * N Ans = 0 distance[0] = 0 for i in range(len(Nodes)): min_distance = INF for j in range(len(Nodes)): if not used_nodes[j] and distance[j] < min_distance: min_distance = distance[j] u = j Ans += min_distance used_nodes[u] = True for v in range(len(Nodes)): dist[v] = min(distance[v], W[u][v]) if 0<W[u][v] and distance[v] == W[u][v]: MST[v]=u

Инициализация алгоритма начинается с того, что мы присваиваем переменной dist значение 0 для точки старта и указываем значение бесконечность для всех других вершин. Теперь, используя данные из ранее созданного списка MST, последовательно визуализируем все ребра оптимального дерева.

for start, end in MST.items(): xs,ys = Nodes[start] xe,ye = Nodes[end] canv.create_line(xs,ys,xe,ye,fill='blue',width=3) root.update() time.sleep(1)

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

Теперь нам только осталось сравнить последовательность пути, выбранную алгоритмом с последовательностью, совершенной по факту.