22

データ構造プロジェクトの場合、一度に1文字だけ変更して、 2つの単語（"cat"となど）の間の最短経路を見つける必要があります。"dog"パスを見つけるために使用するスクラブルの単語リストが提供されます。例えば：

cat -> bat -> bet -> bot -> bog -> dog

幅優先探索を使用して問題を解決しましたが、より良いものを探しています（辞書をトライで表現しました）。

より効率的な方法（速度とメモリの観点から）についていくつかアイデアを教えてください。ばかげているおよび/または挑戦的な何かが好ましい。

私は友人の一人（彼は後輩です）に尋ねました、そして彼はこの問題に対する効率的な解決策はないと言いました。彼は、私がアルゴリズムのコースを受講したときに、その理由を学ぶと言いました。それについて何かコメントはありますか？

私たちは言葉から言葉へと移動しなければなりません。行くことはできませんcat -> dat -> dag -> dog。トラバーサルも印刷する必要があります。

4

9 に答える 9

16

新しい答え

最近の更新を考えると、ヒューリスティックとしてハミング距離を使用してA*を試すことができます。距離を過大評価することはないので、許容できるヒューリスティックです

古い答え

レーベンシュタイン距離の計算に使用される動的計画法を変更して、一連の操作を取得できます。

編集：文字列の数が一定の場合、問題は多項式時間で解決できます。そうでなければ、それはNP困難です（それはすべてウィキペディアにあります）..あなたの友人がNP困難であるという問題について話していると仮定します。

編集：文字列の長さが等しい場合は、ハミング距離を使用できます。

于 2009-10-05T19:36:20.663 に答える
9

辞書の場合、BFSが最適ですが、必要な実行時間はそのサイズ（V + E）に比例します。n文字の場合、辞書の全体が〜a ^ nになる可能性があります。ここで、aはアルファベットサイズです。辞書にチェーンの最後にあるはずの単語以外のすべての単語が含まれている場合は、考えられるすべての単語をトラバースしますが、何も見つかりません。これはグラフ走査ですが、サイズが指数関数的に大きくなる可能性があります。

構造を「インテリジェントに」参照して多項式時間で実行することで、より高速に実行できるかどうか疑問に思われるかもしれません。答えは、私が思うに、いいえです。

問題：

単語が辞書にあるかどうかをチェックする高速（線形）方法が与えられます。2つの単語u、vであり、シーケンスu-> a 1-> a 2-> ...->anがあるかどうかをチェックします。->v。

NP困難です。

証明：次のような3SATインスタンスを取得します

（pまたはqまたはrではない）および（pまたはqまたはrではない）

0 000 00から始めて、222222に進むことができるかどうかを確認します。

最初の文字は「終了しました」で、次の3つのビットがp、q、rを制御し、次の2つのビットが句を制御します。

許可される単語は次のとおりです。

  • 0で始まり、0と1のみを含むもの
  • 2で始まり、合法であるもの。これは、0と1で構成されていることを意味します（最初の文字が2であることを除いて、すべての句ビットは変数ビットに従って正しく設定され、1に設定されます（したがって、これは式が満足できることを示します）。
  • 少なくとも2つの2で始まり、0と1で構成されるもの（正規表現：222 *（0 + 1）*、22221101のように、2212001ではない

0000000から222222を生成するには、次のようにする必要があります。

（1）適切なビットを反転します（例：0 100 111）。これには、3SATソリューションを見つける必要があります。

（2）最初のビットを2：2 100 111に変更します。ここで、これが実際に3SATソリューションであることが確認されます。

（3）変更2100111-> 2200111-> 2220111-> 2222111-> 2222211->2222221-2222222。

これらのルールは、チート（チェック）できないことを強制します。2 222 22に進むことができるのは、式が満足できる場合のみであり、それがNP困難であることを確認する必要があります。それはさらに難しいかもしれないと思いますが（おそらく#PまたはFNP）、その目的にはNP困難で十分だと思います。

編集：互いに素なセットのデータ構造に興味があるかもしれません。これはあなたの辞書とお互いから到達できるグループの単語を取ります。すべての頂点からルートまたは他の頂点へのパスを保存することもできます。これにより、必ずしも最短のパスではなく、パスが提供されます。

于 2009-10-05T21:04:20.517 に答える
3

リンクを見つけるための効率を変える方法があります-たとえば、単語の長さごとに完全なグラフを作成したり、BK-Treeを作成したりできますが、友だちは正しいです-BFSが最も効率的なアルゴリズムです。

