أقصر طريق لتحويل كلمة واحدة إلى أخرى

Question

لمشروع هياكل البيانات، يجب أن أجد أقصر مسار بين كلمتين (مثل "cat" و "dog")، تغيير حرف واحد فقط في وقت واحد. نحن نحصل على قائمة كلمات الخربشة للاستخدام في العثور على طريقنا. علي سبيل المثال:

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

لقد قمت بحل المشكلة باستخدام عملية البحث الأولى، لكنني أبحث عن شيء أفضل (أمثل القاموس مع ثلاثي).

من فضلك أعطني بعض الأفكار لطريقة أكثر كفاءة (من حيث السرعة والذاكرة). شيء مثير للسخرية و / أو التحدي هو المفضل.

سألت أحد أصدقائي (إنه صغار) وقال إنه هناك رقم حل فعال لهذه المشكلة. قال إنني سأتعلم لماذا أخذت دورة الخوارزميات. أي تعليقات على ذلك؟

يجب أن ننتقل من كلمة إلى Word. لا نستطيع الذهاب cat -> dat -> dag -> dog. وبعد علينا أيضا طباعة اجتياز.

Answer 1

إجابة جديدة

بالنظر إلى التحديث الأخير، يمكنك تجربة * مع مسافة Hamming كإرامية. إنه مزعج مقبول لأنه لن يفدد في تقدير المسافة

الإجابة القديمة

يمكنك تعديل البرنامج الديناميكي المستخدم لحساب Levenshtein المسافة للحصول على تسلسل العمليات.

تحرير: إذا كان هناك عدد ثابت من السلاسل، فإن المشكلة قابلة للحل في وقت متعدد الحدود. آخر، إنه NP-Hard (كل شيء هناك في ويكيبيديا) .. على افتراض أن صديقك يتحدث عن المشكلة التي يجريها NP-Hard.

تحرير: إذا كانت سلاسلك متساوية الطول، فيمكنك استخدامها hamming المسافة.

Answer 2

مع وجود قاموس، BFS هو الأمثل، ولكن وقت التشغيل اللازم يتناسب مع حجمه (V + E). مع رسائل N، قد يكون لدى القاموس ~ ^ n يستهلك، حيث يكون حجم الأبجدية. إذا كان القاموس يحتوي على كل الكلمات ولكن الشخص الذي يجب أن يكون في نهاية السلسلة، فسوف يعبر كل الكلمات الممكنة ولكن لن يجد أي شيء. هذا هو اجمل رسم بياني، ولكن الحجم قد يكون كبيرا كبيرا.

قد تتساءل عما إذا كان من الممكن القيام بذلك بشكل أسرع - لتصفح هيكل "بذكاء" وتفعل ذلك في وقت متعدد الحدود. الجواب هو، أعتقد، لا.

المشكلة:

أنت تعطى وسيلة سريعة (خطية) للتحقق مما إذا كانت الكلمة في القاموس، وكلمتين يو، v، هي التحقق مما إذا كان هناك تسلسل U ->₁ -> أ₂ -> ... ->_ن -> v.

هو np-hard.

إثبات: خذ بعض مثيل 3SAT، مثل

(ص أو س أم لا ص) و (ص أم لا q أو r)

ستبدأ مع 0 000 00 وتتأكد مما إذا كان من الممكن الذهاب إلى 2 222 22.

ستكون الشخصية الأولى "هل انتهينا"، ستتحكم ثلاث بتات القادم في P و Q و R واثنين من القادمين ستحكم في البنود.

الكلمات المسموح بها هي:

