LINUX.ORG.RU

Как рассчитать время изготовления по блок-схеме такой ?

 ,


0

2

Подскажите как сделать формат файла для рассчета времени изготовления по подобным блок-схемам https://ibb.co/h84LqPT Каждый блок на схеме имеет время свое, задается пользователем, блок-схему может менять пользователь. Блоки на одном уровне могут исполняться параллельно, блоки, в которые входят стрелки, только по готовности тех, откуда стрелки. Как бы ее связи записать в файл ? Есть ли примеры как такое по-проще запрогать. Нужно рассчитать минимальное время изготовления финального блока.



Последнее исправление: user2132 (всего исправлений: 2)

Что-то типа этого? https://i.imgur.com/MJAoQO8.png

результат
    шаг 1
        шаг 1.1
    шаг 2
        шаг 2.1
        шаг 2.2
            шаг 2.2.1
                шаг 2.2.1.1
                шаг 2.2.1.2
    шаг 3

Можно брать любой стандартный формат, поддерживающий иерархию. Например XML.

anonymous
()

Обходишь граф рекурсивно, начиная с финального блока. В каждом блоке значением является время текущего блока плюс максимум времени из всех линий, входящих в этот блок.

i-rinat ★★★★★
()

Пользователь случайно не может понаделать в блок-схеме циклов?

Мне кажется, тебе нужно построение списка всех уникальных путей по ориентированному графу, от каждого корневого узла (у которых нет входов), до каждого концевого (у которых нет выходов).
И отдельно выловить пути с циклами.
Время считать для каждого пути без циклов, а для путей с циклами возвращать бесконечность любым удобным способом.


Время выполнения любой из задач одного уровня это время выполнения самой длинной из них, или они независимы?

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

blexey ★★★★★
()
Ответ на: комментарий от blexey

Блок схемы будут без циклов, но могут быть вот с такими закрученными связями кто от кого зависит.

user2132
() автор топика
Ответ на: комментарий от i-rinat

А можно пример обхода графа рекурсивно с финального блока ? Я думал вариант от верхних блоков, время которых можно сразу посчитать и после считать время блоков, которые зависят от верхних.

user2132
() автор топика
Ответ на: комментарий от blexey

Время выполнения любой из задач одного уровня это время выполнения самой длинной из них, то есть максимум. Они независимы и могут параллельно выполняться.

user2132
() автор топика
Ответ на: комментарий от user2132
фн время_узла(узел):
    аккумулятор = 0
    для каждого узла `уз`, втекающего в `узел`:
        если время_узла(уз) > аккумулятор:
            аккумулятор = время_узла(уз)
    вернуть (узел.своё_время + аккумулятор)
i-rinat ★★★★★
()

Не изобретай велосипеды. Есть такая штука, называется «сетевое планирование и управление». Как раз то, что тебе надо. Целую теорию написали, как это считать. Докинь его кстати в теги, если можешь. Может и придёт кто, готовый разжевать на пальцах всё, что выше не разжевали.

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 3)
Ответ на: комментарий от i-rinat

А тут точно =, а не +=.

аккумулятор = время_узла(уз)

Мне суммировать ведь нужно от финального узла.

user2132
() автор топика
Ответ на: комментарий от user2132
+------------+    +---------------+
|            |    |               |
|    1 сек   |    |    2 сек      |
|            |    |               |
+-----+------+    +-------+-------+
      |                   |
      v                   v
+---------------------------------+
|                                 |
|              3 сек              |
|                                 |
+---------------------------------+

Когда обрабатываешь узел 3, нужно выбрать максимальное время из 1 и 2, а не их сумму, потому что 1 и 2 могут начаться одновременно, и их общее время параллельного исполнения будет 2 секунды, а не 1 + 2. Максимум складываешь с длительностью узла 3, и так получается общее время исполнения узлов 1, 2 и 3.

Попробуй на бумаге нарисовать разные схемы и посчитать вручную. Сразу станет понятнее.

i-rinat ★★★★★
()
Ответ на: комментарий от user2132

Нет. Вероятно ты создать не можешь просто - звёзд мало.

peregrine ★★★★★
()
Ответ на: комментарий от i-rinat

А можешь еще подсказать тут BFS алгоритм в ширину нужно использовать для задач подсчета ? DFS тут не подходит ?

user2132
() автор топика
Ответ на: комментарий от user2132

Если сможешь придумать, как через DFS организовать, значит подходит. Если не сможешь, значит нет.

i-rinat ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.