最大化所有人的出行距离总和
最大化您的旅行计划中所有人的旅行距离总和。一个人的出行距离是指他所居住的城市与他所前往的城市之间的距离。旅行者在旅行时总是选择最短路线。
问题陈述:给定一个位置列表(代表人们的位置),找到使所有人的总旅行距离最小化的最佳集合点。
最小化算法
- 对位置列表进行排序。
- 找出位置中位数。中位数最小化与所有其他位置的绝对差值之和。
- 计算所有人到中位数位置的总路程。
def minTotalDistance(positions): |
最大距离算法
任务是设计一个旅行计划,以满足两个规则:
- 所有的人都应该去对方的城市之一。
- 他们两个从来没有去过同一个城市。
利用深度优先搜索(DFS)和树上的组合学找出最大移动距离:
什么是深度优先搜索(DFS)
深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始(在图的情况下选择某个任意节点作为根节点),并在回溯之前沿着每个分支尽可能远地探索。
树形数据结构可以通过以下方式遍历:
- 深度优先搜索或 DFS[list=1]
- 中序遍历
- 预序遍历
- 后序遍历
图的深度优先遍历(DFS)类似于树的深度优先遍历。
唯一与树不同:图可能包含循环(一个节点可能被访问两次)。为了避免多次处理节点,请使用布尔访问数组。
思路
首先,我们可以将此问题陈述可视化为一棵树,其中每个城市充当树的节点,每个道路连接充当顶点之间的边。
为了最大化总行驶距离,我们需要尽可能最大化每条边的贡献。
分步算法:
- 根据给定的输入创建邻接加权树。
- 我们可以使用 count[] 数组来跟踪节点的子节点数量,使用它我们可以计算:
- 节点 x 左侧的节点数= count [x]
- 节点 x 右侧的节点数= 节点总数 – count [x]
- 调用深度优先搜索计算count数组
- 迭代每条边并使用以下公式将其最大贡献添加到最终答案中:
- Min(count[x], 总节点数-count[x]) * 边权重 * 2
import java.util.ArrayList; |
另外一种算法Python:
from collections import defaultdict |