HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

困難な問題とヒューリスティックな回答

Hard Problems and Heuristic Answers (stochastic.blog)

5 pointsby Anon841 コメント

要約

この記事では、最適化問題、特に巡回セールスマン問題(TSP)を取り上げ、厳密な解法と、計算速度のために最適性を犠牲にするヒューリスティック(近似)解法との違いを探求します。OpenFlightsのデータを用いて12空港のTSPインスタンスを作成し、厳密な解と3つの異なるヒューリスティック手法による近似解を比較することで、困難な問題における確実性と速度のトレードオフの本質を解説します。

全文翻訳

困難な問題とヒューリスティックな解答

Stochastic Blog

[画像: 困難な問題とヒューリスティックな解答]

ポスト8では、問題を解ける形に変える最適化ツールキットを構築し、勾配と凸性がどのように良い解答への道筋を与えるかを学びました。今回は、私たちが知っているどんな巧妙なトリックにも抵抗する問題があるという、より厳しい現実に直面します。それらの問題に対しては、その難しさを正確に理解し、確実性を速度と交換する手法に頼るのが唯一誠実な対応です。この記事の終わりまでに、12空港の巡回セールスマン問題(全ての空港を一度ずつ訪問する最短の往復経路を見つける問題)を正確に62,741 kmで解き、その後、3つの異なるヒューリスティック(速度のために保証された最適性を犠牲にする近似手法)が様々な成功度でその数値に迫る様子を観察し、それらの間のギャップが失敗ではなく、困難な問題の本質そのものである理由を理解します。

OpenFlightsデータセットは、約2MBのCSVファイルに約7,700の空港と67,000のルートという生の材料を提供してくれます。私たちはルートからグラフを構築し、空港間の大圏距離を計算し、6大陸にまたがる小さくも現実的な巡回セールスマン問題を作成します。この記事の通底するテーマは、証明できることと計算できることの間のギャップ、そして私たちが遭遇するあらゆる手法が、実際にはそのギャップを交渉するさまざまな方法であるということです。

データ

ソルバーがツアーに触れる前に、何を取り扱っているかを知る必要があります。重複と自己ループを削除した後、ルートグラフは3,425ノードと19,256エッジを持ち、次数(直接接続数)の分布はすぐにパターンを示します。

[画像: 空港ルートの次数分布]

図2. 次数分布はヘビーテールを持っています:少数のハブが巨大な次数を持ち、ほとんどの空港は数カ所の目的地にしか接続していません。

ログログプロットはヘビーテールを示しています:LHRやJFKのような少数のハブは巨大な次数を持ちますが、ほとんどの空港は数カ所の目的地にしか接続していません。ハブの基本レート(次数が10以上である空港の割合)は21.9パーセントです。これは、地理的に広範囲にわたるTSPを有意義にする構造です。なぜなら、巨大な連結成分が3,425空港のうち3,397空港を保持しており、主要都市を巡るツアーは一つの連結された世界内に留まるからです。

棒グラフはその不均衡を確認しています:ハブは少数派ですが、接続性を支配しています。

[画像: ハブステータスの分布]

図1. ハブは空港の少数派ですが、接続性を支配しています。

私たちの目的においては、これは重要です。なぜなら、主要な国際ハブから抽出された12空港のサンプルは、現実的な距離と本物の最適化問題を持つからです。また、1,625の重複したIATA行と1つの自己ループが見つかったため、これらをツアーインスタンスを構築する前に統合します。データは現実的であるには十分乱雑で、作業するには十分きれいです。

困難さとランダム性

グラフが構築されたら、最初のモジュールは、検証できる解答と見つけられる解答の間の壁に直面します。P対NP問題は、解答を素早く検証できる問題はすべて素早く見つけることもできるのか、と問います。この記事の問題については、私たちは一般的な合意である「いいえ」を受け入れます。多項式還元は、一つの困難な問題を別の困難な問題に変換することを可能にします。私たちは、最小頂点被覆(全ての辺に接続するノードの集合)がサイズ3の集合 {0, 1, 3} である5ノードグラフでこれを実証します。その被覆の補集合である {2, 4} は自動的に独立集合(ノード間に辺がないノードの集合)となり、2つのノード間に辺がないことを確認します。これはミニチュア版の還元です:一つの問題を解けば、もう一つが無料で手に入ります。

SAT(ブール充足可能性問題:ある割り当てによって、式の全ての節を真にすることができるか)は、NP完全問題(NP問題の中で最も困難なクラス。一つに高速な手法があれば、全てを高速に解ける)の代表例であり、私たちは3変数インスタンスを節 (1, -2), (2, 3), (-1, -3) で総当たりで解きます。満足する割り当ては {1: True, 2: True, 3: False} として得られ、これは8つの可能な割り当て全てをチェックすることで見つかります。3変数であれば瞬時に終わりますが、指数関数的な成長こそが本質です。

巡回セールスマン問題は私たちの継続的な例であり、平均ペアワイズ距離が9,600 kmの12空港インスタンスを構築します。モンテカルロアルゴリズムはランダムサンプリングによって推定するため、2,000のランダムなツアーを描画し、その分布を観察します:平均は115,019 km、最良のランダムツアーは75,277 kmに達します。ランダムなツアーは地理的条件をほとんど考慮しないため、平均が妥当な経路よりもはるかに高くなるのです。ラスベガスアルゴリズムはランダム性を使用しますが、常に正しい解答を返します。空港座標に対する私たちのランダム化クイックソートは、その点を証明します:出力は常にソートされていますが、実行時間のみが変動します。