Communication Network-1and2-Basic Problems

通信网络里的一些基本问题

  • Shortest path problem(最短路径问题)
  • Max flow problem(最大流量问题)
  • Minimum-cost flow problem(最小损耗流量问题)
  • Disjoint path routing problem(不相交路径问题)
  • Basic Problem
    • Shortest path problem(最短路径问题)
      • Dijkstra’s algorithm(迪克斯特拉算法)
      • Bellman-Ford algorithm(贝尔曼-福特算法)
    • Max flow problem(最大流量问题)
      • Ford–Fulkerson algorithm(贪婪算法)
    • Minimum-cost flow problem(最小成本流问题)
      • Cycle-canceling algorithm(Klein’s algorithm.)
    • Disjoint path routing problem(不相交路径问题)



我只是一个勤劳的翻译工



Lecture

L1

L2

通信网络模型

  • 通信网络由节点和链路组成。

  • 两个节点之间的箭头是这些节点的连接,称为链路。 流量的方向是从箭头的尾部到箭头的头部。

  • 每个链路都有其方向的网络,用相应的箭头表示。

  • 每个链路上的数字表示其链路成本。

  • 如果连接仅由一条线而不是箭头表示,则流量可以在链路的两个方向上流动。 在两个方向上流经该链路的网络称为无向图。

Shortest path problem(最短路径问题)

  • 从源节点到目标节点的损耗最小的路径称为最短路径。

  • 最短路径是通过考虑网络中的链路成本来确定的。 此问题称为最短路径问题。

  • 解决了问题并获得了解决方案,如图2所示。从节点1到节点6的最短路径为1→2→5→6,则路径成本(即路径上链路成本的总和)为$3 + 4 + 6 = 13$。

Dijkstra’s algorithm(迪克斯特拉算法)

一种查找从源节点到目标节点的最短路径的算法,其中每个链路成本都不为负

概述

  • 网络中的节点分为三种类型的节点,访问ing节点(表示当前选中的这个节点,已被前面的所有相邻节点访问,正要去访问未访问节点),已访问节点(已访问过其他所有相邻节点的节点)和未访问节点(未被全部路径访问的节点)。除了源节点和目标节点,每一个节点都会经历从$未访问节点\to 访问ing节点\to已访问节点$——个人总结

  • 在初始阶段,源节点被设置为访问ing节点,其他节点被设置为未访问节点。将源节点的距离设置为$0$,将所有其他节点的距离设置为$\infty$。

  • $访问ing节点的距离D(j)=已访问节点的距离D(j-1)+已访问节点和此访问ing节点之间的链路成本cost(j-1\to j)$

  • 接下来,选择距离最短的未访问节点,以在下一次迭代中访问。 重复该过程,直到网络中的每个节点都成为已访问节点为止。 此过程产生从源节点到网络中所有节点的最短路径。

具体过程

(1)设置从源节点到每个节点的距离为$\infty$,源节点的距离设为$0$;

(2)将源节点标记为访问ing节点,其他节点标记为未访问节点;

(3)对于访问ing节点,通过将当前节点和每个相邻节点之间的链路成本加到当前节点的距离上,此结果作为到未访问的相邻节点的距离。 如果这个距离小于先前记录的距离,就更新距离为这个值。 对于距离已更新的未访问节点,记录从源节点经过前一跳节点的路径。 访问ing节点成为已访问节点。 注意,如果一个节点是已访问的节点,则距离不会被更新,并且保证是最短路径树的一部分。

(4)在未访问的节点中选择距离最短的未访问的节点,并将其设置为访问ing节点。

(5)如果将网络中的所有节点都标记为已访问节点,则过程结束。 否则,从步骤3开始重复相同的过程。


Bellman-Ford algorithm(贝尔曼-福特算法)

它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于Dijkstra’s algorithm(迪克斯特拉算法)的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达O(VE)。但算法可以进行若干种优化,提高了效率。

概述

  • 如果网络中没有负环路,则可以将Bellman-Ford算法应用于包含负链路成本的网络。

  • 如果网络中存在负环路,则无法获得正确的答案。 在负循环中,每次迭代的无限距离之和变小。因此,无法确定最短路径。

  • 节点不按访问分类。 每个节点的距离最多可以更改$N-1$次以获得最短路径,其中$N$是网络中的节点数。

