Кратчайший путь для преобразования одного слова в другое

Question

Для проекта Data Structures я должен найти кратчайший путь между двумя словами (например, "cat" и "dog"), меняя только одну букву за раз. Нам дан список слов Эрудит, чтобы использовать его при поиске пути. Например:

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

Я решил проблему с помощью поиска в ширину, но ищу что-то лучше (я обозначил словарь с помощью трех).

Пожалуйста, дайте мне несколько идей относительно более эффективного метода (с точки зрения скорости и памяти). Что-то смешное и / или вызывающее является предпочтительным.

Я спросил одного из моих друзей (он младший), и он сказал, что нет эффективного решения этой проблемы. Он сказал, что я узнаю почему, когда я пошел на курс алгоритмов. Любые комментарии по этому поводу?

Мы должны переходить от слова к слову. Мы не можем идти cat -> dat -> dag -> dog. Мы также должны распечатать обход.

Answer 1

НОВЫЙ ОТВЕТ

Учитывая недавнее обновление, вы можете попробовать A * с расстоянием Хемминга в качестве эвристики. Это допустимая эвристика, поскольку она не будет переоценивать расстояние

СТАРЫЙ ОТВЕТ

Вы можете изменить динамическую программу, используемую для вычисления расстояния Левенштейна , чтобы получить последовательность операций.

РЕДАКТИРОВАТЬ: Если есть постоянное количество строк, проблема решается за полиномиальное время. Иначе, это NP-hard (все это есть в википедии) ... если ваш друг говорит о проблеме NP-hard.

РЕДАКТИРОВАТЬ: Если ваши строки имеют одинаковую длину, вы можете использовать Расстояние Хэмминга .

Answer 2

При наличии словаря BFS является оптимальным, но необходимое время работы пропорционально его размеру (V + E). С n буквами в словаре может быть ~ a ^ n entires, где a - размер алфавита. Если словарь содержит все слова, кроме того, которое должно быть в конце цепочки, то вы пройдете все возможные слова, но ничего не найдете. Это обход графика, но его размер может быть экспоненциально большим.

Вы можете задаться вопросом, возможно ли сделать это быстрее - просмотреть структуру «разумно» и сделать это за полиномиальное время. Ответ, я думаю, нет.

Проблема:

Вам дан быстрый (линейный) способ проверить, есть ли слово в словаре, два слова u, v и проверить, есть ли последовательность u -> a ₁ -> a ₂ -> ... -> a _n -> v.

NP-жесткий.

Доказательство: возьмите 3SAT, например

(p или q или не r) и (p или не q или r)

Вы начнете с 0 000 00 и должны проверить, можно ли перейти к 2 222 22.

Первый символ будет "мы закончили", три следующих бита будут управлять p, q, r и два следующих будут управлять предложениями.

Допустимые слова:

• Все, что начинается с 0 и содержит только 0 и 1
• Все, что начинается с 2 и является законным. Это означает, что он состоит из 0 и 1 (за исключением того, что первый символ равен 2, все биты предложений справедливо установлены в соответствии с битами переменных, и они установлены в 1 (поэтому это показывает, что формула выполнима).
• Все, что начинается с по крайней мере двух 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-трудной. Я чувствую, что это может быть еще сложнее (вероятно, #P или FNP), но NP-твердость достаточно для этой цели, я думаю.

Редактировать : Вас может заинтересовать несвязанная структура данных набора . Это займет ваш словарь и групповые слова, которые могут быть достигнуты друг от друга. Вы также можете сохранить путь от каждой вершины до корня или другой вершины. Это даст вам путь, не обязательно самый короткий.

Answer 3

Существуют методы различной эффективности для поиска ссылок - вы можете построить полный график для каждой длины слова, или вы можете, например, создать BK-Tree , но ваш друг прав - BFS - самый эффективный алгоритм.

Однако существует способ значительно улучшить время выполнения: вместо выполнения одной BFS с исходного узла, выполните два поиска в ширину, начиная с любого конца графика и заканчивая, когда вы находите общий узел в их пограничные наборы. Объем работы, который вам нужно выполнить, примерно вдвое меньше необходимого, если вы выполняете поиск только с одного конца.

Answer 4

Вы можете сделать это немного быстрее, сначала удалив слова неправильной длины. Больше ограниченного словаря поместится в кэш процессора. Наверное, все это.

Кроме того, все сравнения strncmp (при условии, что вы сделали все строчными) могут быть сравнениями memcmp или даже развернутыми сравнениями, что может привести к ускорению.

Вы можете использовать магию препроцессора и жестко скомпилировать задачу для этой длины слова, или бросить несколько оптимизированных вариантов задачи для общих длин слова. Все эти дополнительные сравнения могут «уйти» ради чистого развёрнутого веселья.

Answer 5

То, что вы ищете, называется Редактировать расстояние. Есть много разных типов.

From (http://en.wikipedia.org/wiki/Edit_distance): "В теории информации и информатике расстояние редактирования между двумя строками символов - это число операций, необходимых для преобразования одной из них в другую."

В этой статье о Jazzy (API проверки правописания java) содержится хороший обзор сравнений такого рода (аналогичная проблема - предоставление предлагаемых исправлений) http://www.ibm.com/developerworks/java/library/j-jazzy/

Answer 6

Это типичная проблема динамического программирования . Проверьте наличие проблемы редактирования расстояния.

Answer 7

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/

Answer 8

Мне кажется, что ваш друг прав, потому что нет более эффективного решения, но это предполагает, что вы каждый раз перезагружаете словарь. Если бы вы сохранили работающую базу данных общих переходов, то наверняка был бы более эффективный метод поиска решения, но вам нужно было бы сгенерировать переходы заранее и выяснить, какие переходы будут полезны (поскольку вы не можете сгенерировать их всех!), вероятно, искусство само по себе.

Answer 9

Вы можете найти самую длинную общую подпоследовательность и, следовательно, найти буквы, которые нужно изменить.