Как применить формулу расстояния к списку [x, y] координат в python - PullRequest
Новая
       12

Как применить формулу расстояния к списку [x, y] координат в python

0 голосов
/ 15 мая 2018

Чтобы решить задачу коммивояжера (TSP) с использованием генетического алгоритма, я случайным образом генерирую список из Z точек на сетке N by N: 

field = [random.sample(range(N), 2) for x in range(Z)]

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

path = random.sample(field, len(field))
path.append(member[0])

Этоодин из возможных «путей»: 

[[0, 7], [167, 118], [150, 173], [37, 21], [48, 150], [0, 7]]

Однако мне также необходимо измерить пригодность, то есть длину пути, чтобы определить, какие пути следует исключить, а какие -сохранить (так как это генетический алгоритм).И здесь я не понимаю, как действовать дальше.

Моя текущая идея - использовать Формула расстояния для пары точек, но тогда все значения должны быть продублированы для меня.чтобы передать каждую пару координат x, y в мой калькулятор для нахождения формулы расстояния.

Например, для точек выше, она должна выглядеть примерно так: 

[[[0, 7], [167, 118]], [[167, 118], [150, 173]], [[150, 173], [37, 21]],....]

С технической точки зрения я понятия не имею, как бы я мог создать такой список.

PS Я нашел этот ответ на проблему, однако он находится в R, и я до сих пор не понимаю, как подойти к этой проблеме.

Ответы [ 2 ]

0 голосов
/ 15 мая 2018 
def dist(p1, p2):
    return math.hypot(p2[0] - p1[0], p2[1] - p1[1])

route = [[3, 0], [0, 4], [1, 4], [2, 1], [1, 4], [3, 0]]

total_dist = 0.0
for i in range(len(route) -1):
    total_dist += dist(route[i], route[i+1])
0 голосов
/ 15 мая 2018

Это просто сделать с zip, используя слайсы, за исключением того, что zip создает кортежи вместо списков: 

>>> list(zip(path[0:], path[1:]))
[([0, 7], [167, 118]), ([167, 118], [150, 173]), ([150, 173], [37, 21]), ([37, 21], [48, 150]), ([48, 150], [0, 7])]

Если вам абсолютно необходимы списки вместо кортежей, вы можете создать их аналогично с помощьюпонимание списка. 

>>> [[a, b] for a, b in zip(path[0:], path[1:])]
[[[0, 7], [167, 118]], [[167, 118], [150, 173]], [[150, 173], [37, 21]], [[37, 21], [48, 150]], [[48, 150], [0, 7]]]
...