|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 03 Feb 2003 18:16:23
To : Evgeniy Jirnov
Subject : Re: Сложная ( для меня) задача...
--------------------------------------------------------------------------------
Evgeniy Jirnov wrote:
>
> 1. Придти к конечному слову, изменяя одну букву. Все слова должны
> содержать
> 2. Придти к конечному слову, так чтобы следующее слово начиналось с
> последней
> буквы предыдущего.
Обе эти задачи - не что иное, как поиск наикратчайшего пути в графе.
Только правило перехода из одного узла в другой разное. И все. А в
остальном все решения абсолютно идентичны.
Поиск наикратчайшего пути в графе делается волновым алгоритмом,
который я тут приводил в письме от 6 января.
Количество операций при этом в худшем случае - N * K,
где N - размер словаря, а К - число шагов по наикратчайшему
пути от источника до цели.
То есть в самом xудшем случае - N * N.
При словаре в 10000 слов - не более 100 миллионов операций.
Отработает за несколько секунд...
Если предполагается на одном словаре делать много поисков
для разных пар слов, можно сначала проиндексировать
словарь в соответствии с текущим правилом. Искать будет
быстрее. А для единичного поиска индексация наверное и смысла
не имеет. Ибо расходы на индексацию будут сопоставимы с
расходами на линейный поиск с вычеркиваниями.
> 3. Есть слово. Гхм... Как бы объяснить... В общем покажу на примере:
> к->ур->а
> а->му->р
> р->яв->к
> а->мб->а
Разбиваешь слова в группы по длине слова. Каждому слову ставишь в
соответствие пару {первый_символ, последний_символ }
Потом одинаковые пары группируешь в триады:
{первый_символ, последний_символ, сколько_таких_пар }.
Потом для пары входных слов смотришь, сколько и каких
пар нужно. И по триадам смотришь - есть ли достаточное
количество таких пар для данной длины строки.
Потом перебираешь от самых коротких слов к более длинным,
пока не найдешь.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
