2017-12-01 12 views
0

私は人気のあるケビンベーコンゲームのグラフ表現を作成しようとしています。私はグラフと頂点のクラスを作成しましたが、グラフを横断してケビン・ベーコンから俳優までの最短経路を見つけ出し、途中でエッジをプリントアウトするための最初の検索方法を作成するのに問題があります。 ユーザーは俳優を入力する必要があり、プログラムはケビンベーコンからその俳優までの最短経路を見つけなければなりません。ユーザーは俳優に入り続け、その俳優への最短経路がとられ、ケビンベーコンの番号が印刷されます。そうでなければ、それは印刷されません。ケビンベーコンゲームの最短経路グラフトラバーサル

頂点とグラフのクラスがあります。頂点クラスは、それが接続されている他の頂点と辺を含むディクショナリです。

私はこのようなルックスで働いていたデータ:

頂点:

[ "ケビン・ベーコン"、 "actor1"、 "ACTOR2"、 "ACTOR3"、 "actor4"、 "actor5"、 "actor6"]

エッジ:

( "ケビン・ベーコン"、 "actor1"、 "MOVIE1")

( "ケビン・ベーコン"、 "ACTOR2"、 "MOVIE1")

( "actor1"、 "ACTOR2"、 "MOVIE1")

( "actor1"、 "ACTOR3"、 "MOVIE2")

( "ACTOR3"、 "ACTOR2"、 "movie3")

( "ACTOR3"、 "actor4"、 "movie4")

( "actor5"、 "actor6"、 "movie5")映画は、エッジ名または量が

、及びタプルの他の部分は頂点です。 BFSアルゴリズムですべてのエッジとケビンベーコンの番号を出力したり、アクターに到達できない場合は不可能であることを表示したりします。

ここまではコードです。どんなアドバイスや助けもありがとうございます。

class Vertex: 
    ''' 
    keep track of the vertices to which it is connected, and the weight of each edge 
    ''' 
    def __init__(self, key): 
     ''' 

     ''' 
     self.ID = key 
     self.connected_to = {} 

    def add_neighbor(self, neighbor, weight=0): 
     ''' 
     add a connection from this vertex to anothe 
     ''' 
     self.connected_to[neighbor] = weight 

    def __str__(self): 
     ''' 
     returns all of the vertices in the adjacency list, as represented by the connectedTo instance variable 
     ''' 
     return str(self.ID) + ' connected to: ' + str([x.ID for x in self.connected_to]) 

    def get_connections(self): 
     ''' 
     returns all of the connections for each of the keys 
     ''' 
     return self.connected_to.keys() 

    def get_ID(self): 
     ''' 
     returns the current key id 
     ''' 
     return self.ID 

    def get_weight(self, neighbor): 
     ''' 
     returns the weight of the edge from this vertex to the vertex passed as a parameter 
     ''' 
     return self.connected_to[neighbor] 


class Graph: 
    ''' 
    contains a dictionary that maps vertex names to vertex objects. 
    ''' 
    def __init__(self): 
     ''' 

     ''' 
     self.vert_list = {} 
     self.num_vertices = 0 

    def __str__(self): 
     ''' 

     ''' 
     edges = "" 
     for vert in self.vert_list.values(): 
      for vert2 in vert.get_connections(): 
       edges += "(%s, %s)\n" %(vert.get_ID(), vert2.get_ID()) 
     return edges 

    def add_vertex(self, key): 
     ''' 
     adding vertices to a graph 
     ''' 
     self.num_vertices = self.num_vertices + 1 
     new_vertex = Vertex(key) 
     self.vert_list[key] = new_vertex 
     return new_vertex 

    def get_vertex(self, n): 
     ''' 

     ''' 
     if n in self.vert_list: 
      return self.vert_list[n] 
     else: 
      return None 

    def __contains__(self, n): 
     ''' 
     in operator 
     ''' 
     return n in self.vert_list 

    def add_edge(self, f, t, cost=0): 
     ''' 
     connecting one vertex to another 
     ''' 
     if f not in self.vert_list: 
      nv = self.add_vertex(f) 
     if t not in self.vert_list: 
      nv = self.add_vertex(t) 
     self.vert_list[f].add_neighbor(self.vert_list[t], cost) 

    def get_vertices(self): 
     ''' 
     returns the names of all of the vertices in the graph 
     ''' 
     return self.vert_list.keys() 

    def __iter__(self): 
     ''' 
     for functionality 
     ''' 
     return iter(self.vert_list.values()) 

    def bfs(self): 
     ''' 
     Needs to be implemented 
     ''' 
     pass 

