Найти кратчайший путь между двумя веб-страницами

Question

Мне нужно найти кратчайшее расстояние между двумя страницами Википедии (в «прыжках»)

У меня есть способ извлечь все внутренние вики-ссылки на странице

Я знаю начальный пункт назначения и конечный пункт назначения, но я не знаю, как извлечь данные из данных

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

Если у кого-то есть идеи о том, что такое хорошая структура данных для хранения информации, а затем как ее просмотреть, я был бы очень признателен

Answer 1

Знаете ли вы что-нибудь о теории графов ? У вас есть необходимые данные для построения графика, но вам нужно будет использовать алгоритм Дейкстры , чтобы пройти по нему, чтобы найти кратчайший путь между вашими двумя точками.

Answer 2

Может быть, это немного глупо, поскольку я не программист на C #, а многомерный массив, содержащий все ссылки внутри, в зависимости от глубины измерений, позволяющий узнать, какой путь содержит меньше обручей.

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

Примерно так:

[source] -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> etc
         -> [source link] -> ['source link' link] -> [target]
         -> [source link] -> ['source link' link] -> etc

Answer 3

Вот реализация алгоритма Дейкстры в python: http://code.activestate.com/recipes/119466/

Answer 4

Если у вас есть IEnumerable<Link> PageLinks(Link link)

Количество прыжков будет определяться следующим образом:

Link curentPage = "somepage";
Link destinationPage = "otherpage";
if (currentPage == destinationPage) return 0;
int hops = 1;
IEnumerable<Link> currentLinks = PageLinks(currentPage);
IEnumerable<Link> visited = new [] {currentPage};
while(!currentLinks.Contains(destinationPage)) 
{
    currentLinks = currentLinks
        .SelectMany(l => PageLinks(l).Where(f => !visited.Contains(f)));
    visited = visited.Union(currentLinks);
    hops++;
}
return hops;

Отредактировано, чтобы сделать быстрее для езды на велосипеде, хотя алгоритм работал бы без него. Он может работать до StackOverflow или около того, если страницы не связаны.

Answer 5

Я думаю, что график в этом случае редок. Поэтому было бы неплохо использовать что-то вроде HashSet для каждой страницы Википедии, со страницами, на которые она ссылается внутри набора.

В этом случае вам не нужно реализовывать алгоритм кратчайшего пути Диджикстры. Поскольку эта проблема равна задаче кратчайшего пути, где вес каждого ребра равен 1. Вы можете просто выполнить поиск в ширину и получить глубину, на которой находится страница назначения.