問題タブ [heuristics]

スターアルゴリズムで8パズルソルバーを実行しています。このソルバーにマンハッタンと置き忘れたヒューリスティック関数を実装します。場合によっては、ソルバーは正常に機能します。しかし、場合によっては、解決策を見つけるのに多くの時間がかかります。私の問題の1つは、オープンリスト（拡張を待機中）で最も低い値を持つノードを検索する関数にあると思います。

では、最小のf_score値を見つけるための最良の方法は何ですか？最小値を見つけるか、追加する状態があるときにリストを変更する必要があります（状態を追加するときにリストを並べ替えます）。これにより、最小値が最初の位置になります。

8 つの方向のいずれかに移動できる正方形のタイルのマップがあります。隣接するタイルから別のタイルに移動するコストを示す関数が呼び出されcost(tile1, tile2)た場合、許容可能で一貫性のあるヒューリスティック関数 h(y, goal) をどのように見つけますか? costこの設定でヒューリスティックを見つける方法を一般化できますか、それとも機能 によって異なるのでしょうか?

ゲームのconnect6wikiを表現したいと思います（おそらく述語stone（P、X、Y）、ここでPはプレーヤー、X、Yは座標です）。また、問題を解決するために（対戦相手を作るために）優れたヒューリスティックを使用したいと思います。PrologのゲームAIに関する記事のヒントを教えてください。ありがとう

私は医療コンテンツ配信システムのユーザビリティ調査を行っており、ヒューリスティック評価のために CHI 論文にあるいくつかのヒューリスティックを使用することを計画していました。ただし、焦点領域が論文とはわずかに異なるため、すべてのヒューリスティックが正しいかどうかはわかりません。適用可能であり、それらをガイドラインとして使用する必要があるかどうか。

このような状況にどのように対処しますか?独自のヒューリスティックを作成するか、既存のヒューリスティックを使用してプロセスに合わせて適応させますか?

ありがとう

複数のセールスマンがいる巡回セールスマン問題に効果的に縮小された問題があります。最初の場所から訪問する都市のリストがあり、限られたセールスマンですべての都市を訪問する必要があります。

私はヒューリスティックを考え出そうとしていて、誰かが手を差し伸べることができるかどうか疑問に思っていました. たとえば、2 人のセールスマンがいる 20 の都市がある場合、私が考えたアプローチは 2 ステップ アプローチです。まず、20 の都市をランダムに 10 の都市に分割し、それぞれ 2 人のセールスマンを配置します。それぞれのツアーは、数回の反復で独立しているかのように見つけることができます。その後、都市を交換するか別のセールスマンに割り当てて、ツアーを見つけたいと思います。事実上、それは TSP であり、最小メイクスパンの問題です。これに関する問題は、遅すぎることと、都市のスワッピングまたは割り当ての適切な近隣生成が難しいことです。

上記を改善する方法について誰かアドバイスをいただけますか？ありがとう。

複数のセールスマンによる巡回セールスマン問題に事実上縮小された問題があります。最初の場所から訪問する都市のリストがあり、限られた数のセールスマンですべての都市を訪問する必要があります。

私はヒューリスティックを考え出そうとしていて、誰かが手を差し伸べることができるかどうか疑問に思っていました. たとえば、2 人のセールスマンがいる 20 の都市がある場合、私が考えたアプローチは 2 ステップ アプローチです。まず、20 都市をランダムに 10 都市に分割し、それぞれ 2 人のセールスマンを割り当てます。数回繰り返して、それぞれのツアーが独立しているかのように見つけます。その後、都市を交換するか別のセールスマンに割り当てて、ツアーを見つけたいと思います。事実上、それは TSP であり、最小メイクスパンの問題です。これに伴う問題は、遅すぎることと、都市のスワッピングや割り当ての適切な近隣生成が難しいことです。

上記を改善する方法について誰かアドバイスをいただけますか？

編集：

各都市の地理的位置は既知であり、セールスマンは同じ場所で開始および終了します。目標は、最大移動時間を最小化することであり、この種の最小 makespan 問題を作成します。たとえば、salesman1 が 10 時間、salesman2 が 20 時間かかる場合、最大移動時間は 20 時間になります。

私は現実世界の問題を次の質問に抽象化しています。

