2-опционный алгоритм для решения задачи коммивояжера в Python - PullRequest
Новая
       16

2-опционный алгоритм для решения задачи коммивояжера в Python

0 голосов
/ 13 ноября 2018

Мне не удалось найти полную реализацию алгоритма 2-opt в Python, поэтому я пытаюсь добавить недостающие части в код, найденный здесь , который я представляю ниже. 

def two_opt(route):
     best = route
     improved = True
     while improved:
          improved = False
          for i in range(1, len(route)-2):
               for j in range(i+1, len(route)):
                    if j-i == 1: continue # changes nothing, skip then
                    new_route = route[:]
                    new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
                    if cost(new_route) < cost(best):  # what should cost be?
                         best = new_route
                         improved = True
          route = best
     return best

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

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

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

def main():
    # code to read from file
    # code to append co-ordinates to points and calculate the haversine distance between each point
    route = random.sample(range(10), 10)
    best = two_opt(route, adj_matrix)  # passing my adjacency matrix
    print(best)

ValueError: Значение истинности массива с более чем одним элементом является неоднозначным. Используйте a.any () или a.all ()

Еще один вопрос из двух вариантов Python: Генерация всех соседей для 2OPT в python

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

Ответы [ 2 ]

0 голосов
/ 30 декабря 2018

2-opt удаляет два ребра и создает два новых (при условии, что матрица затрат симметрична), поэтому функцию стоимости можно упростить, чтобы рассмотреть только изменяющиеся ребра. Для больших массивов это намного быстрее, чем перечисление по всему маршруту. 

import numpy as np

def cost_change(cost_mat, n1, n2, n3, n4):
    return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]


def two_opt(route, cost_mat):
    best = route
    improved = True
    while improved:
        improved = False
        for i in range(1, len(route) - 2):
            for j in range(i + 1, len(route)):
                if j - i == 1: continue
                if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
                    best[i:j] = best[j - 1:i - 1:-1]
                    improved = True
        route = best
    return best


if __name__ == '__main__':
    nodes = 1000
    init_route = list(range(nodes))
    print(init_route)
    cost_mat = np.random.randint(100, size=(nodes, nodes))
    cost_mat += cost_mat.T
    np.fill_diagonal(cost_mat, 0)
    cost_mat = list(cost_mat)
    best_route = two_opt(init_route, cost_mat)
    print(best_route)
0 голосов
/ 13 ноября 2018

Прежде всего, матрица смежности обычно является (0, 1) -матрицей . То, что у вас есть здесь, по-разному называется стоимость , вес или матрица расстояний .

Теперь к вашему вопросу.

Функция стоимости может быть простой: 

def cost(cost_mat, route):
   return cost_mat[np.roll(route, 1), route].sum()

Здесь np.roll() «поворачивает» маршрут на одну позицию, чтобы упростить его использование с route для индексации в матрице затрат. sum() просто складывает стоимость отдельного сегмента для вычисления общей стоимости маршрута.

(Если в какой-то момент вы решите взглянуть на Асимметричный TSP, вам нужно убедиться, что порядок строк / столбцов соответствует построению cost_mat; для евклидового TSP это не имеет значения, поскольку матрица затрат симметрично.)

Пример использования: 

cost_mat = np.array([
   [0, 1, 2, 3],
   [1, 0, 4, 5],
   [2, 4, 0, 7],
   [3, 5, 7, 0],
])

route = np.array([2, 1, 3, 0])

print(cost(cost_mat, route))
...