加载中...

地址发布 老王说明书 宣传中心
此板块只作为纯讨论

正经话题,不搞色情!贤者时间必备
查看: 4921|回复: 29
收起左侧

[学习讨论] RPG游戏的寻路算法——从绯月讲起

[复制链接]
 楼主| 发表于 2023-12-25 18:31:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?免费注册

x
本帖最后由 navebayes 于 2023-12-26 12:02 编辑
2 q4 r: e$ T4 M* C
" e, s* |8 J4 v0 |. `8 ]7 g5 W最近正在玩个游戏,也算是国产之光绯月仙行录,这个游戏哪里都好就是bug太多,并且作者过于摆烂,以至于有很多玩家都认为这个游戏就是故意拖着吃赞助的(bushi)% `- a) [6 @4 j) R% L* i+ c(欢迎访问老王论坛:laowang.vip)
言归正传,在游玩这个游戏的过程中,我在一个评论区里看到这样一段话:自从玩了绯月之后,对于其他RPG游戏都看不上眼了,因为这个游戏独创了自动寻路的功能,可以说是RPG类游戏的里程碑式壮举。7 g2 J% B1 J; }1 V5 H# i8 {(欢迎访问老王论坛:laowang.vip)
我对此感到好奇,因为从前从来没有游玩RPG类游戏的经验,但我学过一点点算法,于是我打算用一些浅显易懂的方式说说自动寻路这样一个功能的实现。
, d& j9 T/ i! S
- [8 G; @. b3 J+ `) ~. T, V主流的寻路算法:深度优先,广度优先,Dijkstra,A* 等,我这里主要讲讲后两种。
/ Q7 E2 G/ P. H' U6 F$ U. B6 p3 j, d7 Y! Y(欢迎访问老王论坛:laowang.vip)
Dijkstra算法:这个算法是目前很多地图软件都在使用的算法,采用OPEN,CLOSE表的方式实现寻路功能。$ P6 E* Q. ^( G, z" q& l(欢迎访问老王论坛:laowang.vip)
    创建两个表,OPEN, CLOSE。
0 d" e% C# x  [& t( R2 @4 \OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。
" m; _  o& C) n+ q% D, }6 C/ `+ j1. 访问路网中里起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。
" V5 W* [* Y* `8 [# {0 V2. 从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。
7 E0 P6 H) U4 Y) P3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。; E! R; y) I. I, ~8 ]% B(欢迎访问老王论坛:laowang.vip)
4. 重复2,3,步。直到OPEN表为空,或找到目标点。9 A1 B. J1 Z. `$ ^(欢迎访问老王论坛:laowang.vip)
7 Y' }6 v9 ~: W, B9 [8 N/ m3 F(欢迎访问老王论坛:laowang.vip)
实际写代码还是比较占行数的,直接给出链接如下。
" m: a& B% t8 N) q参考:https://blog.csdn.net/YiYeZhiNian/article/details/122217450
* K4 p; u( |; [. v* z
: A) ]0 y- O% F1 T用这个算法,我写过一个课程作业,具体就是对于各个城市的地铁最短路径规划,大致还是比较成功的。先说说个人对于Dijkstra算法设计地铁线路规划:
$ Z+ c7 k; g( n5 [6 M, s1.首先用爬虫爬到该城市的地铁网络,包含站点名称,该站点经纬度和线路图,并生成excel表格。用该excel表格生成pickle文件,方便直接调用。
7 P! ?" B0 h0 x; {- q2.注册高德地图开发者账号(该功能需要实名),得到一个key用于调用api(每日上限100次,超过付费,我调试到后面不让我调试了...)
" D- `, r+ h- @1 e" q+ }+ ?3.输入始发地和目的地,并通过api返回两个位置的经纬度坐标。9 g1 j! l3 A' F  z(欢迎访问老王论坛:laowang.vip)
4.比较两地理位置之间的最近地铁站,并根据Dijkstra算法实现路径规划。& f; ~3 Q6 K9 e, U4 e(欢迎访问老王论坛:laowang.vip)
5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表,并将他和邻居节点进行比对,当所有节点都被处理后即为最短路径: q& s7 {! g0 i  w- F(欢迎访问老王论坛:laowang.vip)
至此,已初步完成具体工作流程。
% D1 F5 \( M; ]& y
  1. def get_nearest_subway(data,longitude1,latitude1):: D0 q7 m$ X# F3 e( \- N(欢迎访问老王论坛:laowang.vip)
  2.   #找最近的地铁站
    " N+ r8 `5 R# ]  R0 j0 K+ v
  3.   longitude1=float(longitude1)
    4 w0 S" v- o4 c2 T" @
  4.   latitude1=float(latitude1)0 ?' e7 f: j) }- ?) \; X(欢迎访问老王论坛:laowang.vip)
  5.   distance=float('inf')
    - N6 A5 y4 T( T5 _
  6.   nearest_subway=None
    6 O, ~; b. Z, v0 B3 f( d) d9 X+ K
  7.   for i in range(data.shape[0]):1 T1 z$ ~2 Q# }' G; m' F" r(欢迎访问老王论坛:laowang.vip)
  8.     site1=data.iloc[i]['name']    8 t, Y7 ^8 k% |: n% p% N(欢迎访问老王论坛:laowang.vip)
  9.     longitude=float(data.iloc[i]['longitude'])& a7 V- j0 @5 X! h(欢迎访问老王论坛:laowang.vip)
  10.     latitude=float(data.iloc[i]['latitude'])    #分别将经纬度代入,计算与目标之间的欧氏距离
    - O: u9 q! W% F! ], V3 W. \4 j
  11.     temp=geodesic((latitude1,longitude1), (latitude,longitude)).m   #temp对其遍历即可,这里对比各个地铁站的欧氏距离
    1 b: O1 H' `6 W( g% |* x3 Q/ t) J
  12.     if temp<distance:3 D4 K6 W& T& H4 E& t2 O7 Y(欢迎访问老王论坛:laowang.vip)
  13.      distance=temp
    2 J. f# E  n* o* X1 Q" p
  14.      nearest_subway=site1
    - z, `3 y( F5 O9 V; j
  15.      return nearest_subway  
复制代码
  1. def subway_line(start,end):    #创建点之间的距离
    0 ]. v+ q2 F; N% K
  2.   file=open('graph.pkl','rb')
    $ h1 F7 ?9 D- B5 D9 E8 e9 \
  3.   graph=pickle.load(file)   #现在我们有了各个地铁站之间的距离存储在graph
    3 q% t' [, K1 ^$ f- ]& g: w
  4.   costs={}    #创建节点的开销表,cost是指从start到该节点的距离) j! K( ^) J- |* D  q4 d* p! i8 I9 ^3 v(欢迎访问老王论坛:laowang.vip)
  5.   parents={}
    1 |7 V5 V+ f  K2 o
  6.   parents[end]=None
      @& }2 T. D  z# i1 I, y
  7.   for node in graph[start].keys():
    $ e! a7 n- w0 U4 e
  8.     costs[node]=float(graph[start][node])) d) w: |6 w( B% `$ J) ^0 y(欢迎访问老王论坛:laowang.vip)
  9.     parents[node]=start
    8 n# c) t: r( Z# R
  10.     costs[end]=float('inf')    #终点到起始点距离为无穷大) P- l1 N8 a6 S8 ~4 `: S" Y, s+ @(欢迎访问老王论坛:laowang.vip)
  11.     processed=[]      #记录处理过的节点list  s& D2 ^1 v6 c$ H& Q5 M5 v(欢迎访问老王论坛:laowang.vip)
  12.     shortest_path=dijkstra(start,end,graph,costs,processed,parents)9 k. K  O# ^% a6 H! d; m(欢迎访问老王论坛:laowang.vip)
  13.     return shortest_path
