アルゴリズムの教科書を見てアルゴリズムのスキルを向上させますが、この質問に完全にこだわっており、それが私を悩ませています。基礎となるデータ構造はグラフであると思いますが、この問題のどこから始めればよいのかさえわかりません。
提供する地形図が提供されます最大高度 隣接する2つの都市間の直接道路沿い、および2つの 都市aおよびb。を見つける線形時間アルゴリズムを考え出す 最大高度を最小化するsからtへのルート。道路は 両方向に移動した。
回答：
回答№1は2これは難しい質問です。この章には、解決に向けたガイドとなるヒントがいくつかあると思います。
説明している問題は、ミニマックスパス問題または最も広いパス問題のインスタンスです。 http://en.wikipedia.org/wiki/Widest_path_problem
ウィキペディアによると、線形時間があるアルゴリズムですが、それはかなり複雑なので、この本はあなたがそれを理解することを期待していないと思います。この問題を解決する簡単な方法は、最小スパニングツリーを見つけることです。最小スパニングツリーの「最小カット」プロパティにより、最小スパニングツリーに沿ってaとbを接続するパスはminimaxプロパティを持ちます。つまり、このパスに沿った最大高度は、aからbを接続するパスの最小になります。 。
ただし、線形時間の最小スパンはありませんツリーアルゴリズム。一方、グラフが平面であると想定できる場合（ロードマップである可能性が高いため）、線形時間で最小スパニングツリーを見つけることができます。だから私はこれが彼らが後にするかもしれないものだと思う。この問題を含む章では、最小全域木および/または平面グラフについて説明していますか？