問題タブ [heuristics]

http://lab.arc90.com/experiments/readability/は、雑然とした新聞、雑誌、ブログのページを非常に読みやすい方法で表示するための非常に便利なツールです。これは、いくつかのヒューリスティックを使用して、Web ページの関連するメイン テキストを見つけることによって行われます。そのソース コードは、http://lab.arc90.com/experiments/readability/js/readability.jsでも入手できます。

jQuery を使用して新聞の「本文」を取得するのに苦労していたとき、私の同僚の何人かがこれに注意を向けました。ジャーナル | ブログ | 等のウェブサイト。私の現在のヒューリスティック (および jQuery での実装) は、次のようなものを使用します (これは Firefox Jetpack パッケージ内で行われます)。

つまり、「DIV 内の段落を取得して、'script' などの無関係な文字列をチェックする」のようなものです。私はこれを試してみましたが、ほとんどの場合、Web 記事の本文を取得できますが、より優れたヒューリスティックまたはより優れた jQuery 選択メカニズム (およびさらに短い?) が必要です。

より良い提案はありますか？

PS: たぶん、「最も内側の DIV (つまり、DIV タイプの子要素がない) を見つけて、その DIV を取得します。

s only" は、現在の目的にはより良いヒューリスティックですが、jQuery でこれを表現する方法を見つけることができませんでした。

ユーザー名/パスワードのテキスト入力フィールドがある Web サイトの場合、通常、ブラウザーは簡単にそれらを記憶してくれます (私の場合、Safari はそれらを OS X キーチェーンに入れます)。

これは、特定の Web サイトでは発生しません。頭に浮かぶ最初の例は、vBulletin フォーラムです。つまり、毎回どこかからコピーして貼り付けることを望まない限り、複雑な/ランダムなパスワードを使用することはできません.

ブラウザは、「これはユーザー名/パスワードのように見えますか」というヒューリスティックによって、いつこれらを記憶することを提案するかを検出し、時々失敗しますか?

これは舞台裏でどのように機能しますか?

編集：仲間のSafariユーザーは、このコンボをチェックしてください：

http://8-p.info/greasekit/

http://userscripts.org/scripts/show/8021

http://userscripts.org/scripts/show/28696

とにかく、最小数のヒューリスティックが幅優先検索以外で満たされることを保証する方法はありますか? おそらく、もう少し説明が役立つでしょう。

次のようなランダムなグラフがあります。

左上隅から始めて、右下隅に到達するのに必要な最小ステップ数を知る必要があります。接続された色の各セットは 1 つのノードであると想定されるため、たとえば、このランダム グラフでは、一番上の行にある 3 つの 1 はすべて 1 つのノードと見なされ、隣接する (対角線ではない) 接続されたすべてのノードが可能な次の状態になります。したがって、最初から考えられる次の状態は、一番上の行の 1 または 2 番目の行の 3 です。

現在、私は双方向検索を使用していますが、ツリー サイズの爆発性はかなり急速に上昇しています。私の人生では、問題を調整してノードに安全に重みを割り当て、幅優先検索にならずに目標に到達するための状態変化の数を最小限に抑えることができませんでした。これを街の地図と考えると、ヒューリスティックは目標に到達するまでの最小ターン数になります。

より複雑な問題のヒューリスティックの一部であるため、この検索の結果が最小のターン数であることが非常に重要です。

NP困難/NP完全であるいくつかのスケジューリング問題があることを私は知っています...しかし、それらのどれもこの状況がNPでもあることを示すような方法で述べられていません。

startAfter、startBy、durationに制約された一連のタスクがあり、すべてが単一のリソースを使用しようとしている場合...スケジュールを解決するか、徹底的な検索なしでは解決できないことを特定できますか？

答えが「申し訳ありませんが、これはNP完全です」の場合、使用するのに最適なヒューリスティックは何でしょうか。また、a）スケジュールを解決し、b）解決できないものを特定するのにかかる時間を短縮する方法はありますか。スケジュール。

「最小ウィンドウファースト」ヒューリスティックを実装する再帰を通じて、基本的な競合解決の目標を（プロローグで）実装しました。これは実際にはかなり迅速に解決策を見つけますが、無効なスケジュールを見つけるのは非常に遅いです。これを克服する方法はありますか？

複雑な質問にイェーイ！

これがぼんやりとした質問のように思われる場合は申し訳ありませんが、それはしばらくの間私を悩ませてきたものです。