复制代码
  1. #计算图中从start到end的最短路径% z0 z4 D, ~, m, s(欢迎访问老王论坛:laowang.vip)
  2. def dijkstra(start,end,graph,costs,processed,parents):" J- e" K, n1 b& w' V(欢迎访问老王论坛:laowang.vip)
  3.     #查询到目前开销最小的节点) F: R; X$ z5 b  u) s' ^$ l/ C$ j1 Y+ I(欢迎访问老王论坛:laowang.vip)
  4.     node=find_lowest_cost_node(costs,processed)
    " B! U2 k& B/ t4 _( S
  5.     #使用找到的开销最小节点,计算它的邻居是否可以通过它进行更新2 d- Y- W% v# ~6 u(欢迎访问老王论坛:laowang.vip)
  6.     #如果所有的节点都在processed里面 就结束
    % Z3 q) x5 h" @+ x4 F: }" A
  7.     while node is not None:
    & t7 T  {' P& v) V
  8.     #获取节点的cost
    ! s6 E+ `9 n$ d0 ?5 h
  9.       cost=costs[node]  #cost 是从node 到start的距离6 V2 b4 O1 S) b* t* W0 G1 `(欢迎访问老王论坛:laowang.vip)
  10.       #获取节点的邻居
    * ]/ Z; b3 n2 @1 l/ r
  11.       neighbors=graph[node]
    # ]  W) w$ G& U2 u& y1 k7 s2 G
  12.       #遍历所有的邻居,看是否可以通过它进行更新
    2 v; Y9 |/ g! Y& w: A
  13.       for neighbor in neighbors.keys():
    , A) H% y* e" X$ b
  14.       #计算邻居到当前节点+当前节点的开销
    # c  V) T% R: g; @# X! z: I
  15.         new_cost=cost+float(neighbors[neighbor])
    * J  d0 T6 m) ?. W
  16.         if neighbor not in costs or new_cost<costs[neighbor]:8 X  U& {# ~  C/ X1 \( q' q(欢迎访问老王论坛:laowang.vip)
  17.         costs[neighbor]=new_cost1 g" l& ^0 O+ h(欢迎访问老王论坛:laowang.vip)
  18.         #经过node到邻居的节点,cost最少
    1 Q% Y. r) X; K+ z5 t7 S
  19.         parents[neighbor]=node4 \9 o8 ]4 t( i3 X' X4 {- u(欢迎访问老王论坛:laowang.vip)
  20.         #将当前节点标记为已处理
    - b' m& A( W. P$ Q
  21.   processed.append(node)2 ]! D* W, g' ]# O(欢迎访问老王论坛:laowang.vip)
  22.   #下一步继续找U中最短距离的节点  costs=U,processed=S
    ; [# x" ~  L& l" T& D2 H1 b
  23.   node=find_lowest_cost_node(costs,processed)
复制代码
  1. def find_lowest_cost_node(costs,processed):
      i8 p4 @9 Y2 W3 v, I3 G8 @% h
  2.     #初始化数据
    5 t2 c# h# J2 b
  3.   lowest_cost=float('inf') #初始化最小值为无穷大
    ! M$ M( r3 J( u7 U2 \
  4.   lowest_cost_node=None) O1 H' `$ z/ [. Y7 w& ]) J& W(欢迎访问老王论坛:laowang.vip)
  5.     #遍历所有节点
    ) d" g+ g3 b: s+ ^9 K" b
  6.   for node in costs:
    " z9 M- n( l9 _
  7.     #如果该节点没有被处理, M/ p2 J3 `! h+ H(欢迎访问老王论坛:laowang.vip)
  8.     if not node in processed:" ]2 P6 Y1 x6 d2 N8 ^) S% @4 X% a(欢迎访问老王论坛:laowang.vip)
  9.       #如果当前的节点的开销比已经存在的开销小,那么更新该节点为最小开销的节点
    3 Z2 U& a. C  |3 l0 F6 n) Y
  10.       if costs[node]<lowest_cost:& [* C4 U" H8 l3 w6 y* N3 y# r(欢迎访问老王论坛:laowang.vip)
  11.       lowest_cost=costs[node]: y$ D( e  n- b+ q% M% |(欢迎访问老王论坛:laowang.vip)
  12.       lowest_cost_node=node2 v+ F; a) z  K2 e- g& q2 `! s2 o/ v(欢迎访问老王论坛:laowang.vip)
  13.     return lowest_cost_node
复制代码
上面这段基本上搬运的,主要是他代码已经写的很好了,注释也写的不错,但我写的时候爬虫调不出来(反爬虫技术可以的),最后是我手动去地图里找经纬度得到的结果。
# ~! B' Q. e  r, Q, k引用:https://blog.csdn.net/fengdu78/article/details/111570695) W- a( s, H- G(欢迎访问老王论坛:laowang.vip)

1 s3 U! w" ~2 z2 W5 D% _
. \, b! t' l# X* r  A1 H
1 X; p& H6 i: A(欢迎访问老王论坛:laowang.vip)
A*算法:这个算法也是非常著名的算法,与Dijkstra算法相比,增加了启发式函数 ---- 启发函数的好坏直接决定了算法的效率和结果。由此衍生的D*(动态A算法)算法也被广泛运用于各类游戏中。D*的搜索效率高的原因就在于,当计划路径上某点被阻碍,因为是反向指针,可以定位到被堵节点的上一节点。也就是说只需重新搜索很小的一部分,其余部分仍然使用初始规划出的路径,大大提高了重规划的效率。: R) x, }7 {6 \(欢迎访问老王论坛:laowang.vip)
. g, u, v1 E8 u+ r6 I(欢迎访问老王论坛:laowang.vip)

/ \' N) v1 i5 I% k$ _4 R( \1 T额外补充-dfs&bfs逻辑
, X5 B0 Y# n, L' a深度搜索(dfs)和广度搜索(bfs)的算法逻辑可以说是最具有代表性的,基本任何有关于寻路的算法都没法绕开他俩。我担心可能没了解这2个算法直接去看Djkta和A*会有些懵逼' q/ b! B5 G* t$ D9 c! g(欢迎访问老王论坛:laowang.vip)

& f* A+ T. k" f, u, q1 d% ]深度搜索(dfs)
( F6 n( t2 ?8 m  `5 s4 X5 a

7 @% i' c9 r3 e* jdfs就和它字面意思一样,是往更深的地方找(deepfound), u+ a6 l& J+ ~. _" l& ?(欢迎访问老王论坛:laowang.vip)
它的核心思想很简单:6 l% |; N% N. t8 ?. ^- x, s7 Z% t( P- M(欢迎访问老王论坛:laowang.vip)
一直往前走,走不通就回头; o. V+ p% D' ]' @) F- N# D( i(欢迎访问老王论坛:laowang.vip)
dfs.png
3 t* O6 Y5 o, M" W$ S7 w+ w0 @顺序?当然是长幼啦,有长立长无长立幼 (1会先找2而非6,在2时会先找4而非5 ,直到4发现3 发现无路可走再back回去): b6 t' _& P  d) r; F1 U9 q! R7 H(欢迎访问老王论坛:laowang.vip)
大致伪代码如下
; U9 T- m+ D; f; b. U
  1. input 地图  P, d$ l+ v. Q( _" X(欢迎访问老王论坛:laowang.vip)
  2. create 已经过点. u* l/ g" H- H! H7 K2 |(欢迎访问老王论坛:laowang.vip)
  3. create 结果存储# L' G' W6 Y7 n9 B1 \( I* U(欢迎访问老王论坛:laowang.vip)

  4. / H* Y7 M& Y- v5 X1 b) ^) ^, d; w
  5. type node{. O' G* P. v4 J: D  C" s5 ?# @(欢迎访问老王论坛:laowang.vip)
  6. node nextNode[];//下一节点们: K" C$ O0 E/ J# W( U. e3 O; v( y(欢迎访问老王论坛:laowang.vip)
  7. nodeval;//节点标记物+ R: y7 ^. o* ^* R9 b+ g& B, x(欢迎访问老王论坛:laowang.vip)
  8. }7 }  U' L: }! ~/ x(欢迎访问老王论坛:laowang.vip)

  9. ' S" A- @; M5 n5 O' c

  10. % C# @2 b( h! u
  11. //这里开始是函数
    , [$ m3 [4 o1 g( n& N* E
  12. fun dfs(node* nowPoint)& A5 a* N) I2 J(欢迎访问老王论坛:laowang.vip)
  13. {
    + |. x9 `. f+ [7 a: d
  14. define u 为 nextNode[] size% m3 R; f0 t6 [5 M3 V(欢迎访问老王论坛:laowang.vip)
  15. int  key;
    $ Q) k0 E0 X. e9 G, l6 ^

  16. $ }" ?. ]3 _- P" q- I+ ~
  17. for i in u {
    3 |6 p/ F; v5 R$ T
  18.       if (nowPoint.noteval == target). w7 P- z9 G* d1 }- O! l(欢迎访问老王论坛:laowang.vip)
  19.         {
    . [1 W  u; h- G6 \7 y% }" x% a
  20.             结果存储[0] = nowPoint.noteval;
    8 j& O" x! j! z2 d
  21.             return 0 ;
      t) C& \. z" F- B2 }
  22.         }  7 T$ ]2 l7 B1 \5 U- ?(欢迎访问老王论坛:laowang.vip)
  23.       else if( key = (dfs(nowPoint->nextNode[i])) != -1 ) //如果dfs这次没有返回负1(即 找到终点了)
    ( u0 D" N9 S+ n! `; R, q- z4 T- F
  24.             {6 ^; f' g: v) Y" W& s+ T+ c(欢迎访问老王论坛:laowang.vip)
  25.                 结果存储[key] = nowPoint.noteval;  l+ |; K: K2 Q7 X% @(欢迎访问老王论坛:laowang.vip)
  26.                 return key+1;         ! {/ g( p. s+ g& T9 _(欢迎访问老王论坛:laowang.vip)
  27.             }   
    1 H. y( L9 U5 h/ ^
  28.         else- A+ J2 o# ?6 ]4 Z' @(欢迎访问老王论坛:laowang.vip)
  29.             {
      {8 p% F$ \' f5 y3 B" N  ~# G
  30.                 /********************/
    ' Z9 g  b* d$ {# V! }
  31.                 /**        nothing          **/
    ( E; r( a' m1 R: f+ l6 Y7 V6 `
  32.                 /********************/
    2 ~8 D% ]) \6 n! M6 X- B
  33.             }   
    , u/ d( M+ m. v9 C/ {# e1 l
  34. 8 {$ \) W+ O' p(欢迎访问老王论坛:laowang.vip)
  35.         / g- @( [; p: B7 J" i(欢迎访问老王论坛:laowang.vip)
  36.    }   
    ' M' Z. j+ @; j% P/ e3 U9 _
  37.     return -1;! G! x' k7 a6 G4 v7 k6 b( {9 Q(欢迎访问老王论坛:laowang.vip)
  38. }- z' l9 A, R+ v$ K$ _+ w  [4 F5 R2 R: ~(欢迎访问老王论坛:laowang.vip)
复制代码
就那么短,你只需要确定是不是就行了
) u* h: u8 o* p! C9 c+ _是不是很简单:p 但是这就是一个比较原始的寻路算法的模样-顺其自然流5 C" @: L2 S/ D; L(欢迎访问老王论坛:laowang.vip)
6 I" i1 P6 a0 x3 r(欢迎访问老王论坛:laowang.vip)
在dfs算法中,你需要做的就是 询问+上抛
; y, v0 J. i9 P4 g当然,dfs算法唯一能保证的就是‘找得到路’,这也是为什么纯粹的dfs算法不常用于生产环境中
  E8 v0 `1 I& A6 e) }, J
- r4 v1 f: i) p# o
& e  Z% Z" x# Z* b% X/ X  ]广度搜索(bfs)" R; u/ m0 X; f8 Z(欢迎访问老王论坛:laowang.vip)
知道深度,广度就很容易联想了 先找周围嘛 无论如何,先找周围0 p7 ~) I/ `" u7 u, [(欢迎访问老王论坛:laowang.vip)
bfs.png 4 {* T7 ~8 K# B0 P(欢迎访问老王论坛:laowang.vip)
这里不进行代码补充了,只简单地说一下逻辑# G8 ^7 U5 \/ p$ D: {+ ^) L; D& ~(欢迎访问老王论坛:laowang.vip)
; G2 E+ ?4 ^4 e1 f2 D  P) l) @(欢迎访问老王论坛:laowang.vip)
这个算法分以下几步:
0 {3 ]. e4 @% L8 b! r0,准备一个队列(就是那个queue),然后丢入我们的起点 命运的齿轮开始拨动9 f& G9 Q' N: W' s( B1 F) z& M( [(欢迎访问老王论坛:laowang.vip)

5 \$ |" C% O: s1,询问当前节点是否终点?
  a0 D) R2 U0 J2,将自己的nextNode 塞入队列中(除了访问过的)
9 i! u8 L& k$ u( G2 D) X3,从队列里output一个节点,作为下一个‘当前节点’$ b; L) y% l  ]/ o% f. y2 Y8 T(欢迎访问老王论坛:laowang.vip)
. G8 @# L+ L/ E(欢迎访问老王论坛:laowang.vip)
然后就是循环1~3
: ~6 ^( [6 O, g& p( ?( S7 c
3 ^' b* x, I& @是不是很简单?
6 n) G! Y2 H7 J% Q
7 e+ S. [/ T6 k/ _6 k0 S1 u" x' ~这2个算法都属于随性流,一个适合终点远一个适合终点近。但无论如何这俩都暂时没有比较最优的功能
; X  W8 J6 ~$ K因为他们刚~满~十~八~岁~的审敛条件就只是找得到路
/ @* L1 q3 L$ b' G7 @% Y4 g" J- O4 {0 K& V( M6 i( f3 `(欢迎访问老王论坛:laowang.vip)
但你可以发现哦?如果将dfs的‘长幼判断’换成‘最优判断’,将呆值传递换为矩阵存储 就是dj算法了诶(a*也是类似的)7 _$ a( C) {' M8 W2 Z$ L9 @(欢迎访问老王论坛:laowang.vip)
而bfs作为‘扩散式搜索’显然地在进行多点寻路时效用更加明显
& G5 l+ _" l! ^如果觉得寻路算法很难的话,不妨先从dfs&bfs开始了解, z* z4 k9 m7 v( F2 M- [; b(欢迎访问老王论坛:laowang.vip)

: n. W4 T* i) i& j" H
1 i8 B" K' X, u. l4 E4 p" f- A5 A- N" c. J. D- I+ a- W8 i" r(欢迎访问老王论坛:laowang.vip)
: w( C( b5 h; z+ v& o(欢迎访问老王论坛:laowang.vip)

A*寻路算法

A*寻路算法

评分

参与人数 1软妹币 +235 收起 理由
navebayes + 235 cheese!!

查看全部评分

本帖被以下淘专辑推荐:

回复

使用道具 举报

发表于 2023-12-25 20:31:04 手机版 | 显示全部楼层
Applcu 发表于 2023-12-25 20:19
( \- I) B# _! W我在想怎么算说明运作逻辑.....真贴上去么?这个编辑器到底怎么用啊' O" A7 P9 F0 ^8 O6 U(欢迎访问老王论坛:laowang.vip)
...
' T$ D5 t! q* d! O; @" e6 O& j(欢迎访问老王论坛:laowang.vip)
有一个代码框功能,可以用那个。主要编辑的话建议用正八经的md编辑器(我用的是国产的typora)
回复 支持 3 反对 0

使用道具 举报

发表于 2023-12-25 20:25:06 | 显示全部楼层
navebayes 发表于 2023-12-25 20:11* t; U, Z# j7 K  e$ a6 V# z(欢迎访问老王论坛:laowang.vip)
申请失败,原因:对算法本身描述过少,请更具体地说明算法的运作逻辑和方式,如果可以最好给出部分低代码8 f  B" b  g& r; J; F2 Y(欢迎访问老王论坛:laowang.vip)
2 I' B7 }8 x% \# O% _. _(欢迎访问老王论坛:laowang.vip)
...

9 `4 R. l9 K6 l% T- I9 X啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
! ~  t# A8 m8 m. `0 H0 Q$ R4 o
  P0 c& M! ~3 y这玩意考试考得头昏脑涨,我tm 深度生成树画错了,越想越气 怎么会这么蠢7 e' X* i/ Q( v* |$ E(欢迎访问老王论坛:laowang.vip)
回复 支持 2 反对 0

使用道具 举报

 楼主| 发表于 2023-12-25 23:28:47 | 显示全部楼层
昔有佳人公孙氏 发表于 2023-12-25 23:08
" U" L  L$ X' i8 C其实目前,本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环: B" K" j9 w: d$ s3 l(欢迎访问老王论坛:laowang.vip)
但其实寻找最 ...
. c' x: J: \4 C: z" q4 Y6 k& t(欢迎访问老王论坛:laowang.vip)
黏菌那个早有耳闻,确实是大自然的力量。我之后还想写点加密算法,比如AES,RSA,ECC之类的,其实这个地铁的算法也是我的一个课设,我大概花了两天就搞完了,我的主专业课是自控/单片机/数电/模电/嵌入式之类的,更偏自动化这个方向,算法我研究的不深。这个当毕业论文可能还是有一些勉强的,个人感觉工科是要做出一点实物的东西,当然不同学校可能要求不尽相同。$ ?1 o/ v. p" v(欢迎访问老王论坛:laowang.vip)

5 T" [) [' V% z/ Q0 s0 D- E0 m
- {6 i% j9 `6 R
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2023-12-25 21:58:28 | 显示全部楼层
先说说个人对于Dijkstra算法设计地铁线路规划:! s/ M1 [# [) K. O$ @& g  x! r(欢迎访问老王论坛:laowang.vip)
1.首先用爬虫爬到该城市的地铁网络,包含站点名称,该站点经纬度和线路图,并生成excel表格。用该excel表格生成pickle文件,方便直接调用。& V  g, x5 X6 j(欢迎访问老王论坛:laowang.vip)
2.注册高德地图开发者账号(该功能需要实名),得到一个key用于调用api(每日上限100次,超过付费,我调试到后面不让我调试了...)
% @, r! C" h8 d2 H3.输入始发地和目的地,并通过api返回两个位置的经纬度坐标。9 ]( f7 |+ F7 y8 c4 b& N(欢迎访问老王论坛:laowang.vip)
4.比较两地理位置之间的最近地铁站,并根据Dijkstra算法实现路径规划。
4 }$ g8 ]( D+ s% _9 T1 ~8 ^  D5 ^5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表,并将他和邻居节点进行比对,当所有节点都被处理后即为最短路径* `0 q5 O3 ^( f) I/ i' s" Y(欢迎访问老王论坛:laowang.vip)
至此,已初步完成具体工作流程。
5 p  M. |0 \( p) `0 s" A4 L
  1. def get_nearest_subway(data,longitude1,latitude1):
    , y9 E4 ~  H# W) o4 j5 y8 I
  2.     #找最近的地铁站
    2 `4 N9 |- _9 Z7 t
  3.     longitude1=float(longitude1)7 V% K# A, F! D6 Y5 a/ H; [(欢迎访问老王论坛:laowang.vip)
  4.     latitude1=float(latitude1)
    ' s7 ]) [* Y0 z3 C7 v" P
  5.     distance=float('inf')5 r" ]6 J. L& s# G& H4 I; Y(欢迎访问老王论坛:laowang.vip)
  6.     nearest_subway=None
    0 B6 \8 Z$ F2 F5 w" }1 e  [0 C$ p
  7.     for i in range(data.shape[0]):  i6 z; B/ {8 J8 K3 s/ e: P(欢迎访问老王论坛:laowang.vip)
  8.   site1=data.iloc[i]['name']   
    1 V8 i1 M0 G2 O- t! @) \8 a9 L
  9.   longitude=float(data.iloc[i]['longitude']). A/ z/ d, m2 h; o(欢迎访问老王论坛:laowang.vip)
  10.   latitude=float(data.iloc[i]['latitude'])    #分别将经纬度代入,计算与目标之间的欧氏距离: k# D" P1 S/ s" c: ?(欢迎访问老王论坛:laowang.vip)
  11.   temp=geodesic((latitude1,longitude1), (latitude,longitude)).m   #temp对其遍历即可,这里对比各个地铁站的欧氏距离
    ) E* q+ l1 z7 t' n8 K( h+ ]2 o, X
  12.   if temp<distance:" O  V' w4 l3 k& s(欢迎访问老王论坛:laowang.vip)
  13.     distance=temp
    + M2 O7 k5 d4 Z# z+ E. Z# X% @
  14.     nearest_subway=site1) |% Q0 F/ c. d7 _. z/ x(欢迎访问老王论坛:laowang.vip)
  15.     return nearest_subway  
复制代码
  1. def subway_line(start,end):    #创建点之间的距离
    ( \9 A# t; t1 P7 |3 _+ U8 a+ x/ x( N+ L
  2.     file=open('graph.pkl','rb')
    * P) {) q4 v6 x5 M; K, y
  3.     graph=pickle.load(file)   #现在我们有了各个地铁站之间的距离存储在graph3 d! z8 X/ z* Z4 l8 r. `(欢迎访问老王论坛:laowang.vip)
  4.     costs={}    #创建节点的开销表,cost是指从start到该节点的距离
    8 d* T" }6 z) p
  5.     parents={}: C/ }$ v+ U" L! X  c(欢迎访问老王论坛:laowang.vip)
  6.     parents[end]=None
    . `, J- ]4 ?( Y7 V/ |
  7.     for node in graph[start].keys():
    1 `3 H8 @5 \! g* W: ~- _
  8.   costs[node]=float(graph[start][node])
    ! |* B/ u$ ^/ p1 Y/ n9 e" x8 E. X
  9.   parents[node]=start1 b) `1 C0 `" ^+ B+ ?(欢迎访问老王论坛:laowang.vip)
  10.     costs[end]=float('inf')    #终点到起始点距离为无穷大9 P$ T0 x' n5 {# V- Z(欢迎访问老王论坛:laowang.vip)
  11.     processed=[]      #记录处理过的节点list. ?5 n+ e4 V/ [  q2 l% H(欢迎访问老王论坛:laowang.vip)
  12.     shortest_path=dijkstra(start,end,graph,costs,processed,parents)
    1 k; p7 B0 h( R9 N5 r
  13.     return shortest_path
复制代码
  1. #计算图中从start到end的最短路径
    / T, ~4 v; `* `& {% N* {
  2. def dijkstra(start,end,graph,costs,processed,parents):' \3 @  |0 o, W6 E) y3 {(欢迎访问老王论坛:laowang.vip)
  3.     #查询到目前开销最小的节点
    . d& Y8 T/ c7 [# L" e
  4.     node=find_lowest_cost_node(costs,processed)- |8 O) l/ _: t' S9 a: U+ u(欢迎访问老王论坛:laowang.vip)
  5.     #使用找到的开销最小节点,计算它的邻居是否可以通过它进行更新
    * I; R5 {& ~9 m2 t" i$ ?4 o
  6.     #如果所有的节点都在processed里面 就结束
    " B( M% r! I% {) ?; q
  7.     while node is not None:" F3 N/ f! m* W- r0 H(欢迎访问老王论坛:laowang.vip)
  8.   #获取节点的cost
    4 E4 P  @3 ]) d1 ^: w5 N3 P: G' _3 E
  9.   cost=costs[node]  #cost 是从node 到start的距离  L& C. G0 p, R0 y5 F/ r(欢迎访问老王论坛:laowang.vip)
  10.   #获取节点的邻居- T7 g" p& g# |6 N; O& {9 d(欢迎访问老王论坛:laowang.vip)
  11.   neighbors=graph[node]! ~, x7 T3 N/ `% p& v(欢迎访问老王论坛:laowang.vip)
  12.   #遍历所有的邻居,看是否可以通过它进行更新% ]4 }1 T3 D% A) A" F(欢迎访问老王论坛:laowang.vip)
  13.   for neighbor in neighbors.keys():6 u, V8 q" R3 o# Y( h(欢迎访问老王论坛:laowang.vip)
  14.     #计算邻居到当前节点+当前节点的开销
    : z6 E( Q# @; |. u* T
  15.     new_cost=cost+float(neighbors[neighbor]). a. I( v- K8 L8 e" h(欢迎访问老王论坛:laowang.vip)
  16.     if neighbor not in costs or new_cost<costs[neighbor]:; Q  {" @7 R9 @4 F(欢迎访问老王论坛:laowang.vip)
  17.       costs[neighbor]=new_cost$ n6 [9 C, C3 c5 ?! `(欢迎访问老王论坛:laowang.vip)
  18.       #经过node到邻居的节点,cost最少
    & e! e8 i+ w1 u
  19.       parents[neighbor]=node
    . m4 `) @: e2 ]. S2 C: ~
  20.   #将当前节点标记为已处理" N& I- h9 v% L(欢迎访问老王论坛:laowang.vip)
  21.   processed.append(node)
    ( v* F) [# H1 h7 Z/ `& M( ~3 W
  22.   #下一步继续找U中最短距离的节点  costs=U,processed=S
    . r4 K4 y% Q. |, F. H* ~! E
  23.   node=find_lowest_cost_node(costs,processed)
复制代码

5 ]2 s9 f+ T# k  a2 f. z  T  x! m' Y. @: j(欢迎访问老王论坛:laowang.vip)
  1. def find_lowest_cost_node(costs,processed):0 W+ b8 y2 L- `$ R(欢迎访问老王论坛:laowang.vip)
  2.     #初始化数据1 F" u7 G9 m4 _1 e# E(欢迎访问老王论坛:laowang.vip)
  3.     lowest_cost=float('inf') #初始化最小值为无穷大
    , y, d+ ?( |7 l6 q
  4.     lowest_cost_node=None4 Z) B2 r1 _( q$ V1 Y7 K  h(欢迎访问老王论坛:laowang.vip)
  5.     #遍历所有节点
    " F3 j' f. Q; j: G  \' z
  6.     for node in costs:/ ~6 l* W/ |8 h* E(欢迎访问老王论坛:laowang.vip)
  7.   #如果该节点没有被处理
    , `8 g. @  O; {+ t1 g' l, {0 u
  8.   if not node in processed:* |+ f1 C* {" j, \3 ^! ^- O9 y7 @(欢迎访问老王论坛:laowang.vip)
  9.     #如果当前的节点的开销比已经存在的开销小,那么更新该节点为最小开销的节点+ d+ a# y4 _5 |(欢迎访问老王论坛:laowang.vip)
  10.     if costs[node]<lowest_cost:+ r- ?" D3 D+ u(欢迎访问老王论坛:laowang.vip)
  11.       lowest_cost=costs[node]
    , Z# Y2 m/ S) ^; |$ |$ U  c
  12.       lowest_cost_node=node
    ' O7 [2 P! l$ S. z# J% |
  13.     return lowest_cost_node
复制代码
上面这段基本上搬运的,主要是他代码已经写的很好了,注释也写的不错,但我写的时候爬虫调不出来(反爬虫技术可以的),最后是我手动去地图里找经纬度得到的结果。
- e+ U9 \" P3 p+ Y% Y引用:https://blog.csdn.net/fengdu78/article/details/1115706957 V( h1 w! t, }( g  N! M4 {(欢迎访问老王论坛:laowang.vip)
回复 支持 1 反对 0

使用道具 举报

发表于 2023-12-25 20:11:24 手机版 | 显示全部楼层

修改修改

本帖最后由 navebayes 于 2023-12-25 20:14 编辑
! ~3 d' I. x1 Z; N* I, V( Q+ l/ m& X+ l(欢迎访问老王论坛:laowang.vip)
申请失败,原因:对算法本身描述过少,请更具体地说明算法的运作逻辑和方式,如果可以最好给出部分低代码
- C+ t+ [, d# h& P/ r# R8 r: X* X3 ^* i1 n/ x0 k(欢迎访问老王论坛:laowang.vip)
ps:只要做滴好,王爷有赏啊
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2023-12-25 20:19:00 | 显示全部楼层
navebayes 发表于 2023-12-25 20:11
: N9 M! [( _2 [/ M申请失败,原因:对算法本身描述过少,请更具体地说明算法的运作逻辑和方式,如果可以最好给出部分低代码" }" r! \# g! [" u(欢迎访问老王论坛:laowang.vip)
8 g7 O/ g: V8 ~& n) a(欢迎访问老王论坛:laowang.vip)
...
/ ?3 Q, i2 ~: g% ~( Y(欢迎访问老王论坛:laowang.vip)
我在想怎么算说明运作逻辑.....真贴上去么?这个编辑器到底怎么用啊
, x3 n; r4 ~. _/ |" R% ?" H0 U
回复 支持 反对

使用道具 举报

发表于 2023-12-25 20:35:28 手机版 | 显示全部楼层
昔有佳人公孙氏 发表于 2023-12-25 20:25
9 h# j; b1 q) e7 v0 x啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
/ m2 T/ u* _" p. i% `( T1 U( B
& }( B: ~! L/ u' g, U& [4 H这玩意考试考得头 ...

! X4 Q7 t1 s! t$ |. R" [看作者本人嘛,我不想干涉思路..: D& b; |) }, S7 j: I8 k) O(欢迎访问老王论坛:laowang.vip)
(程序:哥们这可不是什么负权圈,这是时空之门啊啊啊啊啊(然后获得了每过一年减一岁的黄金体验))
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 20:43:49 | 显示全部楼层
昔有佳人公孙氏 发表于 2023-12-25 20:25
4 y2 N! ^/ g/ r  W! Q1 S啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法5 }5 A, U9 f+ [* [, ~) f& [(欢迎访问老王论坛:laowang.vip)

  ~0 i8 J/ P- H: w- g' G* h' o这玩意考试考得头 ...

) u9 G4 w- m+ R/ @9 z这应该是考专业课考破防了
4 [  H% }% ~$ Q& ~2 z8 D7 b
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 20:48:19 | 显示全部楼层
昔有佳人公孙氏 发表于 2023-12-25 20:25
  b( z! [! k( \- L( q啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
3 u; k( e0 `2 `, ^2 O  i; I8 _9 |( b) L" ^(欢迎访问老王论坛:laowang.vip)
这玩意考试考得头 ...
& r! T9 u1 S& b3 x' o5 o: J(欢迎访问老王论坛:laowang.vip)
负权不就卡bug了么,越来越低就成环了9 X7 i. A: z1 q" ]. o3 n$ y(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

发表于 2023-12-25 20:56:03 手机版 | 显示全部楼层
Applcu 发表于 2023-12-25 20:48: v5 Z3 [8 K( L  u  s(欢迎访问老王论坛:laowang.vip)
负权不就卡bug了么,越来越低就成环了

6 I! ^1 R0 i/ m! g% p) X宝宝,把剩下的内容补上嘛
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 21:15:16 | 显示全部楼层
navebayes 发表于 2023-12-25 20:563 L+ g. P/ _2 |. L(欢迎访问老王论坛:laowang.vip)
宝宝,把剩下的内容补上嘛

# S4 j5 W# e$ X" T真是男童啊.....
# l; u7 \- d, @" T+ J! \
回复 支持 反对

使用道具 举报

发表于 2023-12-25 21:37:16 手机版 | 显示全部楼层
Applcu 发表于 2023-12-25 21:15
6 a* O( A/ Q! {+ V7 s真是男童啊.....

- \' a( V: T& S, c* e诽谤管理封七天
回复 支持 反对

使用道具 举报

发表于 2023-12-25 22:34:33 | 显示全部楼层
Applcu 发表于 2023-12-25 21:58- s( k9 l$ z  W6 H(欢迎访问老王论坛:laowang.vip)
先说说个人对于Dijkstra算法设计地铁线路规划:
" g3 z; N7 k7 F9 B1.首先用爬虫爬到该城市的地铁网络,包含站点名称,该站点 ...
+ `7 A+ I: w' y& Y# L9 K4 Y(欢迎访问老王论坛:laowang.vip)
可以加入正文喵6 ~5 j. ^( x( w4 E' F0 {4 l(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 22:42:13 | 显示全部楼层
昔有佳人公孙氏 发表于 2023-12-25 20:25
( d4 \4 C4 |. _' D0 {' G- h/ J啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法8 t0 o# J: y$ z3 f(欢迎访问老王论坛:laowang.vip)
; m; ?* H  }! m/ D9 S(欢迎访问老王论坛:laowang.vip)
这玩意考试考得头 ...
" W5 d* [. o% d0 @. G! z' x0 P(欢迎访问老王论坛:laowang.vip)
我也头大了.....但本质还是因为Dijkstra算法认为,如果有一条最短路线可以直达目的地,那么从旁边走另外的路将会直接不考虑,但在负权边这里,反而会减小cost,所以Dijkstra算法失效了,因为无法发现这条最短的路径1 v1 \: R, C% e# ~. f(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 22:51:56 | 显示全部楼层
navebayes 发表于 2023-12-25 22:34! K  N  M: E( P9 Y- c- S(欢迎访问老王论坛:laowang.vip)
可以加入正文喵

$ e% f3 z7 a* B3 |9 o加了加了
) A2 t6 Z" J0 E+ H0 K
回复 支持 反对

使用道具 举报

发表于 2023-12-25 23:02:44 | 显示全部楼层
Applcu 发表于 2023-12-25 22:51# L' G0 x4 ^0 K& ~$ N2 c/ D, u(欢迎访问老王论坛:laowang.vip)
加了加了
. b! x1 y- N$ w/ u5 d(欢迎访问老王论坛:laowang.vip)
介意让我改一下吗https://pic.imgdb.cn/item/6589996fc458853aef070f38.gif5 S8 J- q6 q" w7 i(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

发表于 2023-12-25 23:08:15 | 显示全部楼层
其实目前,本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环
" {* f0 q7 ?, R8 H- H3 Q& q$ ^但其实寻找最短路径的算法里还有很知名的黏菌算法。
" J: N8 l' e, @8 c' ?有兴趣的可以去B站搜搜黏菌走迷宫,看看在大自然顶级的算法编辑下的单源最短路径问题的解法
4 r, f5 x+ w$ q不是说将奖励放置位置对应于日本的各大城市,两天内的黏菌路线就基本和目前日本的城市规划大致相似了吗,当然不太严谨是真的
& W7 B5 o, s  z! z! ]就好像楼主说的做了地铁最短路径规划, 这玩意我舍友和你类似,她做的事全国铁路路径规划,涉及到价格,时间,反正做到最后是你输入起始地址和目的地,就能得出花费最少,时间最少,转站最少的路线,C++课设 我记得很清楚,我记得老师说的评价是,如果再加上运筹学的内容,说不定可以当毕业论文了,不出意外她拿了满分。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-12-25 23:30:40 | 显示全部楼层
navebayes 发表于 2023-12-25 23:02
6 R9 z$ X5 m( |4 A介意让我改一下吗

+ `' x/ J) X9 r3 M& x可以可以1 u9 E! @, w( M) \& o(欢迎访问老王论坛:laowang.vip)
回复 支持 反对

使用道具 举报

发表于 2023-12-26 12:03:53 | 显示全部楼层
Applcu 发表于 2023-12-25 23:30
5 `( J4 ^, {9 `' t; z  O可以可以

2 g5 N7 H! a" X6 @: u2 V排版改了下喵,东西加好了喵
/ D3 l/ r  L/ |/ b9 o2 u# j% O
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 免费注册
点击进行验证

本版积分规则

我们不生产资源,只做资源的搬运工。

tags标签-春满四合院-AvGood-Archiver-小黑屋- |网站地图