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

ポスト8では、問題を解ける形に変える最適化ツールキットを構築し、勾配と凸性が良い答えへの道筋をどのように与えてくれるかを学びました。今、私たちはより困難な真実に直面しています。それは、私たちが知っているどんな巧妙なトリックにも抵抗する問題があり、それに対して唯一誠実な対応は、その問題がどれほど困難であるかを正確に理解し、確実性を速度と交換する手法に手を伸ばすことです。この記事の終わりまでには、12空港の巡回セールスマン問題（すべての空港を一度ずつ訪問する最短の往復経路を見つける問題）を正確に62,741 kmで解決し、その後、3つの異なるヒューリスティック（速度のために保証された最適性を犠牲にする近似手法）が様々な成功度でその数値を追いかけるのを見て、それらの間のギャップが失敗ではなく困難な問題の本質そのものであることを理解するでしょう。 OpenFlightsデータセットは、約7,700の空港と67,000のルートを約2MBのCSVファイルで提供してくれます。私たちはルートからグラフを構築し、空港間の大圏距離を計算し、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です。ランダムなツアーは地理をほとんど尊重しないため、平均は sensible な経路よりもはるかに高くなります。ラスベガスアルゴリズムはランダム性を使用しますが、常に正しい答えを返します。空港座標に対するランダム化クイックソートは、その点を証明します。出力は常にソートされていますが、実行時間のみが変動します。 世界の航空ネットワークにおけるグラフアルゴリズム ポスト6では、表形式のデータを一貫した物語を語るまでクリーンアップする方法を学びました。この記事では、その同じ規律を取り、異なる種類の構造に適用します。それは、世界の航空ネットワークの有向加重グラフです。私たちは生のOpenFlightsデータからグラフを構築し、その後、サブ問題、文字列、および検索トリックをポスト6では、再帰と分割統治法を第一原理から構築し、問題を独立した半分に分割し、答えを組み合わせる方法を学びました。この記事では、それらのツールを取り、より困難なクラスの問題に向けます。それは、サブ問題が重複し、文字列がきれいに分割されない問題です。ソート、ハッシュ、およびスケッチを370,103語でポスト2では、Pythonのリスト、辞書、セット、および再帰で基盤を構築し、言語のコアコンテナが負荷の下でどのように動作するかを学びました。今、私たちはそれらのツールを実際のデータセットで試します。それは、dwyl/english-wordsから抽出された、1行に1単語の370,103の英語の単語です。情報理論を一気読みポスト3と4では、確率的基盤を構築し、ベイズの定理で信念を更新する方法を学びました。今、私たちはその仕組みを具体的な質問に適用します。それは、テキストの断片に実際にどれだけの情報が含まれているか、ということです。この記事では、WikiText-2でその量を測定します。