答えて

1
  1. お時間をいただき、ありがとうございます俳優は俳優がケビン・ベーコンの場合は、
  2. を取ったパスに沿って戻ってケビン・ベーコン
  3. であれば俳優
  4. チェックします
  5. 俳優がケビン・ベーコンでない場合は、チェックしていない俳優に接続しているすべての俳優を探します。
  6. このアクターが接続しているすべてのアクターをリストに追加してチェックします。

ここでもっとも難しい問題は、あなたが既に訪れた頂点を記録することです。私はあなたのアルゴリズムが頂点のリストをチェックすべきだと思います。いくつかの前提:

  • 各頂点は1回だけリストされます。
  • 頂点は一方向のみです。つまり、アクタ1からアクタ2、アクタ2からアクタ1に移動するには、アクタごとに1つずつ、2つの頂点が必要です。
  • 体重がありますが、どのように体重がかかるのかわかりません。私はそれらを実装しようとします。また、デフォルトの重みを0にすることも、すべてのパスを等しく短くすることもできません(0 * n = 0)。

OKしてください。

def bfs(self, actor): 
    from heapq import heappush, heappop 
    if actor == "Kevin Bacon": 
     return print("This actor is Kevin Bacon!") 
    visited = set() 
    checked = [] 
    n = 0 
    heappush(checked, (0, n, [self.get_vertex(actor)])) 
    # if the list is empty we haven't been able to find any path 
    while checked: 
     # note that we pop our current list out of the list of checked lists, 
     # if all of the children of this list have been visited it won't be 
     # added again 
     current_list = heappop(checked)[2] 
     current_vertex = current_list[-1] 
     if current_vertex.ID == "Kevin Bacon": 
      return print(current_list) 
     for child in current_vertex.get_connections(): 
      if child in visited: 
       # we've already found a shorter path to this actor 
       # don't add this path into the list 
       continue 
      n += 1 
      # make a hash function for the vertexes, probably just 
      # the hash of the ID is enough, ptherwise the memory address 
      # is used and identical vertices can be visited multiple times 
      visited.add(child) 
      w = sum(current_list[i].get_weight(current_list[i+1]) 
        for i in range(len(current_list)-1)) 
      heappush(checked, (w, n, current_list + [child])) 
    print("no path found!") 

また、頂点クラスに__repr __()メソッドを実装する必要があります。私が使用したもので、出力は次のようになります。

g = Graph() 
for t in [("Kevin Bacon", "actor1", "movie1") 
,("Kevin Bacon", "actor2", "movie1") 
,("actor1", "actor2", "movie1") 
,("actor1", "actor3", "movie2") 
,("actor3", "actor2", "movie3") 
,("actor3", "actor4", "movie4") 
,("actor5", "actor6", "movie5")]: 
    g.add_edge(t[0],t[1],cost=1) 
    g.add_edge(t[1],t[0],cost=1) 

g.bfs("actor4") 
# prints [Vertex(actor4), Vertex(actor3), Vertex(actor2), Vertex(Kevin Bacon)] 

私はもともとこれを行うためにheapqを使用しようが、最終的に、私は同様かもしれないことを決めていませんでした。基本的には、チェックリストをソートして最短パスを最初に取得する必要があります。これを行う最も簡単な方法は、一番上から最小の値をポップするたびにリストを並べ替えるだけですが、リストが大きくなると非常に遅くなることがあります。 Heapqはリストをより効率的に並べ替えることができますが、追加するリストの最小値を得るためのキーメソッドはないので、タプルを使ってそれを偽造する必要があります。タプルの最初の値はパスの実際のコストですが、2番目の値は単なる「タイブレーカー」なので、頂点を比較しようとしません(順序付けされていない)。

関連する問題