薪资至少10K的一道题,你能拿下吗

2020-03-29 21:38栏目:科技中心

他们用伦敦地铁数据进行了模拟。结果发现,当所有乘客都选最短路线出行时,如果在乘客所选路线之间加入斥力,而且乘客接受了建议路线,平均路线长度会增加6%,但却能换来节约20%的预设成本。

  3)最优路线:换乘次数最少的最短路线(可能有多条路线)[本题20分,不计入总分]

要找到一条最优路线是容易的,但要找到多条路线的最优组合就比较困难。从互联网即时通信、对等网络,到地铁交通、机场飞行管理、供水系统、传感器部署、军事后勤运输、旅行路线计划等,寻找全局最优路线组合的方法应用广泛。然而,要实现全局路线组合最优化,在计算上极为复杂,要考虑到所有路线的可能性。目前的一般路径算法是让每条路线单独达到最优,而最后的全局方案往往无法达到最优。

 

“虽然用物理学工具解决分析系统的问题确实困难,但聚合体和路径之间的相似性却很容易理解。”研究员杨智浩解释说,“一个聚合体分子是一条长长的高分子链,就像一条有两个末端的绳子。假设用一个高分子来表示我的旅行路线:两端代表起点和终点,中间则是灵活可变的,取决于我们所选路线。如果每个旅行者的路线都如此表示,整个交通网中就有了一个聚合体系统。而交通网要尽量减少拥堵,我们在两个聚合体之间加入引力和斥力,引力表示鼓励旅行者选择相同路线,而斥力表示要尽量减少他们选择相同路线。”

算法提示

更多阅读物理学家组织网相关报道

Return Value

当他们逐渐地将作用力从轻微排斥变成轻微吸引时,闲置节点的数量会急剧上升。“这就像其他物理系统的相变过渡期。”杨智浩说,“也就是说,只要在乘客所选的路线之间引入轻微吸引力,能在平均路径长度增加不多的情况下,大大增加闲置节点数量。这在交通状况较稀疏时,可节约大量资源。”

现在要问:

“推导出理论之后,我们得到了直接的算法。”杨补充说,“我们还用几个数据库对它进行了测试,得到了很好的结果。一旦系统的分析问题解决了,要发现它的宏观特性就变得直接明了,比如平均路线长度、所需能源等。”

 

科学家向高分子“交通网”学习治理交通拥堵

背景概述

假设所有高分子都拥有相同的网络构架,任意两个分子都可能发生路线重叠。“在高分子重叠时,它们之间会产生吸引或排斥作用,作用强度取决于重叠的程度,这又是一个涉及所有高分子的非局域问题。考虑到所有这些复杂性,我们要从所有可能的个别选择及重叠路线中找到最佳路线。”

  应届硕士生10k

新濠国际 1

 

“我们只是用一个简单的随机网络来演示,怎样通过加入的引力和斥力来找到最优通讯路径。”杨智浩说,“我们得到的是一个能实现多个目标的统一算法,只需改变聚合物之间控制引力和斥力强度的一个参数。它还可能用在其他方面,我们欢迎网络专家提出其他特殊的路线问题,来测试这种算法能否解决它们。”

(4)找出序号2的站3可达相邻站2、4,此时4不在其父序{2,3}中,将4加入表,父节点设置为2(序号);此时2在父序中,不做处理。

研究人员还将这种算法用于互联网中,用一种随机曲线来模拟互联网的覆盖网络,也就是在一个计算机网络上面建另一个网络,其中节点可看作是即时连接在一起的虚拟或逻辑连接,相当于一条路径,并与下层网络多个物理链接相连。加入斥力时,每条通讯路径就会避开其他路径,到最后几乎每个人都有自己的路径而不与他人路径重合;如果加入引力,通讯会集中在网络的一小块公共区域里,多人共享路径,留下大量节点和空置连接。如果把空节点看作是路由器,那么关闭它们就能节约大量能源。

  在我看来,2013年应届生应该在4k新濠国际,~5k,今年应届生应该在5k~6k,如果达不到,自身找原因。对于一个慎重的人,应该慎重的选择你们的衣食父母,选择影响命运。

“假如我们鼓励那些在非高峰时段出行的乘客选一般路线,而且允许大部分路线相同,这样,那些次级公交或火车线路就会中止,从而节约大量能源。”杨智浩说,通过模拟聚合体系统之间的吸引力,能得到这种最优的共享路径组合。

Prototype

他们还用全球航空网络做了类似实验,也得到了类似结果。他们认为,在许多运输或通讯网络中,如果能更好协调每个人的出行路线,在节约能源方面会有很大改善。“这和普通的路线查询程序不同,那种程序只能简单地帮人们找出最短路线,并不涉及多人之间的相互作用。”杨智浩解释说,“以我们的算法为基础,可以开发出一种实时应用程序,为那些同时出行的人在全局范围协调路线选择,在高峰时段或高峰季节,实现高速路、地铁、火车或飞机使用平衡的目标。”

我所了解的华为:

物理工具解决分析系统问题

