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

彭希仁

原帖由 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  ...

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

彭希仁

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

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

彭希仁

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


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

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

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

灰袍法师

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

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

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

彭希仁

原帖由 灰袍法师 于 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

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

彭希仁

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

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

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


还是等着学习高 ...

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

winland

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

HHAAMM

偶在琢磨动态规划，各个段该怎么划定范围，怎么计算！！
版版们在用递归
偶想，有一点是应该先做的
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

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

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