#python #artificial-intelligence #depth-first-search
#python #искусственный интеллект #поиск в глубину
Вопрос:
Я пытаюсь использовать DFS для обхода моего графика. Моя функция dfs(cost_matrix, start_point, goals_array)
. Я помещаю путь, по которому алгоритм DFS следует к любому ИЗ ЦЕЛЕВЫХ состояний, в список. Кажется, я не могу понять, когда добавлять и извлекать элементы из списка во время обхода. Я знаю, что после достижения целевого состояния я могу просто выйти из цикла. Я использую метод стека DFS итеративно.
def DFS_Traversal(cost, start_point, goals):
num = len(cost)
visited = [0] * num
visited[start_point] = 1
stack = []
stack.append(start_point)
l = [] #used to store the final path
l.append(start_point)
while(len(stack)):
s = stack.pop()
if(visited[s] == 0):
visited[s] = 1
if s in goals:
break
for i in range (1, num): #going across the matrix
if (cost[s][i] != -1 || cost[s][i] != 0):
stack.append(i) #adding members to the stack
return l
Комментарии:
1. Не могли бы вы опубликовать свою функцию dfs
2. я добавил код
Ответ №1:
Взято и немного изменено, чтобы соответствовать требованию в вопросе и прерываться при нахождении одной из целей — отсюда:
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited, goals):
# Mark the current node as visited
# and print it
print(" ")
visited[v] = True
for goal in goals:
if v == goal:
print(f"found {v} - finish!")
return
print(v, end = ' ')
# Recur for all the vertices
# adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited, goals)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v, goals):
# Mark all the vertices as not visited
visited = [False] * (max(self.graph) 1)
# Call the recursive helper function
# to print DFS traversal
self.DFSUtil(v, visited, goals)
# Driver code
# Create a graph given
# in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is DFS from (starting from vertex 2)")
g.DFS(2, [1,4])
вывод:
Following is DFS from (starting from vertex 2)
2
0
found 1 - finish!
Ответ №2:
# Using a Python dictionary to act as an adjacency list
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
visited = set() # Set to keep track of visited nodes.
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
dfs(visited, graph, 'A')
вот как работает dfs