• أي شيء يبدأ مع 0 ويحتوي فقط على 0 و 1
• أي شيء يبدأ مع 2 والقانوني. هذا يعني أنه يتكون من 0 و 1 من 0 و 1 (إلا أن الحرف الأول هو 2، يتم تعيين جميع الجملات بحق وفقا لتتبع المتغيرات، ويتم تعيينها إلى 1 (لذلك هذا يدل على أن الصيغة تضاءل).
• أي شيء يبدأ مع اثنين على الأقل 2 من 2 ثم يتكون من 0 و 1 (التعبير العادي: 222 * (0 + 1) *، مثل 22221101 ولكن ليس 2212001

لإنتاج 2 222 22 من 0 000 00، عليك أن تفعل ذلك بهذه الطريقة:

(1) تقلب البتات المناسبة - على سبيل المثال 0 100 111 في أربع خطوات. هذا يتطلب إيجاد حل 3SAT.

(2) تغيير الأول بت إلى 2: 2 100 111. هنا سوف تحقق هذا هو في الواقع حل 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-Hard. أشعر أنه قد يكون أكثر صعوبة (#P أو FNP ربما) ولكن صلابة NP كافية لهذا الغرض الذي أعتقد أنه.

يحرر: كنت قد تكون مهتمة في فك تشفير هيكل البيانات. وبعد سيؤدي ذلك إلى اتخاذ القاموس والكلمات الجماعية التي يمكن الوصول إليها من بعضها البعض. يمكنك أيضا تخزين المسار من كل قمة إلى الجذر أو بعض قمة أخرى. هذا سوف يمنحك مسارا، وليس غير عادي أقصر واحد.

Answer 3

هناك طرق كفاءة متفاوتة ل العثور على الروابط - يمكنك إنشاء رسم بياني كامل لكل طول كلمة، أو يمكنك بناء BK-Tree., على سبيل المثال، ولكن صديقك مناسب - BFS هو الخوارزمية الأكثر كفاءة.

ومع ذلك، هناك طريقة لتحسين وقت التشغيل بشكل كبير: بدلا من القيام BFS واحد من العقدة المصدر، قم بإجراء عمليات البحث الأولى الأولى، بدءا من نهاية الرسم البياني، وإنهاء عند العثور على عقدة شائعة في مجموعاتها الحدودية وبعد مقدار العمل الذي يجب القيام به هو نصف ما هو مطلوب تقريبا إذا كنت تبحث من نهاية واحدة فقط.

Answer 4

يمكنك أن تجعلها أسرع قليلا من خلال إزالة الكلمات التي ليست الطول الأيمن، أولا. أكثر من القاموس المحدود سوف يصلح في ذاكرة التخزين المؤقت لمعهد وحدة المعالجة المركزية. ربما كل ذلك.

أيضا، يمكن أن تكون جميع مقارنات STRNCMP (على افتراض أنك جعلت كل شيء صغيرا) مقارنات memcmp، أو حتى مقارنات غير مستقرة، والتي يمكن أن تكون تسريعا.

يمكنك استخدام بعض السحر مسبقا وتجميع المهمة التي تجميعها من خلال طول الكلمة هذه، أو لفة بعض الاختلافات الأمثل لمهمة أطوال الكلمة الشائعة. كل هذه المقارنات الإضافية يمكن أن تذهب بعيدا عن المرح النقي غير المنضد.

Answer 5

هذا هو نموذجي البرمجة الديناميكية مشكلة. تحقق من وجود مشكلة تحرير المسافة.

Answer 6

ما تبحث عنه يسمى مسافة التعديل. هناك العديد من أنواع مختلفة.

من (http://en.wikipedia.org/wiki/edit_distance.): "في نظرية المعلومات وعلوم الكمبيوتر، فإن مسافة التعديل بين سلوتين من الشخصيات هي عدد العمليات المطلوبة لتحويل أحدهم إلى الآخر."

هذه المقالة حول Jazzy (API Java Spell Check API) لديها نظرة عامة لطيفة على هذه الأنواع من المقارنات (إنها مشكلة مماثلة - تقديم التصحيحات المقترحة) http://www.ibm.com/developerworks/java/library/j-jazzy/

Answer 7

يمكنك العثور على أطول لاحق مشترك، وبالتالي العثور على الحروف التي يجب تغييرها.

Answer 8

شعوري الأمعاء هو أن صديقك هو الصحيح، لأنه لا يوجد حل أكثر كفاءة، ولكن هذا هو asumming أنت إعادة تحميل القاموس في كل مرة. إذا كنت ترغب في الحفاظ على قاعدة بيانات قيد التشغيل للتحولات الشائعة، فمن المؤكد أن هناك طريقة أكثر كفاءة للعثور على حل، ولكن عليك أن تولد التحولات مسبقا، واكتشاف ما هي التحولات ستكون مفيدة (بما أنك لا تستطيع توليدها لهم جميعا!) ربما يكون فن من تلقاء نفسه.

Answer 9

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;
};

/ / إرجاع طول سلسلة أقصر سلسلة للوصول إلى "الهدف" من "البداية" // باستخدام الحد الأدنى لعدد التحركات المجاورة. د القاموس

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- shortest-chain-to-reach-a-target-word/