• Xは、文字のすべての可能な順列のプールです。
• Yは文字列のプールです。
• Fは、Xから候補xを取得し、xがYに属するかどうかに応じてブール値を返す関数です。

Fは高価で、Xは巨大です。Yからできるだけ多くの結果を抽出するための最も効率的な方法は何ですか？誤検知は問題ありません。

概要

翻訳文を (元の言語から翻訳された言語に) 一致させるためのヒューリスティックを設計しようとしていますが、ガイダンスとヒントが必要です。おそらく、すでに似たようなことをしているヒューリスティックがありますか? したがって、2 つのテキスト ファイルが与えられた場合、文を照合できるようにしたいと考えています (したがって、文を選択して、これがその文の翻訳であると言うことができます)。

詳細

入力テキストは翻訳された小説になります。したがって、翻訳が文字通りであるとは思いませんが、ヒューリスティックの精度をテストするには、 Google 翻訳などを使用するのが良い方法かもしれません。

私を助けるために、私は翻訳されたテキストの内容を詳しく説明し、文中の単語の定義を提供するライブラリを持っています. 私が知っている他のこと：

• 章と順序は保持されます。私は、第 3 章の最初の文が翻訳の第 3 章の最初の文と一致することを知っています (注意、これは厳密には正しくありません。最初の文は最初の 2 つの文、または 2 番目の文と一致する場合もあります)。
• 全体のサイズ (文字、文、段落) を計算できます。これにより、文のサイズの平均的な違いを知ることができます (たとえば、翻訳は 30% 長くなる可能性があります)。

私が持っているいくつかの本を見てみると、翻訳版は原文よりも約 30% 文章が多くなっています。

実装

（それが重要な場合）

• 私は Java でこれを行うことを計画していますが、それほど大騒ぎしているわけではありません。どの言語でも構いません。
• 速度はあまり気にしません。

確実に一致させるために、ユーザーからのフィードバックが必要になる場合があります。「はい、この文は間違いなくその文と一致します」と言うようなものです。これにより、ヒューリスティックに立つための根拠がいくらか与えられます。これは、ユーザーが言語に多少習熟している必要があることを意味します。

バックグラウンド

（興味のある方）

これを作りたい理由は、外国語の勉強に役立てたいからです。私は日本語を勉強していますが、「良い」素材を見つけるのが難しいと感じています (「良い」とは、好きなものによって定義されます)。ビデオの字幕で同様のことを行うためのツールが既にあります (ビデオのタイミング情報を使用すると、より簡単な作業になります)。しかし、私の知る限り、テキストについては何もありません。

それぞれ値が 1<=X<=10^6 の N 個の整数を含むセット S があります。問題は、セット S を k 個のパーティションに分割することです。パーティションの値は、そこに存在する要素の合計です。分割は、セット S の合計値が k 個の分割に均等に分配されるように行われます。公正さの数学的意味も定義する必要があります (たとえば、目的は、集合 S の平均値からのパーティションの値の標準偏差 (つまり、sum(S)/k) を最小化することである可能性があります)。

例: S = {10, 15, 12, 13, 30, 5}, k=3

適切なパーティショニングは、{30}、{10, 15}、{12, 13, 5} です。

不適切なパーティショニングは {30, 5}、{10, 15}、{12, 13} です。

最初の質問は、あるパーティションが他のパーティションよりも優れている条件を数学的に表現することです。2番目の質問は、問題を解決する方法です。問題は NP-Hard です。ヒューリスティックはありますか？

N <= (k*logX)^2 を解決しようとしている問題で、K は 2 から 7 まで変化します。

================================================== ================================

他の関連する SO の質問に基づいて、分布を評価するための 2 つの合理的な関数があります。

a) 最大値を持つパーティションの値を最小化します。

よく考えてみると、これは良い指標ではありません。セット {100, 40, 40} を 3 つのサブセットに分割するとします。このメトリックは、次の 2 つの分布を区別しませんが、一方が他方よりも明らかに優れています。

分布 1: {100}、{40}、{40} および分布 2: {100}、{40、40}、{}

b) 特定のパーティション内の任意の 2 つの値の差の最大値を最小化します。つまり、max|AB| を最小化します。任意の A、B