コンピューター教授が盗難車両を回収するために使用する貪欲なアルゴリズムはどの程度実用的でしょうか?

超神経質で

ノートルダム大学コンピューターサイエンス学科の終身准教授兼博士指導教員であり、電子工学科の終身准教授も兼務するShi Yiyu氏は、昨年のクリスマス休暇中に、ハリウッド風の自動車狩り事件を経験した。

車両がハイジャックされてから 24 時間以内に、Shi 教授は車両自体が提供するファジー測位機能を使用して、 貪欲なアプローチ 貪欲なアルゴリズム、迅速かつ正確に車両の位置を特定し、彼の車を回収しました。

ケースレビュー

 

サウスベンド 

シカゴ

出発する

 

お昼休み

1日目 午前12時 ギャングによるカージャック Shi教授はタイヤに過給するためにガソリンスタンドに立ち寄った。施教授が車の状態を確認していたところ、2人の暴力団員が車を乗っ取り、パニックに陥り、施教授はこっそりと座席の後ろのポケットに携帯電話を入れた。
	1日目 午後17:00 追跡を開始する 警察に電話しても無駄だった後、石教授はできるだけ早く車の場所を見つけることを選択した。学校に戻ってから追跡を開始しましたが、携帯電話の測位はもう有効ではありませんでした。

2日目 午前5時 ファジーな位置決め Shi教授は、車に付属していたマツダモバイルスタート（MMS）を通じて、車のあいまいな位置を発見しました。車は彼から80キロ以上離れており、システム誤差は6〜7メートルでした。

2日目 午前7時 距離は60メートル！ Shi 教授の貪欲なアルゴリズムによる素早い推論:相対距離が縮まなくなったことが判明すると、時間内に停止し、垂直方向に探索を続けます。 このようにして、シー教授は距離をわずか 60 メートルまで近づけ、最終的にガレージ内で正確に位置決めしました。

2日目 午前9時 警察は無力だ 警察の到着を待っている間、シー教授とシャオ・ワンさんは、強盗たちが何か異変に気づいたかもしれないと気づき、車で立ち去った。シー教授は携帯電話を警察に渡し、警察はシー教授のアルゴリズムに従って捜索を続けた。

2日目 午前10時 車を返してください！ 石教授は携帯電話を取り戻した後、車発見アルゴリズムを使い続け、最終的に駐車場で盗難車を発見し、警察は車を石教授に返すことに成功した。

シー教授のカーチェイステクニック: 貪欲アルゴリズム

この緊迫したカージャック事件は、シー教授の処刑と正確なアルゴリズム推論のおかげで、わずか 24 日で発見することができました。

警察ですら、シー教授が問題を迅速に解決する能力に驚いています。

「彼らはコンピューター サイエンスの教授と手を組むべきではなかったのです。彼らは愚かなのでしょうか? どうしてコンピューター サイエンスの教授からお金を奪うことができるのでしょうか?」

Shi教授は、車両の位置を測位するための主要なテクノロジーは、実際にはコンピューターアルゴリズムにおける最も直接的な貪欲なアプローチであると説明しました。

貪欲なアルゴリズム、貪欲アルゴリズムとしても知られ、数学とコンピューターの分野で最も有名で古典的なアルゴリズムの 1 つです。

問題を解決するときは、前後に何が起こっても、現在の状態にのみ関係し、現在の部分問題に対する最適な解決策のみが得られます。ただし、その都度得られる局所最適解に基づいて大域最適解や最適目標を導出できればよい。

Shi教授は、貪欲なアルゴリズムを車の検索に適用しました。
  運転中、車との相対距離が縮まなくなっていることに気付いた場合は、適時に運転を中止してください。
  垂直方向に向きを変えて探索を続けます。

これはスパイラル探索構造であり、常に距離が減少する方向に単調に探索し、収束することが保証されます。

結局、シー教授は、1 台の車に 2 人しか乗っていなかったとき、ナビゲーション ソフトウェアの指導の下、貪欲なアルゴリズムが最も正確なツールであったため、誤差 3 キロメートルで盗難車を迅速に発見しました。

貪欲なアルゴリズムのその他の古典的なアプリケーション

古典的なアルゴリズムの 1 つである貪欲アルゴリズムの適用はあまり普及していません。

なぜなら、貪欲アルゴリズムは局所最適解を解く戦略を通じてのみ大域最適を達成できるからです。したがって、問題が貪欲アルゴリズム戦略の使用に適しているかどうか、および見つかった解決策が問題に対する最適な解決策である必要があるかどうかを判断することに注意を払う必要があります。

たとえば、ナップザック問題やパス問題など、貪欲の美しさを説明する古典的なアルゴリズムの例をいくつか示します。

ダイクストラのアルゴリズムこれは、重み付き有向グラフで単一ソース最短パス (SSSP) を計算するためのアルゴリズムで、1956 年にコンピューター科学者のエドガー ダイクストラによって考案され、1959 年に公開されました。

それが解決する問題は次のとおりです。
グラフ G とソース頂点 v が与えられた場合、v からグラフ内のすべての頂点までの最短パスを見つけます。

ダイクストラのアルゴリズムは、Greedy アルゴリズム パラダイムを使用して設計されています。

パスの長さの増加順に、各頂点の最短パスを 1 つずつ生成します。アルゴリズムのプロセス中、頂点セット SS は、最短パスを見つけた頂点を保存する必要があります。距離配列 dist を維持することも必要です。dist[i] は、i 番目の頂点とソース ノード s の間の距離の長さを表します。

• S には、初期化時にソース ノード s のみが含まれます。dist[]dist[] 初期化: dist[i]= arc[s][i]、arc はグラフの隣接行列です。 V-SV-S は、最短パスが見つからなかった頂点のセットを表します。

• distdist を昇順に並べ、最短パスを選択し、対応する頂点を V-SV-S から S に追加します。新しい頂点 u が S に追加されるたびに、distdist を更新する必要があります。つまり、s が他の頂点に到達できるかどうかです。頂点 u を通る点が近づきます。 
  つまり、 dist[u] + arc[u][v] < dist[v] の場合、 dist[v]=dist[u]+arc[u][v] を更新します。 

• S=VS=V になるまで上記の手順を繰り返します。 

イースターエッグ: 新しい質問タイプの貪欲なアルゴリズム

H 国の建国記念日に合わせて、国王は n 人の大臣を賞金付きのゲームに招待しました。まず、各大臣に左手と右手にそれぞれ整数を書くように言い、国王自身も左手と右手に整数を書きました。

次に、これら n 人の大臣を一列に並べ、王を列の先頭に立たせます。整列後、すべての大臣は王から報酬として金貨を受け取ります。各大臣が受け取る金貨の数は次のとおりです。大臣の前にいる全員の左手の数字の積を自分の右手の数字で割って、その結果を切り捨てます。

国王は、特定の大臣に特別に多額の報酬を受け取ってほしくないので、最も多くの報酬を獲得した大臣ができるだけ少ない報酬を受け取るようにチームの順序を再調整するのを手伝ってほしいと考えています。

(キングの位置は常に列の先頭であることに注意してください。)