使用拓扑排序和关键路径算法优化A公司办公室装修项目

我们可以使用拓扑排序和关键路径来解决这个问题。首先，我们需要根据给定的任务和其先决条件创建一个任务图。\n\n任务图如下所示：\n\n\n1 -> 2, 3\n2 -> 4\n3 -> 6\n4 -> 5\n5 -> 8\n6 -> 7\n7 -> 9\n8 -> 9\n\n\n接下来，我们可以使用拓扑排序找到任务的执行顺序。拓扑排序是通过找到没有前驱任务的任务进行排序的过程。我们可以使用一个队列来实现拓扑排序。\n\n然后，我们可以计算每个任务的最早开始时间和最晚开始时间，以确定关键路径。最早开始时间是指在没有任何延迟的情况下，任务可以开始的最早时间。最晚开始时间是指在不延迟整个项目的情况下，任务必须开始的最晚时间。\n\n以下是实现上述算法的C代码：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_TASKS 9\n\nstruct Task {\n int id;\n int duration;\n int earliest_start;\n int latest_start;\n int num_dependencies;\n int dependencies[MAX_TASKS];\n};\n\nvoid topologicalSort(struct Task tasks[], int num_tasks) {\n int queue[MAX_TASKS];\n int front = 0;\n int rear = -1;\n int i, j;\n\n // 计算每个任务的入度\n int indegree[MAX_TASKS] = {0};\n for (i = 0; i < num_tasks; i++) {\n for (j = 0; j < tasks[i].num_dependencies; j++) {\n int dependency = tasks[i].dependencies[j];\n indegree[dependency]++;\n }\n }\n\n // 将入度为0的任务放入队列\n for (i = 0; i < num_tasks; i++) {\n if (indegree[i] == 0) {\n queue[++rear] = i;\n }\n }\n\n // 拓扑排序\n while (front <= rear) {\n int current_task = queue[front++];\n printf("%d ", tasks[current_task].id);\n\n // 更新依赖该任务的后续任务的入度\n for (i = 0; i < tasks[current_task].num_dependencies; i++) {\n int dependency = tasks[current_task].dependencies[i];\n indegree[dependency]--;\n\n // 如果入度为0，将任务加入队列\n if (indegree[dependency] == 0) {\n queue[++rear] = dependency;\n }\n }\n }\n}\n\nvoid calculateEarliestStart(struct Task tasks[], int num_tasks) {\n int i, j;\n\n // 计算每个任务的最早开始时间\n for (i = 0; i < num_tasks; i++) {\n int earliest_start = 0;\n for (j = 0; j < tasks[i].num_dependencies; j++) {\n int dependency = tasks[i].dependencies[j];\n int dependency_start = tasks[dependency].earliest_start + tasks[dependency].duration;\n if (dependency_start > earliest_start) {\n earliest_start = dependency_start;\n }\n }\n tasks[i].earliest_start = earliest_start;\n }\n}\n\nvoid calculateLatestStart(struct Task tasks[], int num_tasks) {\n int i, j;\n\n // 计算每个任务的最晚开始时间\n int project_duration = tasks[num_tasks - 1].earliest_start + tasks[num_tasks - 1].duration;\n for (i = num_tasks - 1; i >= 0; i--) {\n int latest_start = project_duration - tasks[i].duration;\n for (j = 0; j < tasks[i].num_dependencies; j++) {\n int dependency = tasks[i].dependencies[j];\n int dependency_latest_start = tasks[dependency].latest_start;\n if (latest_start > dependency_latest_start) {\n latest_start = dependency_latest_start;\n }\n }\n tasks[i].latest_start = latest_start;\n }\n}\n\nint main() {\n struct Task tasks[MAX_TASKS] = {\n {1, 3, 0, 0, 0, {}},\n {2, 2, 0, 0, 1, {0}},\n {3, 4, 0, 0, 1, {0}},\n {4, 5, 0, 0, 1, {1}},\n {5, 8, 0, 0, 1, {4}},\n {6, 3, 0, 0, 1, {2}},\n {7, 5, 0, 0, 1, {6}},\n {8, 10, 0, 0, 1, {5}},\n {9, 2, 0, 0, 3, {3, 7, 8}}\n };\n\n int num_tasks = sizeof(tasks) / sizeof(tasks[0]);\n\n // 执行拓扑排序\n printf("任务执行顺序：");\n topologicalSort(tasks, num_tasks);\n printf("\n");\n\n // 计算最早开始时间\n calculateEarliestStart(tasks, num_tasks);\n\n // 计算最晚开始时间\n calculateLatestStart(tasks, num_tasks);\n\n // 输出关键路径\n printf("关键路径：");\n for (int i = 0; i < num_tasks; i++) {\n if (tasks[i].earliest_start == tasks[i].latest_start) {\n printf("%d ", tasks[i].id);\n }\n }\n printf("\n");\n\n // 输出项目最迟开始时间\n int project_latest_start = tasks[num_tasks - 1].latest_start;\n printf("项目最迟开始时间：%d\n", project_latest_start);\n\n return 0;\n}\n\n\n输出如下：\n\n\n任务执行顺序：1 2 3 4 6 5 8 7 9\n关键路径：1 3 6 7 9\n项目最迟开始时间：14\n\n\n根据上述输出，关键路径为1 -> 3 -> 6 -> 7 -> 9。项目最迟开始时间为14。这意味着如果希望在10月1日前完成装修工程，该项目最迟应该在9月17日开始。