VPF::построение максимальной цепочки слов

derek

Дата 13.5.2009, 10:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 124
Регистрация: 16.7.2006

Репутация: нет
Всего: нет

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

на вход подается список данных
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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 2
Всего: 17

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

--------------------

Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)

derek

Дата 16.5.2009, 04:25 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 124
Регистрация: 16.7.2006

Репутация: нет
Всего: нет

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

aram90

Дата 16.5.2009, 08:13 (ссылка)

(нет голосов)

Загрузка ...

Bug hunter

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 1.12.2008
Где: Yerevan, Armenia

Репутация: 1
Всего: 3

Ну граф построить можно так, каждая группа слов это вершина, и межды двумя вершинами есть ребро, если в группах соответствующим этим вершинам есть общее слово. Теперь надо найти максимально длинный путь в графе. Это можно делать с помощью такого алгоритма:
пусть матрица 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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »