Applcu 发表于 2023-12-25 20:19
我在想怎么算说明运作逻辑.....真贴上去么？这个编辑器到底怎么用啊
7 \' S) c  o8 s6 ~ ...

& v+ e! F% c' X5 t3 s: W有一个代码框功能，可以用那个。主要编辑的话建议用正八经的md编辑器（我用的是国产的typora）

navebayes 发表于 2023-12-25 20:11
- K2 y8 H# s- {5 D0 }2 t申请失败，原因：对算法本身描述过少，请更具体地说明算法的运作逻辑和方式，如果可以最好给出部分低代码
# @0 c9 t8 \6 b( d3 r
...

啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法

这玩意考试考得头昏脑涨，我tm 深度生成树画错了，越想越气 怎么会这么蠢
, v/ k( E- \8 e* N3 v) r

昔有佳人公孙氏 发表于 2023-12-25 23:08
其实目前，本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环
1 x, G4 j& u; m! u1 w! @但其实寻找最 ...

$ ?" }, h* K3 Q" [& y: [  g黏菌那个早有耳闻，确实是大自然的力量。我之后还想写点加密算法，比如ＡＥＳ，ＲＳＡ，ＥＣＣ之类的，其实这个地铁的算法也是我的一个课设，我大概花了两天就搞完了，我的主专业课是自控／单片机／数电／模电／嵌入式之类的，更偏自动化这个方向，算法我研究的不深。这个当毕业论文可能还是有一些勉强的，个人感觉工科是要做出一点实物的东西，当然不同学校可能要求不尽相同。
1 ]7 e; M" F  f- h4 h3 @

# ]  @% |8 y: |" Q

先说说个人对于Dijkstra算法设计地铁线路规划：
1.首先用爬虫爬到该城市的地铁网络，包含站点名称，该站点经纬度和线路图，并生成excel表格。用该excel表格生成pickle文件，方便直接调用。
* E0 H. _  ?  `! _6 ^2.注册高德地图开发者账号（该功能需要实名），得到一个key用于调用api（每日上限100次，超过付费，我调试到后面不让我调试了...）
3.输入始发地和目的地，并通过api返回两个位置的经纬度坐标。
4.比较两地理位置之间的最近地铁站，并根据Dijkstra算法实现路径规划。
5.Dijkstra算法的本质就是不断选择新顶点并更新已处理表，并将他和邻居节点进行比对，当所有节点都被处理后即为最短路径
至此，已初步完成具体工作流程。

1. def get_nearest_subway(data,longitude1,latitude1):
   
2.     #找最近的地铁站
   3 {0 q: ?  t% }
3.     longitude1=float(longitude1)
   
4.     latitude1=float(latitude1)
   
5.     distance=float('inf')
   
6.     nearest_subway=None
   , K" E2 B: n4 n$ i9 a
7.     for i in range(data.shape[0]):
     u* R0 n9 `9 K
8.   site1=data.iloc[i]['name']   
   
9.   longitude=float(data.iloc[i]['longitude'])
   
10.   latitude=float(data.iloc[i]['latitude'])    #分别将经纬度代入，计算与目标之间的欧氏距离
    % E7 L0 R& J; b1 N6 @6 n- w
11.   temp=geodesic((latitude1,longitude1), (latitude,longitude)).m   #temp对其遍历即可，这里对比各个地铁站的欧氏距离
    3 _1 U/ N8 E. k  `/ m
12.   if temp<distance:
    
13.     distance=temp
    ) x' A, `) a! K4 }# ?! g% C) P
14.     nearest_subway=site1
    
15.     return nearest_subway  

复制代码

1. def subway_line(start,end):    #创建点之间的距离
   
2.     file=open('graph.pkl','rb')
   & ^" u- a' e' L& I' B: P% Z" I
3.     graph=pickle.load(file)   #现在我们有了各个地铁站之间的距离存储在graph
   
4.     costs={}    #创建节点的开销表，cost是指从start到该节点的距离
   
5.     parents={}
   & @4 P! O: U. n* b
6.     parents[end]=None
   
