Найти кратчайший путь между двумя статьями в английской Википедии в Python

Вопрос:

Найдите кратчайший путь между двумя статьями в английской Википедии. Путь между статьями A и B существует, если существуют статьи C (i), и в статье A имеется ссылка, которая приводит к статье C (1), в статье C (1), которая приводит к статье C (2),..., в статье C (n) ссылка, которая приводит к статье B

Я использую Python. URL для загрузки статьи в википедии:

Я отредактировал мой исходный код, но он все еще не работает, когда я включаю эти статьи в коды, может кто-нибудь сказать мне, что я здесь возился?

Это мой код:

import urllib2
import re
import xml.etree.ElementTree as ET

text = ET.fromstring(F_D.text.encode('UTF-8'))
text = ET.fromstring(P.text.encode('UTF-8'))
F_D=requests.get('http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms')
P=requests.get('http://en.wikipedia.org/wiki/Wikipedia:Unusual_articles')  
links = text.findall('.//*[@id="mw-content-text"]/p/a')

links=E_D

E_D = graph_dict
E_D[start] = 0

for vertex in E_D:
    F_D[vertex] = E_D[vertex]
    if vertex == end: break

    for edge in graph[vertex]:
        path_distance = F_D[vertex] + graph[vertex][edge]
        if edge in F_D:
            if path_distance < F_D[edge]:
                #raise ValueError,
            elif edge not in E_D or path_distance < E_D[edge]:
                E_D[edge] = path_distance
                [edge] = vertex
return (F_D,P)

def Shortest_Path(graph,start,end):
  F_D,P = D_Algorithm(graph,start,end)
  path = []
  while 1:
    path.append(end)
    if end == start: break
    end = P[end]
  path.reverse()
  return path

Ответы

Ответ 1

Мы смотрим на исследование графика... почему вы должны рассматривать алгоритм Дейкстры? ИМХО... изменить подход.

Во-первых, вам нужна хорошая эвристическая функция. Для каждого node, который вы расширяете, вам нужно geusstimate расстояние от этого node от цели/цели node. Теперь... как вы вычисляете эвристику, это настоящая проблема здесь. Возможно, вы можете выполнить сопоставление ключевых слов между текущей страницей wiki и целевой страницей. Процент матча может дать вам оценку. Или... попытайтесь угадать актуальность содержания между двумя страницами. У меня есть подозрение... возможно, нейронная сеть может вам помочь. Но это не может указывать на оптимальную оценку. Я не уверен. Как только вы выясните подходящий способ сделать это, используйте алгоритм поиска A *.

Ищите и исследуйте эвристическую функцию, не ходите для поиска по ширине, вы не найдете нигде в обширном мире википедии!

Ответ 2

Учитывая количество статей по википедии, для вычисления кратчайшего времени потребуется самое неподходящее время (мое предположение - я не пробовал).

Реальная проблема заключается в том, чтобы найти приемлемый и эффективный короткий путь между двумя статьями.

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

В браузере IIRC google или yahoo используйте Ant Оптимизация колоний, чтобы получить максимально возможное время в оптимальное время. Вы можете проверить этот вопрос SO: Где я могу узнать больше о "ant colony" оптимизация?

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


Я только что посмотрел на этом изображении и который устанавливает количество статей в 4.000.000 для en.wikipedia.com в 2013 году. Гораздо меньше, чем я думал.

РЕДАКТИРОВАТЬ: я сначала заявил, что это проблема NP-Hard, и комментаторы этого не объясняют.