Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > построение максимальной цепочки слов

Автор: derek 13.5.2009, 10:57

стало интересно, а существуют ли готовые алгоритмы построения цепочки слов по такому принципу

на вход подается список данных
blazing skies
looney tunes basketball
charlie and the chocolate factory
acme animation factory
looney tunes: acme arsenal
charlie's angels
looney tunes: back in action
blazing angels: squadrons of wwii

ищутся пары в массиве с одинаковыми словами и ищется максимально длинная цепочка таких пар, т.е. на выходе надо получить что-то вроде этого

blazing skies —(blazing)→ blazing angels: squadrons of wwii —(angels)→ charlie's angels —(charlie)→ charlie and the chocolate factory —(factory)→ acme animation factory —(acme)→ looney tunes: acme arsenal —(looney)→ looney tunes: back in action —(tunes)→ looney tunes basketball

Автор: ksili 13.5.2009, 12:01

Похоже, это задачка на графы. Правда там обычно ищут кратчайший путь, а тут нужен наиболее длинный.

Автор: derek 16.5.2009, 04:25

то, что это задачка на графы понятно. Мне бы алгоритм...

Автор: aram90 16.5.2009, 08:13

Ну граф построить можно так, каждая группа слов это вершина, и межды двумя вершинами есть ребро, если в группах соответствующим этим вершинам есть общее слово. Теперь надо найти максимально длинный путь в графе. Это можно делать с помощью такого алгоритма:
пусть матрица m[i][j] будет показывать для вершин i и j длиннейший путь между ними. В начале если i и j соединены, то m[i][j]=1, иначе m[i][j]=-1 : Потом вот остальное:

Код


for(k=0;k<n;k++)
{
    for(i=0;i<n;i++)
    {
         for(j=0;j<n;j++)
         {
              if(m[i][k]!=-1 && m[k][j]!=-1 && m[i][k]+m[k][j]>m[i][j])
              {
                   m[i][j]=m[i][k]+m[k][j];
                   parent[i][j]=k;
              }
         }
    }
}

после этого в матрице надо искать наибольшее число, какое то m[i][j], значит максимальный путь идет с i до j, а найти его можно с помощью рекурсии, чтобы идти с i на j, надо идти с i на parent[i][j], потом с parent[i][j] на j, а если i и j соединены ребром, тогда идем прямо.
Только если в графе будет цикл, то не получится. И еще, количество групп слов надеюсь не большое, потому что как видно, сложность этого алгоритма O(n^3)

Автор: maxdiver 16.5.2009, 21:24

К сожалению, при естественной постановке задачи в графе обязательно будут циклы...
А задача нахождения длиннейшего простого пути в произвольном графе - NP-полная, т.е. для неё нет эффективных точных алгоритмов (хотя есть быстрые приближённые алгоритмы, способные найти достаточно длинные пути).