• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Using simulated annealing to minimize the cost of multipoint lines in centralized computer networks: Implementation for Windows 3.1(TM).
【24h】

Using simulated annealing to minimize the cost of multipoint lines in centralized computer networks: Implementation for Windows 3.1(TM).

机译：在中央计算机网络中使用模拟退火来最大程度地减少多点线路的成本：Windows 3.1™的实现。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We focus on a problem encountered when designing centralized telecommunications networks, namely, the terminal layout problem. Given each terminal's geographical location, the problem consists in creating multipoint lines rooted at a central site (typically a concentrator) in order to save on connection costs. Well-known multipoint line topologies are the tree, the bus, and the loop. When terminals are assigned a weight representing the average traffic amount exchanged with the central site and lines are constrained by the amount of traffic they can carry, the tree-topology problem is referred to as the Capacitated Minimum Spanning Tree (CMST) problem. Algorithms that generate solutions for CMST problems create tree structured networks but can also be used to produce bus structured networks by imposing additional constraints. As for the loop topology, the problem is analogous to the Vehicle Routing problem found in Operation Research.;These problems are NP-Complete. Finding an optimal solution in an acceptable amount of time is, therefore, unlikely due to the exponential growth in complexity relative to problem size. Nevertheless, techniques yielding exact solutions have been developed but are limited to networks of no more than, say, 50 terminals. Alternatively, heuristics solve the problem to near-optimality with acceptable computational effort.;We designed applications with graphical output capabilities for Windows 3.1
机译：我们集中在设计集中式电信网络时遇到的问题，即终端布局问题。给定每个终端的地理位置，问题在于创建以中心站点（通常为集中器）为根的多点线路，以节省连接成本。众所周知的多点线拓扑是树，总线和环路。当为终端分配代表与中心站点交换的平均业务量的权重，并且线路受到它们可以承载的业务量的限制时，树形拓扑问题称为“容量最小生成树（CMST）”问题。生成CMST问题解决方案的算法会创建树状结构的网络，但也可以通过施加附加约束来用于生成总线结构的网络。至于环路拓扑，该问题类似于在运筹学中发现的车辆路径问题。这些问题是NP-Complete。因此，由于复杂度相对于问题大小呈指数增长，因此不可能在可接受的时间内找到最佳解决方案。然而，已经开发出产生精确解决方案的技术，但仅限于不超过50个终端的网络。另外，启发式方法可以通过可接受的计算工作量将问题解决到近乎最佳状态。

著录项

  • 作者

    Tomiuk, Daniel B.;

  • 作者单位

    Concordia University (Canada).;

  • 授予单位 Concordia University (Canada).;
  • 学科 Business Administration Management.;Engineering System Science.
  • 学位 M.Sc.
  • 年度 1997
  • 页码 148 p.
  • 总页数 148
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号