Ещё добавлю пять копеек к вопросу эвристик. Для симметричной версии задачи на плоскости можно несколько сократить число расчётов убрав заведомо неоптимальные связи. Например, построив для графа минимальное остовое древо, ветви которого будут своеобразными стенами, отсекающими части графа.
Это простая идея может в некоторых случаях сильно ускорить расчёт, но и она не идеальна. Вот пример того, когда эвристика не позволяет найти оптимальное решение.
Зелёным цветом - минимальное остовое древо
Красным - минимальный путь с учётом стен из ветвей остова (длина 4799)
Синим пунктиром - фактический минимальный путь (длина 4796)
Ну да время сократили, но это не минимальное решение.
Код
# Генерация случайного массива и сравнение у метода ветвей и границ с остовным беревом и без
import random
import matplotlib.pyplot as plt
import networkx as nx
import math as mt
import numpy as np
from ctypes import *
from datetime import datetime
import json
#-----------------------------------------------------------------
def distance(x1, y1, x2, y2):
return mt.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
#-----------------------------------------------------------------
def Intersection(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2):
v1 = (bx2 - bx1) * (ay1 - by1) - (by2 - by1) * (ax1 - bx1)
v2 = (bx2 - bx1) * (ay2 - by1) - (by2 - by1) * (ax2 - bx1)
v3 = (ax2 - ax1) * (by1 - ay1) - (ay2 - ay1) * (bx1 - ax1)
v4 = (ax2 - ax1) * (by2 - ay1) - (ay2 - ay1) * (bx2 - ax1)
if (v1 * v2 < 0) and (v3 * v4 < 0):
return True
else:
return False
#-----------------------------------------------------------------
def tsp_branch(n, py_arr, lib):
if n < 2:
return {}
flatten_arr = list(np.concatenate(py_arr).flat)
l = [-1] * (n * n - len(flatten_arr))
flatten_arr = (flatten_arr + l)[:n * n:]
int_arr = (c_int * (n * n))(*flatten_arr)
res = lib.tsp_branch(n, byref(int_arr))
if res > 0:
l = list(int_arr)[:res:]
return {'len' : l.pop(0), 'steps' : l.pop(0), 'path' : l}
else:
return {}
#-----------------------------------------------------------------
random.seed(40)
n = 35
INF = -1
#-----------------------------------------------------------------
v1 = []
points = {}
for i in range(n):
points[i] = (random.randint(1,1000), random.randint(1,1000))
input_matrix = []
for i, vi in points.items():
m1 = []
for j, vj in points.items():
if i==j:
m1.append(INF)
else:
m1.append(round(distance(vi[0], vi[1], vj[0], vj[1])))
v1.append([i,j,round(distance(vi[0], vi[1], vj[0], vj[1]))])
input_matrix.append(m1.copy())
#-----------------------------------------------------------------
lib_c = cdll.LoadLibrary(r"tsp_branch.dll")
lib_c.tsp_branch.argtypes = [c_int, c_void_p]
lib_c.tsp_branch.restype = c_int
#-----------------------------------------------------------------
start_time = datetime.now()
res1 = tsp_branch(n, input_matrix, lib_c)
date_diff = (datetime.now() - start_time).total_seconds()
print(date_diff)
print('Без остова:', res1['len'], res1['steps'], res1['path'])
if 'path' in res1:
d1 = []
for i, v in enumerate(res1['path']):
d1.append([res1['path'][i-1], res1['path'][i]])
#-----------------------------------------------------------------
plt.figure(figsize=(5, 5))
graph = nx.Graph()
graph.add_nodes_from(points)
# Добавляем дуги в граф
for i in v1:
graph.add_edge(i[0], i[1], weight=i[2])
mst = nx.minimum_spanning_tree(graph)
d2 = mst.edges()
for k in mst.edges():
for i in range(len(points)):
for j in range(len(points)):
if (i < j) and (k[0] != i) and (k[0] != j) and (k[1] != i) and (k[1] != j):
if Intersection(points[k[0]][0], points[k[0]][1], points[k[1]][0], points[k[1]][1], points[i][0], points[i][1], points[j][0], points[j][1]):
input_matrix[i][j] = INF
input_matrix[j][i] = INF
# Убираем удалённые рёбра в оригинальном графе
if graph.has_edge(i, j):
graph.remove_edge(i, j)
start_time = datetime.now()
res2 = tsp_branch(n, input_matrix, lib_c)
date_diff = (datetime.now() - start_time).total_seconds()
print(date_diff)
print('С остовом:', res2['len'], res2['steps'], res2['path'])
if 'path' in res2:
d3 = []
for i, v in enumerate(res2['path']):
d3.append([res2['path'][i-1], res2['path'][i]])
# -----------------------------------------------------------------
nx.draw(graph, points, width=1, edge_color="#C0C0C0", with_labels=True, node_size=200, font_size=10)
nx.draw(graph, points, width=7, edge_color="green", edgelist=d2, style="-", node_size=0, alpha=1)
nx.draw(graph, points, width=4, edge_color="red", edgelist=d3, style="-", node_size=0, alpha=1)
nx.draw(graph, points, width=3, edge_color="blue", edgelist=d1, style=":", node_size=0)
Основная проблема муравьиного алгоритма и других эвристических методов не в том, чтоб найти решении быстро, а в том, чтобы доказать, что оно лучшее из возможных. Хотя данное конкретное решение и может являться лучшим.
Тут не всё так однозначно, для плоскости есть более эффективные решения. А где гарантия что задающие вершины располагаются не в трёхмерном пространстве, n- мерном, или расчёт строения белков. Мне хотелось создать универсальный алгоритм.
оценки через эвклидовы расстояния
Над этим нужно думать.
Пробовал играться с минимальными остовыми деревьями как барьерами на плоскости, для уменьшения числа расчётов. Но и там есть исключения, не стал добавлять в текст, ибо остались вопросы.
Ну какие могут быть эвристики в точном решении? Эта реализация как раз и создавалась для поиска точного решения максимально быстро. Для эвристики существуют другие более выигрышные подходы.
Кэши хранят в [i] - элементе минимум2 по [i] строке.
line_cache[0] - нулевой элемент не используется, так как нулевая строка матрицы содержит индексы. Мне думается что в этом нагруженном куске делать пересчёт индекса на – 1 на каждом элементе цикла хуже неиспользуемых 4 байт.
Я возможно вас не совсем правильно понимаю, поясните свою мысль.
Я имел в виду рекурсию в широком смысле, как возможность не вызывать функцию дополнительный раз, когда нужно передавать что-то в виде параметров, которые будут хранится в стеке.
При стандартном алгоритме ветвей и границ мы в любом случае обязаны хранить обе ветви на каждом ветвлении. В моём варианте мы копируем только одну ветвь, а вторую обходим итеративно в цикле не выделяя память отдельно.
Вы не правы, метод ветвей и границ с полным перебором — это точный метод. Другое дело что его практически всегда используют с эвристиками, значительно уменьшающими число вычислений, но тогда да алгоритм перестаёт быть точным.
Эффект есть, и довольно значительный, иначе не было бы смысла об этом писать. Конкретные значения я не приведу, это требует отдельного обзора. Избавление от рекурсии как таковой не самоцель, это требуется для того чтоб не хранить отдельные матрицы на каждом шаге ветвления.
Очень грубый пример: матрица 32х32 требует в среднем где-то 10млн рабочих шагов, возьмём за среднее значение хранимой матрицы шага как 20х20 ~ 1кб. Получается нам нужно хранить в памяти более 9 ГБ информации. А если матрица ещё больше?
Если я правильно понимаю, подход применим только для симметричной задачи и только на плоскости. Я же предлагаю решать в общем виде. Хотя да результаты интересные.
Да, конечно сможет, но хоть один путь через вершину должен существовать иначе расчёт не имеет смысла. Когда нет прямой связи между городами в задающей матрице смежности элементу входящему в вершину и исходящему из неё нужно поставить -1.
Спасибо что вы не прошли мимо! Алгоритм как раз я понял хорошо, возможно выразил не совсем академично, но благодаря Вам, всё стало гораздо яснее. А мне ещё расти над собой.
Ну почему же, выскажитесь, с каким тезисом вы не согласны?
Ещё добавлю пять копеек к вопросу эвристик. Для симметричной версии задачи на плоскости можно несколько сократить число расчётов убрав заведомо неоптимальные связи. Например, построив для графа минимальное остовое древо, ветви которого будут своеобразными стенами, отсекающими части графа.
Это простая идея может в некоторых случаях сильно ускорить расчёт, но и она не идеальна. Вот пример того, когда эвристика не позволяет найти оптимальное решение.
Ну да время сократили, но это не минимальное решение.
Код
Основная проблема муравьиного алгоритма и других эвристических методов не в том, чтоб найти решении быстро, а в том, чтобы доказать, что оно лучшее из возможных. Хотя данное конкретное решение и может являться лучшим.
Тут не всё так однозначно, для плоскости есть более эффективные решения. А где гарантия что задающие вершины располагаются не в трёхмерном пространстве, n- мерном, или расчёт строения белков. Мне хотелось создать универсальный алгоритм.
Над этим нужно думать.
Пробовал играться с минимальными остовыми деревьями как барьерами на плоскости, для уменьшения числа расчётов. Но и там есть исключения, не стал добавлять в текст, ибо остались вопросы.
Ну какие могут быть эвристики в точном решении? Эта реализация как раз и создавалась для поиска точного решения максимально быстро. Для эвристики существуют другие более выигрышные подходы.
Так тут и используется этот подход, но это не является эвристикой.
Алгоритм можно ещё ускорить тут вы правы.
Чем тут помогут суперперестановки?
А вот тут +1 и вправду лишнее:
Про проклятие не уловил, можно подробнее?
Кэши хранят в [i] - элементе минимум2 по [i] строке.
line_cache[0] - нулевой элемент не используется, так как нулевая строка матрицы содержит индексы. Мне думается что в этом нагруженном куске делать пересчёт индекса на – 1 на каждом элементе цикла хуже неиспользуемых 4 байт.
Ах вот вы о чём, в таком изложении соглашусь с вами.
Я возможно вас не совсем правильно понимаю, поясните свою мысль.
Я имел в виду рекурсию в широком смысле, как возможность не вызывать функцию дополнительный раз, когда нужно передавать что-то в виде параметров, которые будут хранится в стеке.
При стандартном алгоритме ветвей и границ мы в любом случае обязаны хранить обе ветви на каждом ветвлении. В моём варианте мы копируем только одну ветвь, а вторую обходим итеративно в цикле не выделяя память отдельно.
Вы не правы, метод ветвей и границ с полным перебором — это точный метод. Другое дело что его практически всегда используют с эвристиками, значительно уменьшающими число вычислений, но тогда да алгоритм перестаёт быть точным.
Эффект есть, и довольно значительный, иначе не было бы смысла об этом писать. Конкретные значения я не приведу, это требует отдельного обзора. Избавление от рекурсии как таковой не самоцель, это требуется для того чтоб не хранить отдельные матрицы на каждом шаге ветвления.
Очень грубый пример: матрица 32х32 требует в среднем где-то 10млн рабочих шагов, возьмём за среднее значение хранимой матрицы шага как 20х20 ~ 1кб. Получается нам нужно хранить в памяти более 9 ГБ информации. А если матрица ещё больше?
Если я правильно понимаю, подход применим только для симметричной задачи и только на плоскости. Я же предлагаю решать в общем виде. Хотя да результаты интересные.
Да, конечно сможет, но хоть один путь через вершину должен существовать иначе расчёт не имеет смысла. Когда нет прямой связи между городами в задающей матрице смежности элементу входящему в вершину и исходящему из неё нужно поставить -1.
JIT-компиляция в Python, вкусно. Спасибо за наводку, обязательно попробую.
Решал похожую задачу по поиску расстояний. Смущает Ваш алгоритм расчёта ребра между двумя точками, уж слишком он приближённый, как по мне.
Такой точнее будет
Спасибо что вы не прошли мимо! Алгоритм как раз я понял хорошо, возможно выразил не совсем академично, но благодаря Вам, всё стало гораздо яснее. А мне ещё расти над собой.
Жаль, что вы не высказались за сам подход.
То на что вы даёте ссылку не коммивояжёр, это поиск кратчайшего пути в графе между точками. Это совсем другая задача.
Ну да, обычно дёргают готовую библиотеку, которая делает магию и всё. Я же хотел объяснить, как это происходит.
Проще конечно же! Но вот быстрее ли, сомнительно. Возможно Вы сможете доказать обратное.
Да и код для библиотеки уже существовал, нужно было только обернуть функцию.