Проблема возврата значения в функции класса Python - PullRequest
Новая
       18

Проблема возврата значения в функции класса Python

0 голосов
/ 02 февраля 2019

Итак, я работал над проектом, и в этом я должен найти наилучший возможный путь ... поэтому я использовал DFS для этого сейчас, проблема в том, что при рекурсивном вызове он печатает все возможные результаты и в концеЛучший.Но эти значения не сохраняются в списке переменных «PathList» класса.

, например: Graph.py - это другой файл, в котором хранятся графики 

import Graph

class G:
    def __init__(self,Graph,vis):
        self.graph = Graph
        self.dist=1000000
        self.PathList= []
        self.stack=[]
        self.visited=vis

    def addEdge(self, u,v):
        self.graph[u].append(v)

    def DFScall(self,v,f,dis):

        self.visited[v]=True
        self.stack.append(v)
        dis+=1
        if(v==f):
            if(dis<self.dist):
                self.PathList = self.stack
                self.dist=dis
                #print(self.PathList)
        else :
            for i in self.graph[v]:
                if self.visited[i] == False:
                    #print(self.visited[i])
                    self.DFScall(i,f,dis)

        self.stack.pop()
        self.visited[v]=False


    def DFS(self,v,f):

        self.DFScall(v,f,0)

    def returnPath(self):
        return self.PathList


if __name__== "__main__":
    graph=Graph.returnGraph()
    vis=Graph.returnNodes()
    g = G(graph,vis)
    g.DFS('S1','B8')

    Pathlist = g.returnPath()
    print(Pathlist)

и выводis: 

['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'G2', 'H3', 'I2', 'J3', 'J4', 'I5', 'H4', 'G5', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'G2', 'H3', 'H4', 'G5', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'D3', 'E2', 'F3', 'F4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'D4', 'E5', 'E6', 'D7', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'C6', 'D7', 'D8', 'C9', 'B8']
['S1', 'F0', 'E1', 'D0', 'C1', 'C2', 'B3', 'B4', 'C5', 'C6', 'B7', 'B8']
['S1', 'F0', 'E1', 'E2', 'D3', 'D4', 'C5', 'C6', 'B7', 'B8']
[]

Последний вывод списка - это вывод при вызове через main ..... Что я должен сделать в этом случае и сказать, есть ли что-то, что мне нужно изучить.

Спасибо

Ответы [ 2 ]

0 голосов
/ 03 февраля 2019

Это потому, что вы на самом деле не копируете stack, делая 

self.PathList = self.stack

Замените его на 

self.PathList = self.stack[:]

или 

self.PathList = list(self.stack)
0 голосов
/ 03 февраля 2019

Проблема в том, что вы не создаете копию лучшего пути.Вы должны сделать: 

self.PathList = self.stack.copy()

Полный пример (с изменением PEP8 для удобства чтения): 

import Graph


class GraphSearch:
    def __init__(self, graph, nodes):
        self.graph = graph.copy()
        self.nodes = nodes.copy()

        self.visited = None
        self.best_path_list = None
        self.current_path_list = None

    def reset_search(self):
        self.visited = {k: False for k, v in self.nodes.items()}
        self.best_path_list = list()
        self.current_path_list = list()

    def _dfs_call(self, current_node, end_node):

        self.visited[current_node] = True
        self.current_path_list.append(current_node)

        if(current_node == end_node):
            current_distance = len(self.current_path_list)
            best_distance = len(self.best_path_list)
            if(current_distance < best_distance):
                self.best_path_list = self.current_path_list.copy()
        else:
            for adj_node in self.graph[current_node]:
                if not self.visited[adj_node]:
                    self._dfs_call(adj_node, end_node)

        self.current_path_list.pop()
        self.visited[current_node] = False

    def dfs(self, current_node, end_node):
        self.reset_search()
        self._dfs_call(current_node, end_node)


if __name__ == "__main__":
    graph = Graph.return_graph()
    nodes = Graph.return_nodes()
    graph_search = GraphSearch(graph, nodes)
    start_node = 'S1'
    end_node = 'B8'
    graph_search.dfs(start_node, end_node)
    print(graph_search.best_path_list)

Я не тестировал код, так как у меня нет тестовых данных.

...