Формирование цепочки задач с непосредственным приоритетом - PullRequest
Новая
       0

Формирование цепочки задач с непосредственным приоритетом

0 голосов
/ 20 сентября 2019

Я пытаюсь сформировать цепочку задач (проиндексированных по номерам) с учетом списка пар задач.

В следующем списке: 

[[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, и я столкнулся с некоторыми трудностями.У меня возникли проблемы с моей нынешней идеей: я формирую новые списки цепочек задач с самого начала и дублирую их, когда у задачи более одного преемника.Однако я не уверен, как обеспечить, чтобы каждый вновь продублированный список получал своего преемника, и как снова и снова запускать каждый список.

Следующий код - моя текущая попытка: 

> 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'.

Любая помощь будет принята с благодарностью, спасибо.

1 Ответ

0 голосов
/ 20 сентября 2019

Вы можете использовать ориентированный граф для моделирования отношений приоритета задачи.

Каждый узел соответствует задаче.Соединение от узла A к узлу B означает, что мы можем выполнить задачу A, за которой следует задача B.

Затем возникает проблема с нахождением всех путей на графике.

Код легко доступен в Интернетемоделировать графики и определять пути.Здесь я использую 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, чтобы соответствовать нумерации задач.

Мы используем его для:

  1. Создатьграфик из списка задач
  2. Найти все пути между узлами на графике 

    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

Далее Мы создаем все возможные цепочки задач Поместите цепочки задач в древовидную структуру (это позволяетбыстрая идентификация цепей с одинаковым префиксом пути) 

# 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)]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...