ただし、ランタイムを大幅に改善する方法があります。ソースノードから単一のBFSを実行する代わりに、グラフの両端から開始し、フロンティアセットで共通ノードを見つけたときに終了する2つの幅優先探索を実行します。 。あなたがしなければならない仕事の量は、片方の端だけから検索する場合に必要な量の約半分です。

于 2009-10-05T20:38:14.250 に答える
2

最初に、適切な長さではない単語を削除することで、少し速くすることができます。制限された辞書の多くは、CPUのキャッシュに収まります。おそらくすべて。

また、すべてのstrncmp比較（すべてを小文字にしたと仮定）は、memcmp比較、または展開された比較でさえあり、これはスピードアップになる可能性があります。

プリプロセッサの魔法を使ってその単語の長さのタスクをハードコンパイルするか、一般的な単語の長さのタスクのいくつかの最適化されたバリエーションをロールすることができます。これらの余分な比較はすべて、純粋に展開された楽しみのために「消え去る」ことができます。

于 2012-06-15T05:35:08.453 に答える
1

あなたが探しているのは編集距離と呼ばれています。多くの異なるタイプがあります。

From（http://en.wikipedia.org/wiki/Edit_distance）：「情報理論とコンピュータサイエンスでは、2つの文字列間の編集距離は、一方を他方に変換するために必要な操作の数です。」

Jazzy（JavaスペルチェックAPI）に関するこの記事には、これらの種類の比較の概要が記載されています（これは、同様の問題です。修正案を提供します）http://www.ibm.com/developerworks/java/library/j-jazzy/

于 2009-10-06T05:09:29.733 に答える
1

これは典型的な動的計画問題です。距離の編集の問題を確認します。

于 2009-10-05T19:40:20.170 に答える
0

最長共通部分列を見つけることができるため、変更する必要のある文字を見つけることができます。

于 2009-10-05T19:35:30.620 に答える
0

私の直感では、より効率的な解決策はないという点で、あなたの友人は正しいと思いますが、それはあなたが毎回辞書をリロードしていることを前提としています。一般的な遷移の実行中のデータベースを保持する場合は、解決策を見つけるためのより効率的な方法が確かにありますが、事前に遷移を生成し、どの遷移が役立つかを見つける必要があります（生成できないため）それらすべて！）はおそらくそれ自身の芸術です。

于 2009-10-05T19:42:14.567 に答える
0 
bool isadjacent(string& a, string& b)
{
  int count = 0;  // to store count of differences
  int n = a.length();

  // Iterate through all characters and return false
  // if there are more than one mismatching characters
  for (int i = 0; i < n; i++)
  {
    if (a[i] != b[i]) count++;
    if (count > 1) return false;
  }
  return count == 1 ? true : false;
}

//単語を格納するキューアイテムと//単語に到達するための最小チェーン長。

struct QItem
{
  string word;
  int len;
};

//隣接する移動の最小数を使用して「開始」から「ターゲット」に到達するための最短チェーンの長さを//返します。Dは辞書です

int shortestChainLen(string& start, string& target, set<string> &D)
{
  // Create a queue for BFS and insert 'start' as source vertex
  queue<QItem> Q;
  QItem item = {start, 1};  // Chain length for start word is 1
  Q.push(item);

  // While queue is not empty
  while (!Q.empty())
  {
    // Take the front word
    QItem curr = Q.front();
    Q.pop();

    // Go through all words of dictionary
    for (set<string>::iterator it = D.begin(); it != D.end(); it++)
    {
        // Process a dictionary word if it is adjacent to current
        // word (or vertex) of BFS
        string temp = *it;
        if (isadjacent(curr.word, temp))
        {
            // Add the dictionary word to Q
            item.word = temp;
            item.len = curr.len + 1;
            Q.push(item);

            // Remove from dictionary so that this word is not
            // processed again.  This is like marking visited
            D.erase(temp);

            // If we reached target
            if (temp == target)
              return item.len;
        }
    }
  }
  return 0;
}

// Driver program
int main()
{
  // make dictionary
  set<string> D;
  D.insert("poon");
  D.insert("plee");
  D.insert("same");
  D.insert("poie");
  D.insert("plie");
  D.insert("poin");
  D.insert("plea");
  string start = "toon";
  string target = "plea";
  cout << "Length of shortest chain is: "
       << shortestChainLen(start, target, D); 
  return 0; 
}

コピー元：https ：//www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/

于 2018-05-13T20:12:09.717 に答える