1

最大化所有人的出行距离总和

 8 months ago
source link: https://www.jdon.com/71344.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

最大化所有人的出行距离总和

最大化您的旅行计划中所有人的旅行距离总和。一个人的出行距离是指他所居住的城市与他所前往的城市之间的距离。旅行者在旅行时总是选择最短路线。

问题陈述：给定一个位置列表（代表人们的位置），找到使所有人的总旅行距离最小化的最佳集​​合点。

最小化算法

  • 对位置列表进行排序。
  • 找出位置中位数。中位数最小化与所有其他位置的绝对差值之和。
  • 计算所有人到中位数位置的总路程。 
def minTotalDistance(positions):
    positions.sort()

# 计算中位数
    median = positions[len(positions) // 2]

# 计算总行程
    total_distance = sum(abs(pos - median) for pos in positions)

return total_distance

# Example
people_positions = [1, 2, 3]
result = minTotalDistance(people_positions)
print("Minimum total travel distance:", result)

最大距离算法
任务是设计一个旅行计划，以满足两个规则：

  1. 所有的人都应该去对方的城市之一。
  2. 他们两个从来没有去过同一个城市。

利用深度优先搜索（DFS）和树上的组合学找出最大移动距离：

什么是深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始（在图的情况下选择某个任意节点作为根节点），并在回溯之前沿着每个分支尽可能远地探索。

树形数据结构可以通过以下方式遍历：

  1. 深度优先搜索或 DFS[list=1]
层序遍历或广度优先搜索或 BFS 对角线遍历

图的深度优先遍历（DFS）类似于树的深度优先遍历。
唯一与树不同：图可能包含循环（一个节点可能被访问两次）。为了避免多次处理节点，请使用布尔访问数组。

思路
首先，我们可以将此问题陈述可视化为一棵树，其中每个城市充当树的节点，每个道路连接充当顶点之间的边。

为了最大化总行驶距离，我们需要尽可能最大化每条边的贡献。

分步算法：

  • 根据给定的输入创建邻接加权树。
  • 我们可以使用 count[] 数组来跟踪节点的子节点数量，使用它我们可以计算：
    • 节点 x 左侧的节点数= count [x]
    • 节点 x 右侧的节点数= 节点总数 – count [x]
  • 调用深度优先搜索计算count数组
  • 迭代每条边并使用以下公式将其最大贡献添加到最终答案中：
    • Min(count[x], 总节点数​​-count[x]) * 边权重 * 2 
import java.util.ArrayList;
import java.util.List;

class Main {

static int dfs(List<List<Pair>> g, List<Integer> vis, 
                List<Integer> count, int n, int vrtx, int[] ans) {
        // 标示已访问的当前节点
        vis.set(vrtx, 1);
        // increment the count of vertex by 1
        count.set(vrtx, 1);

//对当前顶点的每个相邻顶点进行 dfs 调用
        for (Pair child : g.get(vrtx)) {
            int cv = child.first;
            int wt = child.second;

if (vis.get(cv) == 0) {
                count.set(vrtx, count.get(vrtx) + dfs(g, vis, count, n, cv, ans));
               // x 和 y 分别存储 vrtx 左侧和右侧顶点的数量。
                // 和 vrtx 右边的顶点数
                int x = count.get(cv);
                int y = n - x;
                // add the contribution of the current wt to the
                // ans
                ans[0] += Math.min(x, y) * 2 * wt;
            }
        }
        return count.get(vrtx);
    }

// Driver code
    public static void main(String[] args) {
        // Taking input
        int N = 4;
        List<List<Integer>> roads = new ArrayList<>();
        roads.add(List.of(1, 2, 3));
        roads.add(List.of(2, 3, 2));
        roads.add(List.of(4, 3, 2));

//使用给定的输入构造双向图
        List<List<Pair>> g = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            g.add(new ArrayList<>());
        }

for (List<Integer> road : roads) {
            int u = road.get(0);
            int v = road.get(1);
            int w = road.get(2);
            g.get(u).add(new Pair(v, w));
            g.get(v).add(new Pair(u, w));
        }

// visited array
        List<Integer> vis = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            vis.add(0);
        }

// 计数数组，用于记录每个顶点左右两侧的顶点数
        // 每个顶点左右两边的顶点数
        List<Integer> count = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            count.add(0);
        }

// initialize answer to 0
        int[] ans = {0};

// 调用 dfs 计算结果
        dfs(g, vis, count, N, 1, ans);
        System.out.println(ans[0]);
    }
}

class Pair {
    int first, second;

public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

另外一种算法Python：

from collections import defaultdict

def max_distance_travelled(graph, start):
    max_distance = 0

def dfs(node, parent):
        nonlocal max_distance

# Collect distances from the children
        distances = []
        for neighbor in graph[node]:
            if neighbor != parent:
                child_distance = dfs(neighbor, node)
                distances.append(child_distance)

按降序排列距离
        distances.sort(reverse=True)

# 如果至少有两个孩子，则更新 max_distance
        if len(distances) >= 2:
            max_distance = max(max_distance, distances[0] + distances[1])

# 返回从该节点到任何叶子的最大距离
        return 1 + (distances[0] if distances else 0)

dfs(start, None)
    return max_distance

# Example
graph = defaultdict(list)
graph[1]

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK