在写项目管理方面的软件，求关键路径的算法。有相关例子吗？
--------------------编程问答-------------------- 没有约束条件，怎么排列，如果每件事情的都是一件，总工时都将相同 --------------------编程问答-------------------- 用C#写一个using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
interface ITask
{
int During { get; }
IEnumerable<TaskItem> KeyPaths { get; }
}
class TaskItem : ITask
{
public string Name { get; set; }
public int During { get; set; }
public IEnumerable<TaskItem> KeyPaths { get { return new TaskItem[] { this }; } }
}
class TaskGroup : ITask
{
public List<ITask> Tasks { get; set; }
public int During { get { return Tasks.Max(x => x.During); } }
public IEnumerable<TaskItem> KeyPaths { get { return Tasks.OrderByDescending(x => x.During).First().KeyPaths; } }
}
class TaskString : ITask
{
public List<ITask> Tasks { get; set; }
public int During { get { return Tasks.Sum(x => x.During); } }
public IEnumerable<TaskItem> KeyPaths { get { return Tasks.SelectMany(x => x.KeyPaths); } }
}
static class ITaskHelper
{
public static TaskItem StartWith(string name, int during)
{
return new TaskItem() { Name = name, During = during };
}
public static TaskGroup And(this ITask thistesk, ITask tesk)
{
if (thistesk is TaskGroup)
{
(thistesk as TaskGroup).Tasks.Add(tesk);
return thistesk as TaskGroup;
}
return new TaskGroup() { Tasks = new List<ITask>() { thistesk, tesk } };
}
public static TaskGroup And(this ITask thistesk, string name, int during)
{
return ITaskHelper.And(thistesk, new TaskItem() { Name = name, During = during });
}
public static TaskString Then(this ITask thistesk, ITask tesk)
{
if (thistesk is TaskString)
{
(thistesk as TaskString).Tasks.Add(tesk);
return thistesk as TaskString;
}
return new TaskString() { Tasks = new List<ITask>() { thistesk, tesk } };
}
public static TaskString Then(this ITask thistesk, string name, int during)
{
return ITaskHelper.Then(thistesk, new TaskItem() { Name = name, During = during });
}
}
class Program
{
static void Main(string[] args)
{
var t = ITaskHelper.StartWith("找茶叶", 1).And("洗茶碗", 3).And(ITaskHelper.StartWith("洗茶壶", 2).Then("烧开水", 10)).Then("泡茶", 10).And("招呼客人聊天", 5).Then("上茶", 1);
Console.WriteLine(string.Join("->", t.KeyPaths.Select(x => x.Name)));
}
}
}
洗茶壶->烧开水->泡茶->上茶
Press any key to continue . . .
VB能写得更优雅么？不服来辩。 --------------------编程问答--------------------
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
interface ITask
{
int During { get; }
IEnumerable<TaskItem> KeyPaths { get; }
}
class TaskItem : ITask
{
public string Name { get; set; }
public int During { get; set; }
public int Order { get; set; }
public IEnumerable<TaskItem> KeyPaths { get { return new TaskItem[] { this }; } }
public override string ToString()
{
return string.Format("{0}({1})", Name, During);
}
}
class TaskGroup : ITask
{
public List<ITask> Tasks { get; set; }
public int During { get { return Tasks.Max(x => x.During); } }
public IEnumerable<TaskItem> KeyPaths { get { return Tasks.OrderByDescending(x => x.During).First().KeyPaths; } }
public override string ToString()
{
return "[" + string.Join(" / ", Tasks.Select(x => x.ToString())) + "]";
}
}
class TaskString : ITask
{
public List<ITask> Tasks { get; set; }
public int During { get { return Tasks.Sum(x => x.During); } }
public IEnumerable<TaskItem> KeyPaths { get { return Tasks.SelectMany(x => x.KeyPaths); } }
public override string ToString()
{
return string.Join(" -> ", Tasks.Select(x => string.Format("{0}", x.ToString())));
}
}
static class ITaskHelper
{
public static TaskItem StartWith(string name, int during)
{
return new TaskItem() { Name = name, During = during };
}
public static TaskGroup And(this ITask thistesk, ITask tesk)
{
if (thistesk is TaskGroup)
{
(thistesk as TaskGroup).Tasks.Add(tesk);
return thistesk as TaskGroup;
}
return new TaskGroup() { Tasks = new List<ITask>() { thistesk, tesk } };
}
public static TaskGroup And(this ITask thistesk, string name, int during)
{
return ITaskHelper.And(thistesk, new TaskItem() { Name = name, During = during });
}
public static TaskString Then(this ITask thistesk, ITask tesk)
{
if (thistesk is TaskString)
{
(thistesk as TaskString).Tasks.Add(tesk);
return thistesk as TaskString;
}
return new TaskString() { Tasks = new List<ITask>() { thistesk, tesk } };
}
public static TaskString Then(this ITask thistesk, string name, int during)
{
return ITaskHelper.Then(thistesk, new TaskItem() { Name = name, During = during });
}
}
class AutoSchedule
{
List<TaskItem> Tasks { get; set; }
Dictionary<TaskItem, List<TaskItem>> DependList { get; set; }
private AutoSchedule()
{
Tasks = new List<TaskItem>();
DependList = new Dictionary<TaskItem, List<TaskItem>>();
}
public static AutoSchedule New() { return new AutoSchedule(); }
public AutoSchedule DefineTask(string name, int during)
{
if (Tasks.Any(x => x.Name == name)) throw new ArgumentException(name + " is already in list");
Tasks.Add(new TaskItem() { Name = name, During = during });
return this;
}
bool AIsRequiredB(string a, string b)
{
if (DependList.Keys.Any(x => x.Name == a))
return DependList[DependList.Keys.Single(x => x.Name == a)].Any(x => x.Name == b);
return false;
}
IEnumerable<string> whichRequiresA(string a)
{
if (DependList.Keys.Any(x => x.Name == a))
return DependList[DependList.Keys.Single(x => x.Name == a)].Select(x => x.Name);
return new string[] { };
}
bool detectDependLoop(string task, string requiredtask)
{
return task == requiredtask || AIsRequiredB(task, requiredtask) || whichRequiresA(task).Any(x => detectDependLoop(x, requiredtask));
}
public AutoSchedule DefineDepend(string name, params string[] required)
{
if (Tasks.All(x => x.Name != name) || required.Any(x => Tasks.All(y => y.Name != x)))
throw new InvalidOperationException("no such a task");
if (required.Any(x => detectDependLoop(x, name)))
throw new InvalidOperationException("loop require detected");
if (DependList.Keys.All(x => x.Name != name))
DependList.Add(Tasks.Single(x => x.Name == name), new List<TaskItem>());
DependList[DependList.Keys.Single(x => x.Name == name)]
.AddRange(required.Select(x => Tasks.Single(y => y.Name == x)).Where(y => !DependList[DependList.Keys.Single(x => x.Name == name)].Contains(y)));
return this;
}
void decOrder(TaskItem task, int newOrder)
{
task.Order = newOrder < task.Order ? newOrder : task.Order;
foreach (var t in DependList.Where(x => x.Value.Contains(task)).Select(x => x.Key))
decOrder(t, newOrder - 1);
}
public ITask ScheduleIt()
{
Tasks.ForEach(x => x.Order = Tasks.Count());
foreach (var item in DependList)
{
decOrder(item.Key, item.Value.Min(x => x.Order) - 1);
}
TaskString ts = new TaskString();
ts.Tasks = new List<ITask>();
foreach (var item in Tasks.GroupBy(x => x.Order).OrderByDescending(x => x.Key))
{
TaskGroup tg = new TaskGroup();
tg.Tasks = new List<ITask>();
tg.Tasks.AddRange(item);
ts.Tasks.Add(tg);
}
return ts;
}
}
class Program
{
static void Main(string[] args)
{
var t = AutoSchedule.New()
.DefineTask("a", 5)
.DefineTask("b", 3)
.DefineTask("c", 6)
.DefineTask("d", 2)
.DefineTask("e", 5)
.DefineTask("f", 9)
.DefineTask("g", 3)
.DefineTask("h", 1)
.DefineTask("i", 11)
.DefineTask("j", 4)
.DefineDepend("f", "c")
.DefineDepend("a", "g")
.DefineDepend("i", "a", "d")
.ScheduleIt();
Console.WriteLine(t);
Console.WriteLine(string.Join("->", t.KeyPaths.Select(x => x.Name)));
}
}
}
[b(3) / c(6) / d(2) / e(5) / g(3) / h(1) / j(4)] -> [a(5) / f(9)] -> [i(11)]
c->f->i
Press any key to continue . . . --------------------编程问答--------------------
这是来砸场子的么
--------------------编程问答--------------------
这有什么复杂？遍历所有任务，将任务归到不同的路径去。某些路径可能只有一个任务，另一些有多个任务。求出各个路径的最大长度，找到最长路径就是了。
因为扫描中可能遇到有些任务的前任务还没有找到，因此，可能需要遍历多次。直至“任务池”中没有任务为止。
路径可能是树型结构。添加任务的时候，就是对树进行处理。最后求出路径的最大长度。
10 个任务和 10000 个任务的思路是一样的。
--------------------编程问答--------------------
没仔细考虑过不要轻易发表意见。 --------------------编程问答-------------------- 首先谢谢大家的发言。经过一段时间思考，我发现原来关键路径的问题是会随着子任务的增加变得越来越复杂。如果建立象MS project 这样的甘特图才能简单的体现出关键路径。但是甘特图控件一直没有找到。 --------------------编程问答-------------------- 做成ms project那样，gantt chart控件一搜一大把 --------------------编程问答-------------------- 这是拼写错误么？
if (thistesk is TaskString)
优雅是个个人感觉的事情
--------------------编程问答--------------------
是的，拼写错误。不过用VS真的不用担心，直接用重构-重命名就改过来了。 --------------------编程问答--------------------
重构-重命名 是什么
我都是search ,replace --------------------编程问答--------------------
直接修改一处变量，VS会在这个变量下加上一个小红线，点一下，弹出菜单，选择重命名，收工。 --------------------编程问答-------------------- 请热心人,帮忙看看下面的求助吧!
请高手帮忙修正一个注册表模块!已经做成工程文件,有详细的实例的!
http://bbs.csdn.net/topics/390428796 --------------------编程问答--------------------
这样的话工程中所有的变量名称都会被替换？ --------------------编程问答--------------------
所有代表这个变量的变量名都会被替换。比如你有2个方法，每个方法都定义了这么一个局部变量，那么只有当前的那个会被替换。 --------------------编程问答--------------------
其实这很好理解，C#和VB不同的是，前者微软开放了编译器的每个编译步骤，比如词法分析、语法分析、语义分析、中间代码生成。所以给VS编写C#插件很容易，你可以用词法分析的结果做代码高亮，用语法分析的结果做代码折叠，用语义分析的结果做重构（对于重命名来说，无非就是修改抽象语法树，AST的一个变量声明的节点），还可以控制中间代码生成实现AOP动态拦截。当然了，如果能够开源，那就更好了。
而给VB6开发插件，面对实现完全不透明且破烂不堪的VB语言，大部分的插件也就只能做做代码生成或者很低级的界面简化操作，要不就是错漏百出。
补充：VB , 基础类
