我正在阅读一本算法教科书来提高我的算法技能，但我完全被这个问题所困扰，它困扰着我。我认为底层数据结构是一个图表，但我什至不知道从哪里开始解决这个问题。任何人都可以提供一些见解吗？谢谢
您将获得一张地形图，其中提供了任何两个相邻城市以及两个城市 a 和 b 之间的直接道路上的最大高度。提出一个线性时间算法，找到一条从 s 到 t 的路线，使最大高度最小化。道路可以双向穿越。
问问题
657 次
1 回答
2
这是一个棘手的问题。我假设本章中有一些提示可以指导您找到解决方案。
您描述的问题是极小极大路径问题或最宽路径问题的一个实例。 http://en.wikipedia.org/wiki/Wdest_path_problem
根据维基百科，有一个线性时间算法，但它非常复杂，所以我怀疑这本书希望你能弄清楚。解决这个问题的更简单的方法是找到最小生成树。由于最小生成树的“最小割”属性，沿着最小生成树连接 a 和 b 的路径将具有 minimax 属性，这意味着沿着该路径的最大高度将是连接 a 到 b 的任何路径中的最小值.
但是，没有线性时间最小生成树算法。另一方面，如果我们可以假设图是平面的——我们可能可以，因为它是一张路线图——那么就有可能在线性时间内找到最小生成树。所以我认为这就是他们可能追求的。包含这个问题的章节是否讨论了最小生成树和/或平面图？
于 2013-10-01T22:12:37.117 回答