Решение TSP с GA: Должна ли матрица расстояний ускорить время выполнения? - PullRequest
0 голосов
/ 09 декабря 2018

Я пытаюсь написать GA на Python, чтобы решить TSP.Я хотел бы ускорить это.Потому что сейчас требуется 24 секунды для запуска 200 поколений с численностью населения 200 .

Я использую карту с 29 городов .У каждого города есть id и (x, y) координаты.

Я попытался реализовать матрицу расстояний, которая рассчитывает все расстояния один раз и сохраняет ее в списке.Таким образом, вместо расчета расстояния с использованием функции sqrt() 1M + раз, она использует функцию только 406 раз.Каждый раз, когда требуется расстояние между двумя городами, оно просто извлекается из матрицы с использованием идентификатора двух городов в качестве индекса.

Но даже при этом это занимает столько же времени.Я думал, что sqrt() будет дороже, чем просто индексировать список.Это не?Словарь сделает это быстрее?

1 Ответ

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

Краткий ответ:

Да.Словарь сделает это быстрее.

Длинный ответ:

Допустим, вы предварительно обрабатываете и рассчитываете все расстояния один раз - Отлично!Теперь, допустим, я хочу найти расстояние между А и В. Итак, все, что мне нужно сейчас сделать, - это найти расстояние, на котором я его поместил - оно в списке!

Сколько времени сложно найти что-то в списке?Правильно - O (n)

И как я могу использовать его?Мое предположение по вашему вопросу: 1M + раз

Теперь это огромная проблема.Я предлагаю вам использовать словарь, чтобы вы могли искать в заранее рассчитанном расстоянии между любыми двумя городами в O (1).

...