(3)找出序号1的站1可达相邻站10、2,此时10不在其父序{2,1}中,将10加入表,父节点设置为1(序号);此时2在父序中,不做处理。

杨智浩还指出,这种一般路线算法对任何有关路线选择和个体路线协调的问题都适用,希望本研究能有助于解决交通、通讯网络问题,帮助提高现有交通、通讯设施运营效率,减少重复建设。(原标题:《向高分子“交通网”学如何治堵》)

 

有些人可能认为,最短路径总是最佳选择,实际上并非如此:当每个人都选择同一条路时,通常选最短路径都是糟糕的。比如在高峰时段,位于最短路径上的公共路线总是有更多车辆,这些路线就会比稍远些的路线行驶得更慢,造成延迟。

此时已经出现到达站8了,但是还不能结束计算,必须要将循环计算到父节点小于站8父节点为7的位置才能结束,循环序号必须到达9(父节点为6,此上都小于7,此下都不小于7),为什么?

最近,英国阿斯顿大学和中国香港科技大学科学家合作,利用聚合体(由许多相同单体组成的高分子复合物)作用物理学和无序系统原理,来分析宏观层面的一般路线最优化问题。他们推导出一种简单的全局性路径算法,能用于伦敦地铁、全球航空网络和模拟互联网的随机路线图。而且分析显示,相变、比例法则、非单调增长及其他路径问题中出现的新现象都与物理学有关。

(11)找出序号9的站11可达相邻站5,此时5在其父序{2,3,4,5,11}中,不作处理。   

特别声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽。

  2)最短路线:满足最短路线长度要求的所有路线(可能有多条路线,每条路线从起点到终点顺序输出途经的所有站点,包括起点和终点)


  一次输入一条线路,线路表示为一个站点ID数组;

  SrcStation 起点站;

示例

 

  int SearchMinPathes(unsigned int SrcStation, unsigned int DesStation, unsigned int* pPathNum, unsigned int* pPathLen,unsigned int **ppPathes);

Input Param

Input Param

  每条线路都是双向行车 线路有两种:

新濠国际 2

  

  pPathLen 最短路线长度;

 

  0:成功 -1:任何出错情况(包括路线不存在、站点不存在、起点和终点重叠等等)

Output Param

Prototype

题中给了详细思路


  最短线路有几条,请数一数8在表中出现的次数,2;

  无

Output Param

  相关的地铁线和站,请去官方网站使用正则匹配获取,当初是这么干的,别手打,15线279站(不计算重复),累也累死了。

新濠国际 3

(2)找出序号0的站2可达相邻站1、3,此时1、3不在其父序{2}中,将1、3加入表,父节点设置为2的序号。


  ppPathes 存储最短路线的内存地址,内存格式见下图,内存空间在本函数内申请,调用者释放;

  无

  说明:提示的并不是本题的唯一算法,考生可根据情况自行选择是否采用。

实现接口

此时可能看出,7被添加到表中两次,其实这两次是不一样的,仔细推敲吧。此表计算到最后是可以直接找出最优解和所有解,一种理想的数据结构和计算方法,直接拿满分不是更好吗?向下看。

(10)找出序号8的站7可达相邻站5、6、8、9,此时6、8、9不在其父序{2,3,4,5,7}中,将6、8、9加入表,父节点设置为8(序号),此时5在父序中,不作处理。  

 

  我们可以从所有的8开始反向遍历,看看谁的换线次数最少,(所有的线和站都有线性链表,计算遍历线性链表的中断次数),显然 8-7-5-4-3-2 在遍历时线性链表只中断一次,也就是只换乘了一次。也就是我们要找的最优解,将其输出即可2-3-4-5-7-8

 

 

    I形线和O形线 I形线有两个端点,乘客在端点处只能乘坐开往另外一端的地铁,在非端点处则有两个方向可选择。(如图中8号线)

(3) SearchMinPathes

 

 

Return Value

Description  

   void Clear();

(1)将起始站2加入表。

Return Value

  DesStation 终点站;

(4) SearchBestPathes(附加题)

  在地铁网络中任选一站为起点,任选另一站为终点,中途可换乘,要求输出

  SrcStation 起点站;

  增加某条地铁线路

对SETn-1中所有车站,找到前进一站能到达的所有车站,记为SETn,若终点已包含在SETn中,则最短路线长度为n。

  DesStation 终点站;

至此,循环已到达序号9,可以结束了。

(1) AddLine

城市的地铁网络由多条线路组成

  ppPathes 存储最短路线的内存地址,内存格式见下图,内存空间在本函数内申请,调用者释放;

 

Description


  输出从起点站到终点站的最优路线

(5) Clear
Description 清空所有的线路信息

  pStationArray 该条地铁线的所有站点信息,pStationArray指向的存储空间在函数外会被释 放,请自行申请存储空间;

Return Value

  0:成功 -1:任何出错情况(包括路线不存在、站点不存在、起点和终点重叠等等)

输入说明

版权声明:本文由新濠国际发布于科技中心,转载请注明出处:薪资至少10K的一道题,你能拿下吗