空间集合与空间集合之间最优路径选择

seagate

主要场景来源于护镖机器人，一开始的时候林震南给出的伙计位置和预设路径之间最优路径选择。由于伙计位置常常会有10多个重复名字的房间，而预设路径一般来说我的护镖路线是固定死的，
想法就是找离护镖路线最近并且最靠路线后面位置的房间。下面是一个cmud 237开发的递归路线
寻找算法。是一个xml文件。我预设是最大递归层级为4级，大于四级就是寻找失败。

其中$targetlist为林镇南给的信息后找到的房间集合，是一个list，list元素是房间信息的db record，
key分别是direct-方向，id-房间号，name-房间名称，relationid-邻居房间号，relationname-邻居房间名称
$pathlist是预设护镖路线的房间号list
$level是递归到多少层级，初始为0
$targetpath是上一层递归找到的路径房间号list
最终返还结果$rtn_struct是一个db record，pathsno为在行镖路线上定位位置，targetpath为从目的地到行镖
指定房间号的list

函数@batch_room_info($condition)为取出指定条件的房间信息集合。一个对地图数据库搜集信息的函数。
实际上你用cmud自带的地图函数一样可以加工出这个返回结构，我使用ado对象对access数据库处理获得的。


    #local $target_room,$pathid,$condition,$batchlist,$rtn_struct,$temppath,$tmp_struct
$target_room=""
$c
$rtn_struct=""
$tmp_struct=""
$batchlist=""
$pathid=0
#if ($level=0&&$targetpath=-1) {$targetpath=""}
#addkey $rtn_struct {pathsno=0|targetpath=""}
#new $tmp_struct $rtn_struct
#loop %numitems($targetlist) {
  $target_room=%item($targetlist,%i)
  #va $temppath %additem($target_room.id,$targetpath)
  #loop %numitems($pathlist) {
    #if %item($pathlist,%j)=$target_room.id {
      $pathid=%j
      }
    }
--此处为上一步从预设路线成功定位并且这个位置比上一个成功结果更靠后就用这个结果
  #if ($pathid!=0&&$pathid>=$rtn_struct.pathsno) {
    #if $pathid=$rtn_struct.pathsno {
--当两次结果位置相同，但是本次计算路径更短用本次计算路径
      #if %numitems($rtn_struct.targetpath)>%numitems($temppath) {
        $rtn_struct.pathsno=$pathid
        $rtn_struct.targetpath=$temppath
        }
      } {
      $rtn_struct.pathsno=$pathid
      $rtn_struct.targetpath=$temppath
      }
    } {
    #if $level<=4 {
--路径确定失败，用本房间的邻居继续进行下一个递归层级寻找
      $condition=%concat("objectid in (",%expandlist($target_room.rel_id,","))
      $condition=%concat($condition,")")
      $batchlist=@batch_room_info($condition)
      $tmp_struct=@find_targetpath($batchlist,$pathlist,$level+1,$temppath)
--递归找到的结果比上一个结果更靠后用本次结果
      #if $tmp_struct.pathsno>$rtn_struct.pathsno {
        $rtn_struct=$tmp_struct
        }
--递归找到的结果和上一个结果同位置，但是递归结果路径更短用本次结果
      #if ($tmp_struct.pathsno=$rtn_struct.pathsno&&%numitems($tmp_struct.targetpath)<%numitems($rtn_struct.targetpath)) {
        $rtn_struct=$tmp_struct
        }
      }
    }
  }
#return $rtn_struct]]>
      $targetlist,$pathlist,$level,$targetpath
   

ksbzb

oolong

原帖由 seagate 于 2010-1-18 10:50 PM 发表
主要场景来源于护镖机器人，一开始的时候林震南给出的伙计位置和预设路径之间最优路径选择。由于伙计位置常常会有10多个重复名字的房间，而预设路径一般来说我的护镖路线是固定死的，
想法就是找离护镖路线最近并且 ...

楼主的思路俺看不懂啊...
不知道这样找huoji要多长时间，计算路径时间长不长，同时 4个id推车卡不卡呢？