Я (медленно) пишу обзор Руководства по алгоритмам хемоинформатики для новостей SIGACT. В одной главе рассматриваются текущие реализации программного обеспечения, и поиски в базе данных (и другие приложения), по-видимому, не используют столько информации о графиках, сколько могли бы. С другой стороны, возможно, более теоретические алгоритмы будут слишком сложны для реализации. Похоже, что это потенциальная открытая площадка.
Итак, вот мой вопрос:
Есть ли обзор (или небольшое количество ссылок), в котором обсуждается теория и реализация (надеюсь) алгоритмов баз данных графов с метрической информацией? (Каждое ребро является расстоянием, а каждая вершина имеет объем.) Безхимическое описание примерной задачи будет следующим: по базе данных графов найдите все из них, которые содержат определенный подграф.
источник
Ответы:
По-видимому, это связано с проблемой изоморфизма подграфа, которая в общем случае NP-полна, даже без весов. В соответствующей статье Википедии утверждается, что в некоторых случаях ее можно эффективно решить.
Если химия - это что-то вроде биоинформатики, вам, вероятно, будут интересны алгоритмы аппроксимации для борьбы с шумом. Кроме того, с учетом поиска базы данных в качестве приложения, могут быть умные идеи для предварительной обработки, которые дают хорошие амортизируемые среды выполнения.
Нашел (не читал) те:
http://www.springerlink.com/content/4751121q3575v041/
http://bioinformatics.oxfordjournals.org/content/23/2/232.full
http://portal.acm.org/citation.cfm?id=1368898
Отказ от ответственности : Опять же, извините за ответ в стиле комментариев; Мне пока не разрешено комментировать.
источник