图论

航空路线问题

题目描述

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 (1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。 (2)除起点城市外,任何城市只能访问 1 次。 对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。 (更多…)

DefFrancis
图论

太空飞行计划问题

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={I1,I2,…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。 对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。 (更多…)

DefFrancis