※ 引述《yhn0tgb60 (呦厚厚)》之铭言： : 我想也许他们有更好的方法在处里这个问题 ??? : 想和大家讨论一下这个问题 谢谢了 ^^ 我觉得以上的分析本身走错了方向. 因为你分析出来的, 是忽视了以下这些东西: 1. 模拟城市有电量的限制的, 并不是只要连到发电厂就有电, 而 是要发电厂支持得住发电量 2. 在模拟城市表现出来的是发电厂会先提供更接近区的电力. 3. 可以有两个不同地方的发电厂, 所以终点可以有两个, 但到底 决定由谁供电却是谜题. 4. 一个较近的电厂的供电额满, 还是会使用较远的电厂, 所以也 不是单纯找最近的电厂 因此, 最基本的问题是, 「哪个是起点, 哪个是终点」, 这件事根 本就无法在一开始时决定, 既然连起点和终点都不明白, 我们不需 要假定这个系统是建立在「路径搜寻」之上的. 而我认为最简单的做法就是「颜料渗透」法. 在古早时代的语言 BGI 带的绘图指令中, 已经有 floodfill 这种 指令, 简单来说, 就是填色. 把一个区块填满, 直至碰到边为止. 这种指令在 286 的电脑上也不会用很多的时间, 而运作的方式很 简单, 就是从一点开始不断扩张出去, 直至填完为止. 可以用 recursion 或者 BFS 类似的方式达成. 然则, 你把电网想像成一幅图的话, 运作方式也是相同的. 很简单 , 由电厂开始, 你只要加一个参数是「电量」, 每经过一个会使用 电的点处, 就减去相对的数量, 直至填满或者数值不足为止. 你可以想像成, 每座电厂相当於一瓶滚珠, 而电网则是一个迷宫, 你做的事情就是在迷宫几点倒下滚珠, 随他们自己滚动而已. 你有几座电厂, 就做几次, 模拟城市一当中没有小型电厂 (风电, 水电) , 只有大型电厂 (煤电, 核电) , 所以电厂的数量不会太多 , 应该不会超过十个. 相连的电厂更可以直接将电量相加计算. 那麽一次的工作量, 大概就是等於电厂数 x floodfill 的工作量, 另外, 因为不用显以及有限额的关系, 所以工作量应该比 floodfill 要低. 而模拟城市本身的更新速度其实并不很频繁, 一 个月可能只更新五次左右而已. 那是 286 也可以支持得来的. 至於你开电缆, 关电缆, 也不会有影 响, 运算不应该在你建筑或者拆除时进行, 而应该用 timer 计时 器定期进行. 所以这并非一个「searching」动作, 而是一个「floodfill」的动 作, searching 需要找最短的路线, 而你 floodfill 根本就不用顾 虑这问题, 只要节省了「寻找最短路线」这个要求, 你就会发觉你 不需要用那麽复杂的 algorithm 了. 一开始把这问题想成是「路径寻找」的问题就是盲点, 那会误导你 解决问题的方向的. -- 基於饮水思源的理念, 还是该打的广告, hkday.net --- 硕果仅存还愿意和其他地区转信的香港 BBS -- 另外, DOS 时代编释出来的程式, 效能是高於 Windows 时代的. 特 别是有可能在里面使用了组合语言, 其实 286 也是一枚很快的 CPU , 只是不可能受得住现代 OS 和高阶语言一层又一层的剥削而已... 只要不滥用高阶的 call, 你会发觉即使 286 也是很见用的. 老实 说自从我拥有人生第一部 486 之後, 我从没觉得过电脑慢... 那麽更简单. 就是相等於一次 floodfill. 如果只是这样, 只做一次 BFS 就足够了. 因为 BFS 中间产生的数据会显示所有连得到去的点. ※ 编辑: chenglap 来自: 218.252.90.21 (07/10 00:44)