python - 形成具有直接优先级的任务链
问题描述
我正在尝试在给定任务对列表的情况下形成一个任务链(按数字索引)。
在以下列表中:
[[1, 3],
[2, 3],
[3, 4],
[4, 5],
[4, 8],
[5, 6],
[6, 7],
[6, 10],
[7, 11],
[7, 12],
[8, 9],
[8, 11],
[9, 13],
[9, 10],
[11, 13],
[12, 15],
[13, 14],
[14, 16],
[14, 19],
[14, 20],
[15, 17],
[15, 22],
[16, 18],
[17, 18],
[17, 23],
[18, 25],
[19, 22],
[20, 21],
[20, 25],
[21, 22],
[21, 24],
[23, 25]]
数字代表可用任务(例如,任务 1、任务 2、...、任务 25)和优先关系(例如,任务 1 后跟任务 3,任务 2 后跟任务 3 等)
我希望使用 python 找到这个列表中所有可能的任务链,但我遇到了一些困难。我目前的想法遇到了问题,即我从一开始就形成新的任务链列表,并在任务有超过 1 个后继者时复制它们。但是,我不确定如何确保每个新复制的列表都包含不同的后继者,以及如何再次迭代地运行每个列表。
以下代码是我目前的尝试:
> Initial = []; Task_Chain = []
> for i in range(1,26):
> create = 0
> for k in Precedence:
>
> if i != k[1]:
> create += 1
>
> if create == len(Precedence):
> Initial.append([i])
>
> cont = True
> while cont == True:
> count = 0
> successors = []
>
> for i in Initial:
>
> for k in Precedence:
> if i[-1] == k[0]:
> count += 1
> successors.append(k[1])
>
> if count == 1:
> i.append(successors[0])
>
> else:
> for num in range(1,count):
> Initial.append(i)
> ...
我想我会运行while循环,直到所有任务链都完成并实现'cont = false'。
任何帮助将不胜感激,谢谢。
解决方案
您可以使用有向图对任务优先关系进行建模。
每个节点对应一个任务。从节点 A 到节点 B 的连接意味着我们可以执行任务 A,然后执行任务 B。
然后问题就变成了在图中找到所有路径。
代码在 Internet 上很容易获得,用于对图形进行建模和确定路径。在这里我使用https://www.geeksforgeeks.org/find-paths-given-source-destination/
# https://www.geeksforgeeks.org/find-paths-given-source-destination/
from collections import defaultdict
#This class represents a directed graph (from https://www.geeksforgeeks.org/find-paths-given-source-destination/)
# using adjacency list representation
class Graph:
def __init__(self,vertices):
#No. of vertices
self.V= vertices
# 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 recursive function to print all paths from 'u' to 'd'.
visited[] keeps track of vertices in current path.
path[] stores actual vertices and path_index is current
index in path[]'''
def findAllPathsUtil(self, u, d, visited, path, results = set()):
# Mark the current node as visited and store in path
visited[u]= True
path.append(u)
# If current vertex is same as destination, then print
# current path[]
if u ==d:
results.add (tuple(path))
else:
# If current vertex is not destination
#Recur for all the vertices adjacent to this vertex
for i in self.graph[u]:
if visited[i]==False:
self.findAllPathsUtil(i, d, visited, path, results)
# Remove current vertex from path[] and mark it as unvisited
path.pop()
visited[u]= False
# Prints all paths from 's' to 'd'
def findAllPaths(self,s, d, results = set()):
# Mark all the vertices as not visited
visited = defaultdict(lambda: False) # [False]*(self.V)
# Create an array to store paths
path = []
# Call the recursive helper function to print all paths
return self.findAllPathsUtil(s, d,visited, path, results)
以上是创建有向图和打印节点之间所有路径的基本代码。
它稍作修改以允许节点从 1 而不是 0 编号以匹配任务的编号。
我们用它来:
- 从任务列表创建图表
- 查找图中节点之间的所有路径
def create_graph(lst):
" Creates graph from list of task dependencies "
# Find the number of tasks (i.e. maximum task index)
n = max(max(sublist) for sublist in lst)
# Convert task precedence pairs into graph
g = Graph(n)
for sublist in lst:
g.addEdge(sublist[0], sublist[1])
return g
Next 我们创建所有可能的任务链 将任务链放在 trie 树中(这样可以快速识别具有相同路径前缀的链)
# Trie code (see https://www.geeksforgeeks.org/trie-insert-and-search/)
_end = "_end"
def add_trie(lst, root):
for sublist in lst:
current_dict = root
for number in sublist:
current_dict = current_dict.setdefault(number, {})
current_dict[_end] = _end
return root
def get_longest_paths(root, results, path = []):
" Finds longest chains "
if len(root) == 1 and _end in root and len(path) > 1:
#print(f"adding {path} ") #{tuple(path[:-1])} {len(tuple(path[-1]))}")
results.add(tuple(path))
return
for k, v in root.items():
if len(root) == 1 or (len(root) > 1 and k != _end):
# Ingore key terminating key when we have other options since this means
# we are a prefix of a longest list
path.append(k)
get_longest_paths(v, results, path)
path.pop()
def create_task_chains(g, i):
" Creates all sequences of tasks starting at task i"
n = g.V # number of tasks which same as nodes in graph
results = set()
for j in range(n):
if i != j:
g.findAllPaths(i, j, results)
t = sorted(results, key=lambda x: (len(x), x))
return t
测试软件,使用原始列表
lst =[[1, 3],
[2, 3],
[3, 4],
[4, 5],
[4, 8],
[5, 6],
[6, 7],
[6, 10],
[7, 11],
[7, 12],
[8, 9],
[8, 11],
[9, 13],
[9, 10],
[11, 13],
[12, 15],
[13, 14],
[14, 16],
[14, 19],
[14, 20],
[15, 17],
[15, 22],
[16, 18],
[17, 18],
[17, 23],
[18, 25],
[19, 22],
[20, 21],
[20, 25],
[21, 22],
[21, 24],
[23, 25]]
# Create task dependency Graph
g = create_graph(lst)
# Number of tasks
number_tasks = max(max(sublist) for sublist in lst)
trie_tree = {}
for task in range(1, number_tasks + 1):
# Create task chains that start with task i
task_chains = create_task_chains(g, task)
# Create Trie Tree (i.e. prefix tree)
add_trie(task_chains, trie_tree)
# Find shortest paths
# Find the longest task chains (use set to remove repeated paths--only a few)
results = set() # Starting with a new set
get_longest_paths(trie_tree, results) # uses trie trie to ignore chains
# which are part of a longer chain
final_result = sorted(results, key = lambda x: (len(x), x), reverse = True)
print(final_result)
输出
[(2, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21,22),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 20,21, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 22),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(4, 5, 6, 7, 11, 13, 14, 20, 21, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(2, 3, 4, 8, 11, 13, 14, 20, 21, 24),
(2, 3, 4, 8, 11, 13, 14, 20, 21, 22),
(2, 3, 4, 8, 9, 13, 14, 20, 21, 24),
(2, 3, 4, 8, 9, 13, 14, 20, 21, 22),
(2, 3, 4, 5, 6, 7, 12, 15, 17, 23),
(2, 3, 4, 5, 6, 7, 12, 15, 17, 18),
(1, 3, 4, 8, 11, 13, 14, 20, 21, 24),
(1, 3, 4, 8, 11, 13, 14, 20, 21, 22),
(1, 3, 4, 8, 9, 13, 14, 20, 21, 24),
(1, 3, 4, 8, 9, 13,14, 20, 21, 22),
(1, 3, 4, 5, 6, 7, 12, 15, 17, 23),
(1, 3, 4, 5, 6, 7, 12, 15, 17,18),
(5, 6, 7, 11, 13, 14, 20, 21, 24),
(5, 6, 7, 11, 13, 14, 20, 21, 22),
(4, 5, 6, 7, 11, 13, 14, 19, 22),
(4, 5, 6, 7, 11, 13, 14, 16, 18),
(3, 4, 8, 11, 13, 14, 20, 21, 24),
(3, 4, 8, 11, 13, 14, 20, 21, 22),
(3, 4, 8, 9, 13, 14, 20, 21, 24),
(3, 4, 8, 9, 13, 14, 20, 21, 22),
(3, 4, 5, 6, 7, 12, 15, 17, 23),
(3, 4, 5, 6, 7, 12, 15, 17, 18),
(2, 3, 4, 8, 11, 13, 14, 19, 22),
(2, 3, 4, 8, 11, 13, 14, 16, 18),
(2, 3, 4, 8, 9, 13, 14, 19, 22),
(2, 3, 4, 8, 9, 13, 14, 16, 18),
(2, 3, 4, 5, 6, 7, 12,15, 22),
(1, 3, 4, 8, 11, 13, 14, 19, 22),
(1, 3, 4, 8, 11, 13, 14, 16, 18),
(1, 3,4, 8, 9, 13, 14, 19, 22),
(1, 3, 4, 8, 9, 13, 14, 16, 18),
(1, 3, 4, 5, 6, 7, 12, 15, 22),
(6, 7, 11, 13, 14, 20, 21, 24),
(6, 7, 11, 13, 14, 20, 21, 22),
(5, 6, 7, 11, 13, 14, 19, 22),
(5, 6, 7, 11, 13, 14, 16, 18),
(4, 8, 11, 13, 14, 20, 21, 24),
(4, 8, 11, 13, 14, 20, 21, 22),
(4, 8, 9, 13, 14, 20, 21, 24),
(4, 8, 9, 13, 14, 20, 21, 22),
(4, 5, 6, 7, 12, 15, 17, 23),
(4, 5, 6, 7, 12, 15, 17, 18),
(3, 4, 8, 11, 13, 14, 19, 22),
(3, 4, 8, 11, 13, 14, 16, 18),
(3, 4, 8, 9, 13, 14, 19, 22),
(3, 4, 8, 9, 13, 14, 16, 18),
(3, 4, 5, 6, 7, 12, 15, 22),
(8, 11, 13, 14, 20, 21, 24),
(8, 11, 13, 14, 20, 21, 22),
(8, 9, 13, 14, 20, 21, 24),
(8, 9, 13, 14, 20, 21, 22),
(7,11, 13, 14, 20, 21, 24),
(7, 11, 13, 14, 20, 21, 22),
(6, 7, 11, 13, 14, 19, 22),
(6, 7, 11, 13, 14, 16, 18),
(5, 6, 7, 12, 15, 17, 23),
(5, 6, 7, 12, 15, 17, 18),
(4,8, 11, 13, 14, 19, 22),
(4, 8, 11, 13, 14, 16, 18),
(4, 8, 9, 13, 14, 19, 22),
(4, 8, 9, 13, 14, 16, 18),
(4, 5, 6, 7, 12, 15, 22),
(11, 13, 14, 20, 21, 24),
(11, 13, 14, 20, 21, 22),
(9, 13, 14, 20, 21, 24),
(9, 13, 14, 20, 21, 22),
(8, 11, 13, 14, 19, 22),
(8, 11, 13, 14, 16, 18),
(8, 9, 13, 14, 19, 22),
(8, 9, 13, 14, 16, 18),
(7,11, 13, 14, 19, 22),
(7, 11, 13, 14, 16, 18),
(6, 7, 12, 15, 17, 23),
(6, 7, 12, 15, 17, 18),
(5, 6, 7, 12, 15, 22),
(2, 3, 4, 8, 9, 10),
(2, 3, 4, 5, 6, 10),
(1, 3, 4, 8, 9, 10),
(1, 3, 4, 5, 6, 10),
(13, 14, 20, 21, 24),
(13, 14, 20, 21, 22),
(11, 13, 14, 19, 22),
(11, 13, 14, 16, 18),
(9, 13, 14, 19, 22),
(9, 13, 14, 16, 18),
(7, 12, 15, 17, 23),
(7, 12, 15, 17, 18),
(6, 7, 12, 15, 22),
(3, 4, 8, 9, 10),
(3, 4, 5, 6, 10),
(14, 20, 21, 24),
(14, 20, 21, 22),
(13, 14, 19, 22),
(13, 14, 16, 18),
(12, 15, 17, 23),
(12, 15, 17, 18),
(7, 12, 15, 22),
(4, 8, 9, 10),
(4, 5, 6, 10),
(20, 21, 24),
(20, 21, 22),
(15, 17, 23),
(15, 17, 18),
(14, 19, 22),
(14, 16, 18),
(12, 15, 22),
(8, 9, 10),
(5, 6, 10),
(21, 24),
(21, 22),
(19, 22),
(17, 23),
(17, 18),
(16, 18),
(15, 22),
(9, 10),
(6, 10)]
推荐阅读
- vba - 在 Word 文档的页脚中访问 ContentControl(组合框)
- javascript - 制作JS游戏,在代码中添加其他对象的地方
- c# - C# linq IQueryable 多重过滤
- ios - FCM 推送通知声音不起作用 IOS(可能重复但没有任何解决方案)
- swift - 更新文档 Firebase 时无限循环
- python - 我想从网站下载所有 PDF,而不是手动下载,但出现 SSL 错误
- java - 休眠标准。用继承构造
- mongodb - 如何将 fetchNewObject 与 update.one ReactiveMongo 一起使用?
- python - 如何将 create-react-app 项目插入现有的 python/flask 应用程序
- forms - MailApp.sendEmail 谷歌应用表的语法和正确的功能位置?