7.     for node in graph[start].keys():
   8 o  S: P( ]- {! ^- N$ V; O2 m
8.   costs[node]=float(graph[start][node])
   
9.   parents[node]=start
   
10.     costs[end]=float('inf')    #终点到起始点距离为无穷大
    
11.     processed=[]      #记录处理过的节点list
    $ h2 P! T" M- M, @* u
12.     shortest_path=dijkstra(start,end,graph,costs,processed,parents)
    
13.     return shortest_path

复制代码

1. #计算图中从start到end的最短路径
   
2. def dijkstra(start,end,graph,costs,processed,parents):
   
3.     #查询到目前开销最小的节点
   
4.     node=find_lowest_cost_node(costs,processed)
     D! q& [1 R0 `7 N
5.     #使用找到的开销最小节点，计算它的邻居是否可以通过它进行更新
   
6.     #如果所有的节点都在processed里面 就结束
   6 K  \4 @% m; d
7.     while node is not None:
   
8.   #获取节点的cost
   
9.   cost=costs[node]  #cost 是从node 到start的距离
   
10.   #获取节点的邻居
    
11.   neighbors=graph[node]
    / Q0 `1 j0 U2 M- h" l. O1 [  [
12.   #遍历所有的邻居，看是否可以通过它进行更新
    " M" ~1 Q% J, N. B7 N7 M
13.   for neighbor in neighbors.keys():
    ! h" Z4 X" z1 b" p# j  a& i
14.     #计算邻居到当前节点+当前节点的开销
    # p% q9 R1 c5 P* I) y
15.     new_cost=cost+float(neighbors[neighbor])
    
16.     if neighbor not in costs or new_cost<costs[neighbor]:
    0 ], c  X0 Y9 W3 J5 u/ S  F
17.       costs[neighbor]=new_cost
    & C, {. q- ^& ]' R* ^/ g1 n
18.       #经过node到邻居的节点，cost最少
    
19.       parents[neighbor]=node
    
20.   #将当前节点标记为已处理
    
21.   processed.append(node)
    + G2 U  C0 M: @  @; {
22.   #下一步继续找U中最短距离的节点  costs=U,processed=S
    
23.   node=find_lowest_cost_node(costs,processed)

复制代码

) c/ u# k- a# ]

1. def find_lowest_cost_node(costs,processed):
   
2.     #初始化数据
   " G3 _) @2 `2 ^2 Z
3.     lowest_cost=float('inf') #初始化最小值为无穷大
   % d% m- @: ?" o2 `& Y3 @) Y
4.     lowest_cost_node=None
   
5.     #遍历所有节点
   5 k; H) z$ H' e, t4 I6 J5 z
6.     for node in costs:
   0 p3 t4 N! n7 V0 P# R
7.   #如果该节点没有被处理
   
8.   if not node in processed:
   
9.     #如果当前的节点的开销比已经存在的开销小，那么更新该节点为最小开销的节点
   
10.     if costs[node]<lowest_cost:
    $ D' f$ [- A$ F/ N1 r6 V/ i6 y
