Логика Python для нахождения минимального общего расстояния между двумя группами точек в декартовой системе

Есть разные способы решить эту проблему. Вот не слишком короткий ответ с объяснением:

from collections import defaultdict
from itertools import product

dist_dict = {
    "A": [{"x": 12}, {"y": 10}, {"z": 20}],
    "B": [{"x": 14}, {"y": 18}, {"z": 25}],
    "C": [{"x": 8}, {"y": 15}, {"z": 16}],
}


def get_indexes(t: tuple):
    """return a list containing the indexes of items of the `t` inside `player_moves"""
    return [lst.index(i) for lst, i in zip(player_moves.values(), t)]


# Creating a dictionary which maps player names to all available moves.
player_moves = defaultdict(list)
for lst in dist_dict.values():
    for d in lst:
        # Here a copy is needed because later we want to use this dictionary
        player, distance = d.copy().popitem()
        player_moves[player].append(distance)
print(player_moves)


# While iterating, we need to keep track of three things:
# 1. `minimun`: minimum sum of distances
# 2. `moves`: the instances that each player should go
# 3. `moves_indexes`: the indexes of numer 2.
minimun = float("inf")
moves = None
moves_indexes = None
# `product` generates all available moves for us.
for i in product(*player_moves.values()):
    indexes = get_indexes(i)

    # This check is needed because there shouldn't be a player with no move!
    if len(indexes) == len(set(indexes)):
        sum_of_distances = sum(i)
        if sum_of_distances < minimun:
            minimun = sum_of_distances
            moves = i
            moves_indexes = indexes

print(moves)
print(moves_indexes)
print({k: v[i].popitem()[0] for (k, v), i in zip(dist_dict.items(), moves_indexes)})

выход:

defaultdict(<class 'list'>, {'x': [12, 14, 8], 'y': [10, 18, 15], 'z': [20, 25, 16]})
(14, 10, 16)
[1, 0, 2]
{'A': 'y', 'B': 'x', 'C': 'z'}

Внутренняя структура данных (внутри dist_dict) также может быть словарем, чтобы вы могли получить доступ ко всем значениям расстояния по их ключам.

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

from itertools import permutations

dist_dict = {'A': {'x': 12, 'y': 10, 'z': 20},
             'B': {'x': 14, 'y': 18, 'z': 25},
             'C': {'x': 8, 'y': 15, 'z': 16}}

flags = list(dist_dict)
players = list(dist_dict['A'])

min_total_dist = 1000

for player_order in permutations(players):
    total_dist = sum(dist_dict[flag][player] 
                     for flag, player in zip(flags, player_order))
    if total_dist < min_total_dist:
        min_total_dist = total_dist
        best_player_order = player_order

print("optimal solution:")
for player, flag in zip(best_player_order, flags):
    print(f"    player {player} to flag {flag}")

print(f"optimal total distance: {min_total_dist}")

optimal solution:
    player y to flag A
    player x to flag B
    player z to flag C
optimal total distance: 40

Используйте itertools.permutations и минимизируйте, используя функцию, которая вычисляет общее расстояние. (Вы можете переставлять либо игроков, либо флаги. В этом случае я переставляю флаги.)

import itertools

dist = { # I have altered the format of this input slightly
        "A": {"x": 12, "y": 10, "z": 20},
        "B": {"x": 14, "y": 18, "z": 25},
        "C": {"x": 8, "y": 15, "z": 16},
    }

def total_distance(perm):
    return sum(d[flag] for d, flag in zip(dist.values(), perm))

best_perm = min(itertools.permutations("xyz"), key=total_distance)
result = dict(zip(dist, best_perm))

Другой вариант использует pandas и numpy, что сложнее, но может работать быстрее, если у вас много флагов и игроков.

import pandas as pd
import numpy as np
import itertools
dist = pd.DataFrame({ 
    "A": {"x": 12, "y": 10, "z": 20},
    "B": {"x": 14, "y": 18, "z": 25},
    "C": {"x": 8, "y": 15, "z": 16},
})
# make a numeric index [0,1,2]
index = list(range(len(dist)))             

# get all permutations of [0,1,2]
perms = list(itertools.permutations(index))   

# find the index of the permutation of [0,1,2] that minimizes total distance
best_perm_index = dist.to_numpy()[perms, index].sum(axis=1).argmin()  

# get the permutation itself, as a list
best_perm = list(perms[best_perm_index])     

# convert back to a dictionary
result = dict(zip(dist.columns, dist.iloc[best_perm].index))