зв'язковим, тобто, що між довільною парою вершин існує ребро. У тих випадках, коли між окремими містами не існує повідомлення, цього можна досягти шляхом введення ребер з максимальною довжиною. Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує.
Залежно від того, який критерій вигідності маршруту зіставляється величиною ребер, розрізняють різні варіанти завдання, найважливішими з яких є симетрична і метрична завдання.
Приклад рішення задачі комівояжера на мові python на заданому графі ( Рис. 3.2 ).
У лістингу 2 наводиться скрипт для вирішення даної задачі.
Даний скрипт знаходить самий «вигідний» шлях від вершини 1 до вершини 4.
Лістинг 2.
networkx as nxmatplotlib.pyplot as pltnumpy=nx. Graph (); i in range (1,6):. Add_node (i). Add_edge (1, 2, node_color=«m», weight=2) # Параметр weight задає вагу ребра.add_edge (1, 3, node_color =«m», weight=1). add_edge (1, 4, node_color=«m», weight=20). add_edge (1, 5, node_color=«m», weight=10). add_edge (1 , 6, node_color=«m», weight=15). add_edge (5, 4, node_color=«m», weight=1). add_edge (1, 6, node_color=«m», weight=10) . add_edge (6, 1, node_color=«m», weight=4). add_edge (2, 3, node_color=«m», weight=10). add_edge (2, 5, node_color=«m», weight=5). add_edge (2, 6, node_color=«m», weight=20). add_edge (3, 6, node_color=«m», weight=6). add_edge (4, 2, node_color=« ; m », weight=15). add_edge (4, 3, node_color =« m », weight=40). add_edge (5, 6, node_color =« m », weight=10). add_edge (3, 5 , node_color=«m», weight=3). draw (G) # Отрісовка графа.show () _matrix=nx.adjacency_matrix (G) («Матриця вартості») (adjacency_matrix) # Вивід матриці ваг (nx.shortest_path (G, 1, 4)) # Вивід найкоротшого шляху
print (nx.dijkstra_path (G, 1, 4)) # Вивід самого «вигідної» шляху
Вихідні дані:
[1,4] - Найкоротший шлях
[1,3,5,4] - Вигідний шлях
Задача про призначення.
Задача про призначення - одна з фундаментальних завдань комбінаторної оптимізації в галузі математичної оптимізації або дослідженні операцій. Завдання полягає в пошуку мінімальної суми дуг у зваженому дводольному графі.
У найбільш загальній формі завдання формулюється таким чином:
Є деяке число робіт і деяке число виконавців . Будь виконавець може бути призначений на виконання будь-який (але тільки однієї) роботи, але з неоднаковими витратами. Потрібно розподілити роботи так, щоб виконати роботи з мінімальними витратами.
Якщо число робіт і виконавців збігається, то завдання називається лінійної завданням про призначення . Зазвичай, якщо говорять про задачі про призначеннях без додаткових умов, мають зважаючи лінійну задачу про призначення .
Припустимо, що таксомоторна компанія має три вільні машини (виконавці), і три замовника (роботи), які бажають отримати таксі якомога швидше. Фірма піклується про час доставки таксі до замовника, так що для кожної машини «вартість» визначається швидкістю, з якою машина дістанет...
