in Englisch Wikipedia in Python finden

Question

zwischen zwei Artikeln kürzesten Weg die Frage:

zwischen zwei Artikeln in Englisch Wikipedia Finden kürzesten Weg. Der Weg zwischen den Artikeln A und B besteht, wenn Artikel C (i) vorhanden ist und in Artikel A ein Link zu Artikel C (1) führt, der in Artikel C (1) zu Artikel C (2) führt. ., in Artikel C (n) ist Link, der zu Artikel B führt

Ich benutze Python. URL zum Download Wikipedia-Artikel:

1. http://en.wikipedia.org/wiki/Nazwa_artykułu
2. http://en.wikipedia.org/w/index.php?title?Nazwa_artykułu&printable=yes
3. Wikipedia API

Ich habe meine Quellcode bearbeitet, aber es funktioniert immer noch nicht, als ich diese Artikel in Codes enthalten kann jeder einer sag mir, was mache ich hier?

Dies ist mein Code:

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 

Answer 1

Wir betrachten Graph Exploration ... warum sollten Sie Dijkstra-Algorithmus in Betracht ziehen ??? IMHO ... ändere den Ansatz.

Zuerst benötigen Sie eine gute heuristische Funktion. Für jeden Knoten, den Sie erweitern, müssen Sie die Entfernung dieses Knotens vom Ziel-/Zielknoten angeben. Nun ... wie Sie die Heuristik berechnen, ist hier die eigentliche Herausforderung. Möglicherweise führen Sie eine Keyword-Zuordnung zwischen der aktuellen Wiki-Seite und Ihrer Zielseite durch. Ein Prozentsatz der Übereinstimmung kann die Schätzung ergeben. Oder ... versuchen Sie, die Relevanz des Inhalts zwischen den beiden Seiten zu erraten. Ich habe eine Ahnung ... vielleicht kann Ihnen ein neuronales Netzwerk hier helfen. Dies kann jedoch auch keine optimale Schätzung anzeigen. Ich bin mir nicht sicher. Sobald Sie eine geeignete Methode gefunden haben, verwenden Sie den Suchalgorithmus A *.

suchen und erkunden Sie die heuristische Funktion, gehen Sie nicht für Breitensuche, finden Sie nicht, wo in der großen weiten Welt der wikipedia am Ende!

Answer 2

die Anzahl der Artikel auf Wikipedia Da wäre es eine unerschwinglich Zeit nehmen, die kürzeste zu berechnen (meine Vermutung - ich habe nicht versucht).

Das eigentliche Problem besteht darin, einen akzeptablen und effizienten kurzen Weg zwischen zwei Artikeln zu finden.

Algorithmen, die sich mit diesem Problem befassen, sind verwandt mit The travelling salesman problem. Es könnte ein guter Ausgangspunkt sein.

IIRC Google oder Yahoo Bots verwenden Ant Colony Optimization, um die kürzeste akzeptabel in optimierter Zeit zu erhalten. Sie könnten diese SO Frage überprüfen: Where can I learn more about "ant colony" optimizations?

Ich bin persönlich auch gerne die genetic algorithms approach, um ein akzeptables Optimum in einer bestimmten Zeit zu finden.

habe ich at that image nur an und das setzt die Anzahl der Artikel zu 4.000.000 für en.wikipedia.com im Jahr 2013 viel weniger, als ich in der Tat gedacht.

EDIT: Ich erklärte zuerst, es war ein NP-Hard-Problem und Kommentatoren erklären, es ist nicht.