私の日常の仕事では、私が書くコードのいくつかはかなり複雑になります。通常は非常に技術的であるというわけではありませんが、問題のドメイン自体は、とりわけ空間データを扱う複雑な問題です。私のNDAは、私が取り組んでいることの詳細を提供することを禁じていると確信しているので、残念ながら、これはかなり一般的なものにしておく必要があります。

今、私はすべて複雑さを軽減するために、できる限り適切な抽象化を見つけようとしますが、手元にある実際の問題を明示的に処理するのではなく、操作できるメタファーを明示的に処理することによって、さらに複雑さを軽減する方法はありますか？後で欲しい実際の結果に変換しますか？

もちろん、この領域自体は非常に複雑なので、正しいメタファーを見つけようとしましたが、失敗しました（何度も！）:-(

だから私の質問は、誰かがすでにこの作業を行い、与えられたプログラミング問題のセットに対して適切なメタファーまたはヒューリスティックを推定するための構造化された方法を見つけましたか（または半分見つけましたか）？

繰り返しになりますが、これが少し奇妙な質問のように思われる場合は、お詫び申し上げます。私はただ、より良いプログラマーになるための新しい方法を見つけようとしています。

前もって感謝します。

私は巡回セールスマン問題全体とスタックオーバーフローに慣れていないので、正しくないことを言ったら教えてください。

イントロ：

複数の国（エリア）内の複数の都市（ノード）が関与するゲームの利益/時間最適化マルチトレードアルゴリズムをコーディングしようとしています。ここで、

• 接続された2つの都市間を移動するのにかかる物理的な時間は常に同じです。
• 都市は直線的に接続されていません（同時にいくつかの都市間でテレポートできます）。
• 一部の国（地域）には、他の国を経由する最短経路を利用できるテレポートルートがあります。
• 旅行者（またはトレーダー）は、小銭入れ、商品の重量、および特定の交易路で取引できる数量に制限があります。交易路は複数の都市にまたがることができます。

質問パラメータ：

メモリ内にデータベース（python：sqlite）がすでに存在し、ソース都市と宛先都市、配列と金額としての中間の最短パス都市、および総資本に対する％リターン（またはいずれの要因も制限されていない場合は、総資本に対して最大の利益をもたらす方法だけです）。

• 特定のプリセット時間（つまり30分）に対して最適な利益を見つけようとしています
• 新しい都市に渡るという行為は実際には同時です
• 通常、都市地図を移動するのに同じ定義された時間（つまり2分）かかります
• 最初の取引または新しい取引を開始する行為は、1つの都市地図を横断するのと同じ時間（つまり2分）かかります
• 私の出発点は実際には有効な取引がない可能性があります（最初/最も近い/最良のものに移動する必要があります）

これまでの疑似ソリューション

最適化

まず、所要時間に制限があり、各ホップにかかる時間（トレードを開始するための-1を含む）がわかっているため、ホップが。以下のすべてのトレードにグラフを制限できることに気付きましたmax_hops=int(max_time/route_time) -1。この制限時間内に収まらない貿易データベースの要素を切り取り、最短経路の長さが。より大きい都市を剪定しますmax_hops。

私は、現在の都市と、現在の都市ではないすべての既存の取引の開始都市との間の最短経路を含む取引データベースに別のエントリを作成し、それらに0％のリターンを与えます。これらをシティホップの数が、未満の場所に制限します。max_hopsまた、現在の都市から開始都市に加えて最短パスホップを取引する都市が超過するかどうかを計算し、max_hopsこの制限を超えた都市を削除します。

次に、そうでない残りの取引を(current_city->starting_city)取得し、ホップが超過しないすべての目的地と開始都市の間で0％のリターンで取引ルートを追加しますmax_hops

次に、取引データベースに開始都市、目的地都市、または最短経路都市配列の一部として含まれていないすべての都市について、最後の整理を行います。

グラフ検索 制限時間内（つまり30分）に実行可能な取引の（はるかに）小さいグラフが残ります。

接続されているすべてのノードが隣接しているため、接続はデフォルトですべて加重1になります。％returnをトレードのホップ数で割ってから、逆数を取り、+ 1を加算します（これは、 100％帰路）。リターンが0％の場合は…2？

その後、最も収益性の高いルートを返す必要があります...

質問：

多くの場合、

1. お金やスペースを残したときに複数のルートを取る機能を追加して、単一の貿易ルートに個別のパスを介してルートを検索し続けるにはどうすればよいですか？市内で複数の価格と数量で販売されている商品の性質上、重複するルートが多数あります。

2. 新しい交易路の開始にペナルティを課すにはどうすればよいですか？

3. この状況でグラフ検索はさらに役立ちますか？

ちなみに、

3. グラフに対してどのような種類の整理/最適化を行う必要がありますか（または行わないでください）？
4. 私の重み付け方法は正しいですか？私はそれが私に不釣り合いな重みを与えるだろうと感じています。パーセンテージリターンの代わりに実際のリターンを使用する必要がありますか？
5. Pythonでコーディングしている場合、 python-graphなどのライブラリは私のニーズに適していますか？それとも、特殊な関数を作成するためのオーバーヘッドを大幅に節約できますか（私が理解しているように、グラフ検索アルゴリズムは計算量が多くなる可能性があります）。
6. A *検索を使用するのが最善ですか？
7. トレードデータベースの最短経路ポイントを事前に計算して最適化を最大化する必要がありますか、それともすべてをグラフ検索に任せる必要がありますか？
8. 私が改善できることは何か気づきましたか？

ヒューリスティックとアルゴリズムの違いは何ですか?

これはhttp://cssfingerprint.com用です

私はシステムを持っています (詳細については、サイトのページについてを参照してください)。

• 特定の特徴ベクトルに一致するカテゴリのランク付けされたリストを自信を持って出力する必要があります
• バイナリ特徴ベクトルは、サイト ID のリストと、このセッションがヒットを検出したかどうかです
• 特徴ベクトルは、特定の分類に対して、多少のノイズがあります (サイトは履歴から減衰し、人々は通常アクセスしないサイトにアクセスします)。
• カテゴリは、閉じていない大規模なセット (ユーザー ID) です。
• 私の総機能スペースは約 5,000 万項目 (URL) です
• 特定のテストでは、約のみをクエリできます。そのスペースの 0.2%
• これまでの結果に基づいて、何をクエリするかを決定できるのは最大 10 ～ 30 回であり、それを最大 100 ミリ秒以内に行う必要があります (ただし、後処理や関連する集計などを行うには、はるかに長い時間がかかる場合があります)。
• これまでの結果に基づいて、カテゴリの AI の確率ランキングを取得するには、ややコストがかかります。理想的には、決定は主にいくつかの安価なSQLクエリに依存します
• 任意の 2 つの特徴ベクトルが同じカテゴリであるが、異なるとは言えないことを信頼できるトレーニング データがあります (コードを忘れて新しいものを使用することで、新しいユーザー ID が作成されることがあります)。

どの機能 (サイト) がクエリに対して高い ROI を持つ可能性が最も高いかを判断するアルゴリズムが必要です (つまり、これまでのところもっともらしいカテゴリ [ユーザー] をより適切に識別し、それが特定のカテゴリであるという確実性を高めるため)。

これには、活用 (以前のテスト データに基づくテスト) と探索 (どのように機能するかを調べるには十分にテストされていないものをテストする) のバランスを取る必要があります。

アプリオリなランキングを扱う別の質問があります。これは特に、これまでに収集された結果に基づく事後ランキングに関するものです。

現時点では、他の誰かがこれまでにヒットしたすべてのものを常にテストできるほど十分なデータがありませんが、最終的にはそうではなくなり、その時点でこの問題を解決する必要があります.

これは、AI ではかなり標準的な問題であると思います。作成するコストの高いクエリに対して安価なヒューリスティックを使用しますが、AI クラスではカバーされていないため、標準的な答えがあるかどうかは実際にはわかりません。そのため、数学が多すぎない関連する読み物や、特定のアルゴリズムの提案が役立ちます。

この問題にアプローチする良い方法は何ですか?

私は、長さが異なるタスクを実行するワーカースレッドが多数あるマルチスレッドプログラムに取り組んでいます。タスクがほぼ同じ量の作業を行うように、タスクの負荷を分散したいと考えています。各タスク T _iには 、そのタスクに必要な作業量の適切な近似値を提供する 数値 c _{iがあります。}

_{私は効率的な (O(N) N = タスク数以上) アルゴリズムを探しています。これは、 c i}の値が与えられた場合に「おおよそ」適切な負荷バランスを提供します。最適である必要はありませんが、結果として得られる割り当てがどれほど悪いかについて、理論的な境界を設定できるようにしたいと考えています。

何か案は？