11.       lowest_cost=costs[node]
    & |' x# T& ?7 h% V6 b+ R' W7 {( J. A
12.       lowest_cost_node=node
    
13.     return lowest_cost_node

复制代码

上面这段基本上搬运的，主要是他代码已经写的很好了，注释也写的不错，但我写的时候爬虫调不出来（反爬虫技术可以的），最后是我手动去地图里找经纬度得到的结果。
" U4 T0 t, `# w9 }. d) @引用：https://blog.csdn.net/fengdu78/article/details/111570695
) S+ _" c- t/ V- O* F+ H" [

申请失败，原因：对算法本身描述过少，请更具体地说明算法的运作逻辑和方式，如果可以最好给出部分低代码

ps：只要做滴好，王爷有赏啊

我是一个初中OIer，如有错误请指出，欢迎讨论
( v2 o, G2 Y9 y& n% m我记得之前好像看主要地图的寻路算法是A*?如果没记错的话
1 Q' j0 A2 @# T1 G
有几点建议：
1.具体算法实现可以用CPP，Python太慢了，尤其是要处理百万/千万级别的数据时，可以用python爬取数据然后由cpp进行相应处理，这样的好处是大幅减少了时间且使不会特别麻烦(CPP的网络爬虫实现太麻烦，且各种配置环境很难受)不过如果数据量不是很大的话用py很省开发时间(
; u2 e" F  X, x/ a* y: a2.关于实现算法我个人更推荐A*，由于其是启发式的，时间复杂度比Dij低，也能省下很长时间(不过也要看数据量，有些时候IDA*比A*好)至于您说的D*很抱歉我没有接触过这个算法，不予评价

& a& X" d8 ]" d3 h. d7 J5 R如果有很多很多线路要查询的话还可以加个多线程优化，这个用py的threading更容易些，当然cpp也不是不行

六道骸 发表于 2023-12-29 00:45
" ]4 s4 e  c6 x6 f0 h/ d. u& T$ e8 n太专业看不懂，，，

9 `' c  ^, w+ M+ O1 A7 y这个还是要对算法有一定了解才能看懂

太专业看不懂，，，

Applcu 发表于 2023-12-26 22:28
9 |7 G4 P" t) f- x) h3 s$ m. k好的，下次改进一下

- t! k; _- z+ z7 k/ S8 |; W今天给你们加钱了喵，主要是感觉原来的发的还是有些少

qwer20021125 发表于 2023-12-26 20:15
很难想象居然在这里看到了这种文章，点赞

你可以在ｇｈｓ的网站看到高数的视频，那肯定也能在这看到算法类帖子

navebayes 发表于 2023-12-26 13:56
2 h6 @& O) j+ Y. i8 `5 [0 D3 w下次可以的话写详细些..比如算法这类最好有深有浅

. K% y+ h+ Z1 ]好的，下次改进一下
4 m( x$ u( p7 O, X1 f& q9 k  X

很难想象居然在这里看到了这种文章，点赞

Applcu 发表于 2023-12-26 13:37
+ m4 S8 H% c) p2 B! h好好好，大概就这样吧建议打钱

下次可以的话写详细些..比如算法这类最好有深有浅

. M) @; k& u. v
! a  A3 L7 G! a- m- i6 l基础50可读50排版50内容120其他40共计235+45+30=310

navebayes 发表于 2023-12-26 12:03
2 q7 ]2 m+ R( d  z排版改了下喵，东西加好了喵

好好好，大概就这样吧建议打钱

Applcu 发表于 2023-12-25 23:30
可以可以

/ y! \9 {* A1 v5 J" C# P排版改了下喵，东西加好了喵
) i* @- Y' v& f$ `8 D

navebayes 发表于 2023-12-25 23:02
介意让我改一下吗

可以可以

其实目前，本科生能接触到的寻路算法 无外乎迪杰斯特拉和弗洛伊德 一个不吃负值 一个不吃负环
! @0 Z0 S0 F) x$ O5 j9 a! n" Z( G# y但其实寻找最短路径的算法里还有很知名的黏菌算法。
有兴趣的可以去B站搜搜黏菌走迷宫，看看在大自然顶级的算法编辑下的单源最短路径问题的解法
: ?$ j' \) ~& j不是说将奖励放置位置对应于日本的各大城市，两天内的黏菌路线就基本和目前日本的城市规划大致相似了吗，当然不太严谨是真的
就好像楼主说的做了地铁最短路径规划， 这玩意我舍友和你类似，她做的事全国铁路路径规划，涉及到价格，时间，反正做到最后是你输入起始地址和目的地，就能得出花费最少，时间最少，转站最少的路线，C++课设 我记得很清楚，我记得老师说的评价是，如果再加上运筹学的内容，说不定可以当毕业论文了，不出意外她拿了满分。

Applcu 发表于 2023-12-25 22:51
4 |! i9 {" S/ u- q3 w加了加了

+ H4 v' S9 J! ?) |! @介意让我改一下吗https://pic.imgdb.cn/item/6589996fc458853aef070f38.gif
& t9 c: A" _: I- {5 `

navebayes 发表于 2023-12-25 22:34
/ i' ?5 ?# Y+ E8 E4 z可以加入正文喵

+ p( K# N. K8 z* B8 c加了加了
+ ]0 A% b( |/ Y# f, N% W

昔有佳人公孙氏 发表于 2023-12-25 20:25
啊这。不如解释一下单源最短路径问题中对于负权值和负权值回路为什么不能使用上述算法
$ @* x1 u1 C( m
2 b% S* B# R1 U+ @7 w这玩意考试考得头 ...

& [- D; \3 V( N4 R' d' s+ ?我也头大了.....但本质还是因为Dijkstra算法认为，如果有一条最短路线可以直达目的地，那么从旁边走另外的路将会直接不考虑，但在负权边这里，反而会减小cost，所以Dijkstra算法失效了，因为无法发现这条最短的路径
" w" Q! `, _0 m

Applcu 发表于 2023-12-25 21:58
先说说个人对于Dijkstra算法设计地铁线路规划：
1.首先用爬虫爬到该城市的地铁网络，包含站点名称，该站点 ...

/ _  S( l0 H7 r, O; s; R0 W可以加入正文喵
3 N. W+ B9 k; N- _7 i

Applcu 发表于 2023-12-25 21:15
真是男童啊.....

  Z" E6 d/ J& I1 d诽谤管理封七天