求A点到B点之间最短的一条路线(看谁速度最快)

彭希仁 · 发表于 2008-11-7 18:36

原帖由 HHAAMM 于 2008-11-7 12:56 发表
先看下27楼的内容
先大概来个思路（有些情况下会出错，怎么处理还没想好）
不知对不，但感觉就该这么解决这种问题
Sub abc()
Dim x%, y%
ar1 = Range("a2:ae32")
For x = 29 To 2 Step -1
For y = 30 To ...

运行效率太低了,需要再优化一下.

彭希仁 · 发表于 2008-11-7 18:39

原帖由 apolloh 于 2008-11-7 11:26 发表
应该存在2条以上最短路程的可能。

是的,存在很多条最短的路线,如果按需30000行来算,那么不知有多少了,为了简化,只需求出一条就行了.

彭希仁 · 发表于 2008-11-7 18:46

原帖由 apolloh 于 2008-11-7 12:09 发表

如果这样可以2-〉6为什么就不行呢？都是对角线，如果2-〉6可以那么1-〉6又怎么不行能？

是不是这个对角线还是不能算？

呵呵,不能算也可以,这个并不重要.要算1>6这样的对角线,那题的难度就太大了.

灰袍法师 · 发表于 2008-11-7 20:08

看杂志见过一个很巧妙的解决方法

先制造跟路线图一模一样的微小管道，往管道里面充满导电气体

然后在AB两点施加强电压，击穿气体的时候，通电的路径就是最短路径

彭希仁 · 发表于 2008-11-7 20:21

原帖由 灰袍法师 于 2008-11-7 20:08 发表
看杂志见过一个很巧妙的解决方法

先制造跟路线图一模一样的微小管道，往管道里面充满导电气体

然后在AB两点施加强电压，击穿气体的时候，通电的路径就是最短路径

我的解法是灌水法,30000行只需要3秒就可以搞定,

其中这二句花了2秒多钟

arr = Range("A1:AE" & [b65536].End(xlUp).Row)
..............
Range("A1:AE" & [b65536].End(xlUp).Row) = arr

[ 本帖最后由彭希仁于 2008-11-7 20:24 编辑 ]

yclotus · 发表于 2008-11-7 21:00

顶一下楼主，老是出人意料。。。

彭希仁 · 发表于 2008-11-7 21:41

原帖由 yuanhongly 于 2008-11-7 16:28 发表
425553自己弄了下。胡搅蛮缠 + 胡思乱想+ 文不对题+误解楼主原意

但是有点像在找路了。哈哈只看运行效果还有点像那么回事，只是偶尔会找错路

看完代码你会拿石头砸我的！！哈哈

还是等着学习高 ...

思路不错,接着优化一下,也许就出来了.

winland · 发表于 2008-11-7 22:40

发现用我之前那个五色球中最短路径的方法在3000行时就会出现堆践溢出，可能跟太多的递归有关。算了，就等着看答案。。。

HHAAMM · 发表于 2008-11-8 00:09

偶在琢磨动态规划，各个段该怎么划定范围，怎么计算！！
版版们在用递归

偶想，有一点是应该先做的
Sub 去除不通的路()
Dim z%, x%, y%
For z = 1 To 2
For x = 31 To 2 Step -1
      For y = 30 To 2 Step -1
         If Cells(x, y) <> "" Then
            If Cells(x, y - 1) = "" And Cells(x + 1, y) = "" And Cells(x, y + 1) = "" Then Cells(x, y) = ""
            If Cells(x + 1, y) = "" And Cells(x, y + 1) = "" And Cells(x - 1, y) = "" Then Cells(x, y) = ""
         End If
      Next y
Next x

For x = 2 To 31
      For y = 2 To 30
         If Cells(x, y) <> "" Then
            If Cells(x + 1, y) = "" And Cells(x, y - 1) = "" And Cells(x - 1, y) = "" Then Cells(x, y) = ""
            If Cells(x, y - 1) = "" And Cells(x - 1, y) = "" And Cells(x, y + 1) = "" Then Cells(x, y) = ""
         End If
      Next y
Next x
Next z
End Sub

HHAAMM · 发表于 2008-11-8 00:14

下一步再去除一些无意义的通道（还没想好）

偶把情况设想的很复杂，有些复杂的情况，“生成道路”按钮好像并不能生成！！

		自动登录	找回密码
密码			免费注册

[讨论] 求A点到B点之间最短的一条路线(看谁速度最快)