Использование Python поиска в ширину на социальном графе

Я читал много вопросов о stackoverflow о том, как использовать поиск в ширину, dfs, A * и т. Д., Вопрос в том, что является оптимальным использованием и как реализовать его в реальных графах, смоделированных стихами. Например.

Предположим, у вас есть социальный граф Twitter/Facebook/какой-то социальной сети, и мне кажется, что алгоритм поиска будет работать следующим образом:

Если бы у пользователя А было 10 друзей, то у одного из них было бы 2 друга, а у другого 3. Поиск сначала выяснил бы, кто друзья пользователя А, а затем он должен был бы найти, кто друзья, где каждый из десяти пользователей. Мне кажется, это bfs?

Однако я не уверен, что это способ реализации алгоритма.

Спасибо,


python algorithm traversal social-networking breadth-first-search
person eWizardII    schedule 20.12.2010    source источник
comment
Я считаю, что описание поиска в википедии «сначала хлеб» достаточно описательно с точки зрения того, как обращаться с реализацией. en.wikipedia.org/wiki/Breadth-first_search   -  person Manuel Salvadores    schedule 20.12.2010
comment
Реализация будет зависеть от того, чего вы надеетесь достичь, но из вашего вопроса я не совсем понимаю желаемый результат. Вы ищете кратчайший путь между друзьями? Или вы просто пытаетесь пройти весь график?   -  person Gabriel Grant    schedule 20.12.2010
comment
Спасибо, я просто пытаюсь пройти весь граф, а точнее искать кратчайший путь.   -  person eWizardII    schedule 20.12.2010

Ответы (2)


arrow_upward
0
arrow_downward

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

Я просто пытаюсь пройти весь график

Это означает, что ваша терминология технически некорректна — вы говорите о обходе графика, а не о поиске на графике. Если вы на самом деле не пытаетесь найти что-то конкретное, о чем вы, кажется, вообще не упоминаете в вопросе.

С учетом сказанного, Facebook и Twitter — это очень разные графические структуры, которые действительно влияют на то, как вы их просматриваете:

  1. Facebook — это, по сути, неориентированный граф. Если X дружит с Y, Y ДОЛЖЕН дружить с X. (Или в отношениях, или связанных с ним, и т. д.).

  2. Twitter — это, по сути, ориентированный граф. Если вы X следует за Y, Y не обязан следовать за X.

Эти проблемы существенно повлияют на алгоритм обхода графа. Честно говоря, если вы просто хотите посетить все узлы, вам вообще нужен график? Почему бы просто не перебрать их все? Если у вас есть все узлы в некоторой структуре данных MY_DATA, которая является итерируемой, у вас может быть просто выражение генератора, подобное этому:

def nodeGenerator(MY_DATA)
    for node in MY_DATA:
        yield node

Ясно, что вам нужно настроить внутренние компоненты nodeGenerator, чтобы обрабатывать то, как вы на самом деле получаете доступ к узлам. При этом большинство графовых структур реализуют итератор узлов. Затем вы можете просто создать итератор в любое время, когда захотите что-то сделать с помощью:

 for node in nodeGenerator(MY_DATA):
     (Do something here)

Может быть, я просто упускаю суть вопроса, но в настоящее время вы задали вопрос об алгоритмах поиска без проблемы поиска. Из-за бесплатного обеда характера оптимизации и поиска ценность любого алгоритма поиска будет полностью в зависимости от проблемы поиска, которую вы пытаетесь изучить.

Это верно даже среди одного и того же набора данных. В конце концов, если бы вы искали всех, чье имя начинается с буквы D, отличным подходом было бы просто отсортировать всех по алфавиту и выполнить бинарный поиск. Если вместо этого вы пытаетесь найти степень отделения каждого от Кевина Бэкона, вам понадобится алгоритм, который начинается с мистера Бэкона и рекурсивно перебирает всех, кто его знает, и всех, кого они знают. Это обе вещи, которые вы МОЖЕТЕ делать на Facebook или Twitter, но без какой-либо конкретики действительно невозможно рекомендовать алгоритм. Следовательно, если вы ничего не знаете, просто переберите всех в виде списка. Это так же хорошо, как и все остальное. Если вы затем хотите оптимизировать, кэшируйте любые вычисления.

person Namey    schedule 06.06.2011

arrow_upward
0
arrow_downward

У меня около 300 друзей в Facebook, и у некоторых моих друзей в среднем по 300 друзей. Если вы построите из этого график, он будет огромным. Поправьте меня, если я ошибаюсь? . В этом сценарии BFS будет достаточно требовательным?

Спасибо J

person Jijoy    schedule 13.06.2011