具体过程

(1)将源节点到除源节点之外的每个节点的距离设置为$\infty$,并将源节点的距离设置为$0$。

(2)在每个节点上,选择一个相邻节点,以使该相邻节点的距离与从该相邻节点到其自身节点的链路成本之和最小。 将所选的相邻节点设置为前一跳节点。

(3)如果将步骤2重复$N -1$次,则该过程结束。 否则,请重复步骤2。

Max flow problem(最大流量问题)

  • 网络需要考虑每个链路的容量。
  • 每个链路上的数字表示链路容量;在每个链路上流动的流量不超过链路的容量。
  • 我们可以从节点1发送到节点6的最大流量是多少?流量应在哪条路径上传输?此问题称为最大流量问题。
  • 图4显示了此问题的解决方案。 从节点1到节点6的最大流量为$v = 195$,并且由五个路径组成,它们的对应流量为$v_1$至$v_5$。

Ford–Fulkerson algorithm(贪婪算法)

概述

  • 考虑给出了链路容量的网络。

  • 首先,选择链路源和目标节点的路径,并在约束下分配最大可能的流量,即通过每个链路的流量不超过链路容量。 得到的路径称为增强路径。

  • 考虑了在增强路径设置后具有剩余功能的网络。 这称为剩余网络。 对于剩余网络,如果可能,则会为额外的流量分配,并且将其添加到现有流量中。更新剩余网络。

  • 重复此过程,直到无法分配其他额外的流量。 完成后,分配的流量流是增强路径上的流量之和。

具体过程

步骤1:将每个流的流量容量设置为0。

步骤2:根据当前流程创建残留网络。

步骤3:对于在步骤2中定义的剩余网络,如果有任何路径,则从源节点传输到目标节点的任何流量,请选择它。 将最大可能的流量分配给所选路径的所选路径,通过每个链路的流量卷不超过链路容量。 分配的流量被添加到电流流,并且重新进入步骤2。 否则,转到第4步。

步骤4:网络中当前流量的流量变为最大流量问题的解决方案。 这个过程结束了。

Minimum-cost flow problem(最小成本流问题)

  • 网络会考虑每个链路的成本和容量。

  • 每个链路上的数字代表链路成本和链路容量。 流量不能超过链路容量。

  • 将需要从源节点(节点1)传输到目标节点(节点6)的流量设置为$v =180$。如何以最小的成本将所需的流量从节点1发送到节点6? 此问题称为最小成本流问题。

  • 在最低成本流中,每个链路的所需成本定义为$链路成本\times链路上流过的流量$。 我们将流量从节点1发送到节点6的路径上的成本总和最小化。

  • 流量为$v$的流量分为从$v_1$到$v_5$的5条路径。

  • 总流量为$v = v_1 + v_2 + v_3 + v_4 + v_5 = 15 + 10 + 100 + 25 + 30 = 180$。

  • 总成本为$3180$。

    • cost=15*(3+4+6)...
          +10*(3+4+10)...
          +100*(5+10)...
          +25*(9+6+10)...
          +30*(9+14)

Cycle-canceling algorithm

Relationship among three problems

  • 最短路径问题和最大流量问题是最小成本流量问题的特殊情况。

  • 最小成本流量问题可以解决最短路径问题。

    • 我们认为在最小成本流量问题中只考虑链接成本。
    • 每个链路的容量设置为1。
    • 假设流量需求为1。
  • 最小成本流量问题可以解决最大流量问题。

不相交路径问题

  • 寻找可靠的通信的不相交的路径是必要的。

  • 一组节点不相交的路径彼此不共享任何公共节点,但源节点和距离节点除外。而一组链路不相交的路径彼此不共享任何公共链路。 一组链路不相交路径是节点不相交路径的子集。

  • 考虑找到总成本最小的一组不相交的路线的基本问题,即MIN-SUM问题。

打赏
  • Copyrights © 2020-2021 haoyu fang
  • 访问人数: | 浏览次数:

请我喝杯啤酒吧~

支付宝
微信