ある単語を別の単語に変換するための最短パス
https://stackoverflow.com/questions/1521958
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
データ構造プロジェクトの場合、2つの単語の間の最短パスを見つける必要があります（ "cat" と "dog"）、一度に1文字のみを変更します。パスを見つける際に使用するスクラブルワードリストが与えられます。例えば：
cat -> bat -> bet -> bot -> bog -> dog
私は幅の最初の検索を使用して問題を解決しましたが、より良いものを探しています（私は辞書をTrieで表しました）。
より効率的な方法（速度とメモリの観点から）のアイデアを教えてください。とんでもないや挑戦的な何かが好まれます。
私は私の友人の一人に尋ねました（彼は後輩です）、彼はあると言いました 番号 この問題に対する効率的な解決策。彼は、私がアルゴリズムコースを受講したときになぜ学ぶと言った。それについてのコメントはありますか？
私たちは言葉から言葉に移動する必要があります。行けない cat -> dat -> dag -> dog. 。また、トラバーサルを印刷する必要があります。
解決
新しい答え
最近の更新を考えると、ハミング距離をヒューリスティックとして試してみることができます。それは距離を過大評価することはないので、それは許容されるヒューリスティックです
古い答え
計算に使用される動的プログラムを変更できます levenshtein距離 一連の操作を取得します。
編集：文字列の数が一定の場合、問題は多項式時間で解決可能です。そうでなければ、それはNPハードです（ウィキペディアにはすべてです）..あなたの友人が問題がNPハードであることについて話していると仮定します。
編集：文字列の長さが等しい場合は、使用できます ハミング距離.
他のヒント
辞書では、BFSは最適ですが、必要な実行時間はそのサイズ（V+E）に比例します。 n文字を使用すると、辞書には全体があり、Aはアルファベットサイズです。辞書にはすべての単語が含まれている場合、チェーンの終わりにある必要がある単語は、すべての可能な単語を横断しますが、何も見つかりません。これはグラフトラバーサルですが、サイズは指数関数的に大きい場合があります。
あなたはそれをより速くすることが可能かどうか疑問に思うかもしれません - 構造を「インテリジェントに」閲覧し、多項式時間にそれを行うことです。答えは、いいえだと思います。
問題：
単語が辞書にあるかどうかを確認するための高速（線形）方法が与えられています。1 - > a2 - > ... - > an - > v。
NPハードです。
証明：3SATインスタンスを次のようにしてください
（pまたはqまたはr）および（pまたはqまたはr）
0 000 00から始めて、2 222 22に移動できるかどうかを確認します。
最初のキャラクターは「私たちが終了した」ということです。3つの次のビットはP、Q、R、および次の2つを制御します。
許可された言葉は次のとおりです。
- 0から始まり、0から1つだけを含むものはすべて
- 2から始まり、合法的なものは何でも。つまり、0と1で構成されていることを意味します（最初の文字が2であることを除き、すべての条項ビットは変数ビットに従って正当に設定され、1に設定されています（これは、式が満足できることを示しています）。
- 少なくとも2つの2から始まり、その後0と1で構成されます（正規表現：222*（0+1）*、22221101のようには2212001ではありません
0 000 00から2 222 22を生成するには、このようにして行う必要があります。
（1）適切なビットをひっくり返す-4つのステップで0 100 111。これには、3SATソリューションを見つける必要があります。
（2）最初のビットを2：2 100111に変更します。ここで、これは実際に3SATソリューションであることが確認されます。
（3）変更2 100 111-> 2 200 111-> 2 220 111-> 2 222 111-> 2 222 211-> 2 222 221-> 2 222 222。
これらのルールは、チートできないことを強制します（チェック）。 2 222 22に移動することは、式が満たされている場合にのみ可能であり、NPハードであることを確認します。私はそれがさらに難しいかもしれないと感じています（おそらく#PまたはFNP）が、その目的のためにNP-Hardnessで十分です。
編集: ：あなたは興味があるかもしれません Dijoint Setデータ構造. 。これにより、お互いに到達できる辞書とグループの単語が表示されます。すべての頂点からルートまたは他の頂点へのパスを保存することもできます。これにより、最短の道ではなく、パスが得られます。
効率が変化する方法があります 発見 リンク - 単語の長さごとに完全なグラフを作成するか、 Bk-Tree, 、たとえば、あなたの友人は正しいです - BFSは最も効率的なアルゴリズムです。
ただし、ランタイムを大幅に改善する方法があります。ソースノードから単一のBFSを実行する代わりに、グラフの両端から開始し、フロンティアセットに共通ノードを見つけたときに終了すると、2つの幅の最初の検索を行います。 。あなたがしなければならない仕事の量は、一方の端だけから検索する場合に必要なものの約半分です。
最初に適切な長さではない単語を削除することで、少し速くすることができます。限られた辞書の多くは、CPUのキャッシュに収まります。おそらくすべて。
また、すべてのSTRNCMP比較（すべての小文字を作成したと仮定すると）は、MEMCMP比較、またはスピードアップになる可能性のある展開された比較でさえあります。
プリプロセッサの魔法を使用して、その単語の長さのタスクをハードコンパイルするか、一般的な単語の長さについてタスクの最適化されたバリエーションをいくつかロールすることができます。これらの余分な比較はすべて、純粋な展開された楽しみのために「去る」ことができます。
これは典型的なものです 動的プログラミング 問題。編集距離の問題を確認してください。
あなたが探しているものは編集距離と呼ばれます。さまざまなタイプがあります。
から （http://en.wikipedia.org/wiki/edit_distance）：「情報理論とコンピューターサイエンスでは、文字の2つの文字列間の編集距離は、1つの文字を他方に変換するために必要な操作の数です。」
Jazzy（The Java Spell Check API）に関するこの記事には、これらの種類の比較の概要があります（同様の問題です - 推奨される修正を提供します） http://www.ibm.com/developerworks/java/library/j-jazzy/
最も一般的なサブシーケンスを見つけることができ、したがって、変更する必要がある文字を見つけることができます。
私の直感は、あなたの友人がより効率的な解決策がないという点で正しいということですが、それはあなたが毎回辞書をリロードしていると仮定しています。一般的な遷移の実行中のデータベースを保持する場合、確かにソリューションを見つけるためのより効率的な方法がありますが、事前に遷移を生成し、どの遷移が役立つかを発見する必要があります（生成できないためそれらはすべて！）おそらく独自の芸術です。
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;
};
//最短チェーンの長さを返して、「start」から「ターゲット」に到達します//隣接する動きの最小数を使用します。 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-lenty-of-shortest-chain-to-reach-a-target-word/
