机器人登山问题

hujunhua

不过，从n!个排列中去筛选的话，不管筛选条件多么简明，都不是好算法吧。因为规模已经从  n 变成了 n!.

zeroieme

O(n)感觉不可能。

从n!/4减到n!/2^(n/2)算一点进步吧。

KeyTo9_Fans

我目前找到的最好的算法，时间复杂度是$O(n*2^n)$，空间复杂度是$O(2^n/\sqrt{n})$。

该算法能解决$n=30$左右的规模，对于$n=100$仍然无能为力。

以$4$个机器人$a$、$b$、$c$、$d$为例，算法的流程如下图所示：



首先我们可以得到$1$个机器人登顶的最优方案。

$2$个机器人登顶，有$2$种方案，比较一下即可找出较优方案。

$3$个机器人登顶，选择$1$个机器人垫底，有$3$种方案。选定后，根据$2$个机器人登顶的较优方案，得到这个机器人垫底的最佳结果。比较$3$个机器人垫底的结果，得到最优方案。

$4$个机器人登顶，选择$1$个机器人垫底，有$4$种方案。选定后，根据$3$个机器人登顶的最优方案，得到这个机器人垫底的最佳结果。比较$4$个机器人垫底的结果，得到最优方案。

于是当机器人的个数为$n$时，需要按顺序求出$n$个机器人的任意子集登顶的最优方案，一共要求$2^n$个子集。

每个子集需要$O(n)$的时间得到登顶的最优方案，于是该算法的时间复杂度是$O(n*2^n)$。

空间方面，第$n/2$层是瓶颈，复杂度是$C(n,n/2)=O(2^n/\sqrt{n})$。

KeyTo9_Fans

终于找到了更好的算法，该算法的时间复杂度是`\color{wheat}{O(\alpha^n\cdot n^2)}`，空间复杂度是`\color{wheat}{O(\beta^n/\sqrt{n})}`，

其中`\color{wheat}{\alpha=1+\ln 2=1.6931...，\beta=2^(1/\alpha)=1.5058...}`。

该算法的复杂度仍然是指数级的，只是优化了底数而已，

能解决$ $n=35$ $左右的规模，对于$ $n=100$ $仍然无能为力。

#####

很遗憾，这个算法找不到最优解。我再继续想想能不能补救。

#####

补救不了，楼上的算法仍然是目前已知的效率最高的找准确解的算法。

aimisiyou

感觉跟tsp问题类似，遗传算法可以得到近似较优解。

aimisiyou

KeyTo9_Fans 发表于 2015-6-4 20:25
我目前找到的最好的算法，时间复杂度是$O(n*2^n)$，空间复杂度是$O(2^n/\sqrt{n})$。

该算法能解决$n=30 ...

路径数仍是n！啊。求准确解算法的复杂度不可能比这个更优了吧？

aimisiyou

考虑最优路径下的两个相邻个体，为（……（x,y）(a,b)……），sum=b+……，则有（1-（b/a）*(x/y))*sum+y-b>0。
采用倒推（最后一个选取e/c最大）+贪心算法，接着在（1-（b/a）*(x/y))*sum+y-b>0的条件下逐步倒推选择（x,y），使得x/(sum+y)的值最大。

按照上述贪心法，最后判断条件都小于0了。说明第8号必须排在第1位。将第8号位移到第1位后，2-8号位的判断条件都小于0，所以第9位移到第2位上。
……
直到判断条件出现>0情况（如图33）。
……
又出现判断条件都小于0的情况（如图44），此时将第10位移动至第4位。
当最后一人的判断条件大于0时，贪心算法完成（如图55）。

aimisiyou

感觉这跟两两排序最终得到整体的有序类似，贪心算法结果只是保证了每次都是递增，但不一定是最优结果（递增的最多）。

aimisiyou

贪心算法得到的不是最优路径。

aimisiyou

用遗传算法求得的最大值为40.0686
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
  (fix (* n (rnd)))
)
(defun pick (lst i j)
   (setq count (length lst) nc 0 picklst nil)
   (while (<= nc j)
       (if (<= i nc)
           (setq picklst (cons (nth nc lst) picklst))
       )
      (setq nc (+ nc 1))
   )   
   (reverse picklst)
)
(defun xipai (n)
  (setq i 1 j 0 klst nil)
  (while (<= i n)
      (setq klst (cons i klst))
      (setq i (+ 1 i))
   )
   (while (<= j 20)
         (setq i_pot (rnd_n n))
         (setq j_pot (rnd_n n))
         (setq nmin (min i_pot j_pot))
         (setq nmax (max i_pot j_pot))
         (setq klst (append (pick klst  (+ 1 nmax) (- n 1)) (pick klst (+ 1 nmin) nmax) (pick klst 0 nmin)))
         (setq j (+ j 1))
   )
   (mapcar '1- klst)
)
(defun fitfun (ptlst)
  (setq c_sum (apply '+ (mapcar 'cadr ptlst)) sum 0)
  (foreach pt ptlst
     (progn
        (setq sum (+ sum (/ (car pt) 1.0  c_sum)))
            (setq c_sum (- c_sum (cadr pt)))
          )
  )
  sum
)
(setq pts '((0 23 1)(1 25 2)(2 16 3)(3 25 7)(4 30 10)(5 25 9)(6 18 10)(7 15 9)(8 7 6)
            (9 4 2)(10 9 4)(11 16 9)(12 14 8)(13 11 5)(14 15 6)(15 10 9)(16 5 7)(17 1 8))
)
(setq poplst nil)
(repeat 100
  (setq plst (xipai (length pts)))
  (setq poplst (cons plst poplst))
)
(defun n-pt (nlst)
  (mapcar '(lambda (x) (cdr (nth x pts))) nlst)
)
(setq p_best  (car (vl-sort (mapcar '(lambda (x y) (cons (fitfun (n-pt x)) y))
                                      poplst
                                      poplst
                                                          )  
                              '(lambda (e1 e2)  (> (car e1) (car e2)) )
                      )                          
                )
)
(setq p_chane 0.02  N_d 3000 ii 0)
(while (< ii N_d)
   (setq vlst nil)
   (foreach en poplst
       (setq nt (length en))
       (setq  ens en pc1 (nth (rnd_n nt) ens) flag t clst (list pc1))
       (while flag
            (setq r_rnd (rnd))
            (if (< r_rnd p_chane)
                            (setq pc2 (nth (rnd_n (- nt 1)) (vl-remove pc1 ens)))
                (progn
                    (setq en_rnd (nth (rnd_n nt) poplst))
                                        (if (= pc1 (last en_rnd))
                                            (setq pc2 (car en_rnd))
                                            (setq pc2 (cadr (member pc1 en_rnd)) )
                                        )   
                                 )
                          )
                         (if (or (= pc2 (cadr (member pc1 ens))) (= pc1 (cadr (member pc2 ens))) )
                             (setq flag nil)
                 (progn
                    (if (member pc2 (member pc1 ens))
                        (setq ens (append (reverse (member pc1 (reverse ens))) (member pc2 (reverse (cdr (member pc1 ens)))) (cdr (member pc2 ens)) ))
                          (setq ens (append (reverse (member pc2 (reverse ens))) (member pc1 (reverse (cdr (member pc2 ens)))) (cdr (member pc1 ens)) ))
                     )
                     (setq pc1 pc2)
                                         (setq clst (cons pc1 clst))
                                         (if (= (length clst) (- nt 1))
                                             (setq flag nil)
                                          )
                                 )
                         )
           )
      (if (> (fitfun (n-pt ens)) (fitfun (n-pt en)))
              (setq vlst (cons ens vlst))
              (setq vlst (cons en  vlst))
           )
        )
   (setq ii (+ 1 ii))
   (setq poplst vlst)
   (setq p_bestnew  (car (vl-sort (mapcar '(lambda (x y) (cons (fitfun (n-pt x)) y)) poplst poplst)  
                                             '(lambda (e1 e2)  (> (car e1) (car e2)) )
                                    )
                                )
                 )
  (if (> (car p_bestnew) (car p_best))
      (setq  p_best p_bestnew)
   )
)
(setq tsp_pts (n-pt (cdr p_best)))
RND
RND_N
PICK
XIPAI
FITFUN
((0 23 1) (1 25 2) (2 16 3) (3 25 7) (4 30 10) (5 25 9) (6 18 10) (7 15 9) (8 7 6) (9 4 2) (10 9 4) (11 16 9) (12 14 8) (13 11 5) (14 15 6) (15 10 9) (16 5 7) (17 1 8))
nil
((16 15 4 14 2 6 12 10 8 11 9 17 13 1 0 5 3 7) (6 15 17 12 3 5 16 8 14 4 0 13 2 7 11 10 1 9) (1 11 7 10 13 14 9 12 2 15 8 16 0 17 6 5 4 3) (7 16 10 9 3 0 15 14 2 13 8 11 1 17 6 5 4 12) (14 13 11 7 10 8 1 17 5 6 4 15 12 16 2 0 9 3) (9 0 15 7 13 4 12 11 10 3 8 17 2 16 5 14 1 6) (15 13 4 9 0 8 10 1 12 5 14 16 3 2 6 11 7 17) (4 9 7 6 2 14 17 11 3 8 16 13 15 5 10 1 12 0) (13 12 7 11 10 6 0 8 9 1 4 17 14 16 5 15 3 2) (5 0 1 8 3 4 6 16 2 15 11 10 9 12 17 14 7 13) (17 16 7 3 8 5 10 0 14 13 12 2 6 9 11 15 1 4) (10 4 7 3 17 16 11 6 15 13 9 8 1 14 2 0 12 5) (6 5 0 3 9 7 4 12 11 13 14 2 8 16 17 15 1 10) (12 15 14 8 13 5 9 3 7 17 4 1 11 2 0 6 16 10) (13 7 1 9 2 0 6 3 5 8 4 12 10 14 11 17 16 15) (2 5 6 9 0 16 15 12 7 3 11 13 1 14 10 8 17 4) (11 10 12 14 2 1 6 16 7 13 8 4 3 5 0 15 17 9) (6 1 17 0 16 2 15 14 13 12 11 8 3 9 10 5 7 4) (4 9 14 15 17 8 12 2 10 5 0 11 1 3 7 16 6 13) (1 17 6 12 11 4 2 8 9 7 10 3 15 16 14 0 5 13) (1 10 5 8 7 11 9 12 16 13 4 3 0 17 6 14 2 15) (7 14 13 2 4 15 1 12 6 16 5 17 10 0 3 11 8 9) (14 13 2 1 6 12 0 16 3 7 11 10 17 15 9 8 5 4) (14 13 9 6 16 1 0 7 3 11 10 2 4 8 5 17 15 12) (7 10 12 9 8 5 4 16 15 14 1 2 11 13 3 17 0 6) (4 16 2 10 8 7 1 15 6 0 13 5 17 3 9 12 11 14) (10 9 3 16 15 11 6 12 7 1 0 17 4 13 14 2 8 5) (11 6 15 13 14 0 2 1 16 3 8 7 9 10 5 12 4 17) (14 15 7 17 11 8 16 9 0 10 1 4 12 13 3 2 6 5) (14 3 7 5 1 0 4 12 9 8 6 15 13 17 2 16 10 11) (13 12 11 16 0 9 6 4 14 7 10 3 17 2 8 5 1 15) (14 15 6 8 4 17 16 1 9 11 12 3 5 13 7 0 10 2) (15 13 3 0 17 1 7 10 16 11 14 8 4 9 6 5 12 2) (8 0 11 13 6 5 4 15 14 10 2 17 9 7 3 12 1 16) (2 10 13 1 6 16 8 0 12 15 7 11 3 17 14 4 5 9) (5 7 1 0 6 14 11 9 8 3 17 12 2 4 13 15 10 16) (15 12 0 13 10 3 5 11 14 7 9 2 6 4 16 8 1 17) (6 3 17 16 15 4 13 5 8 11 9 2 10 7 1 0 12 14) (7 11 1 12 0 4 15 16 2 9 14 13 5 10 17 6 8 3) (17 16 1 12 7 0 6 8 11 10 3 9 15 14 5 4 2 13) (4 3 15 13 2 8 5 11 1 6 14 7 16 10 9 12 0 17) (0 17 7 6 1 13 5 14 3 9 16 11 2 10 8 12 15 4) (17 16 7 3 15 9 2 6 5 13 10 12 11 8 4 1 0 14) (7 3 1 15 6 5 8 13 0 12 11 10 9 4 14 17 2 16) (12 11 9 10 17 3 0 8 13 15 16 7 6 5 14 2 4 1) (12 16 4 11 2 6 1 3 9 15 5 10 7 14 8 13 17 0) (16 1 5 15 10 8 7 11 6 17 9 0 14 13 2 4 3 12) (10 3 13 7 2 15 14 9 11 0 6 17 12 4 8 1 16 5) (8 10 14 12 9 7 1 17 13 6 5 4 0 3 2 11 16 15) (3 7 6 8 0 15 1 17 2 12 9 4 13 5 14 16 11 10) (14 0 13 6 10 9 1 2 12 11 8 3 16 15 5 17 4 7) (13 2 5 16 11 17 10 6 3 14 1 7 15 8 12 0 4 9) (9 1 4 17 16 2 12 5 15 3 0 11 8 10 13 7 6 14) (6 4 3 2 16 15 10 7 1 9 8 13 17 11 12 0 5 14) (17 16 8 12 6 13 0 1 3 11 7 15 14 5 10 4 2 9) (4 8 7 15 2 13 5 12 9 14 11 10 0 1 17 3 6 16) (16 9 14 5 1 8 6 13 17 15 12 0 4 7 2 11 3 10) (0 4 7 6 14 13 12 2 15 17 10 1 9 16 3 5 11 8) (14 3 1 9 7 0 8 13 16 15 12 4 11 5 6 10 17 2) (17 9 2 16 7 13 5 14 8 10 11 15 3 6 4 12 1 0) (4 8 7 13 10 12 11 6 17 1 16 0 14 2 9 3 5 15) (11 9 10 12 14 5 8 3 2 1 17 0 6 4 15 16 13 7) (12 11 17 0 7 6 2 5 3 14 10 15 16 1 4 13 9 8) (0 4 12 3 13 8 7 2 10 6 5 17 9 15 16 1 11 14) (0 10 16 8 5 1 12 7 9 13 6 4 2 17 15 14 11 3) (17 0 5 13 12 6 2 4 16 15 9 11 3 14 10 1 8 7) (4 14 13 17 15 7 16 11 6 5 1 0 9 8 12 10 2 3) (7 13 12 10 9 3 2 0 6 4 15 11 5 16 1 14 17 8) (16 7 6 3 1 13 4 9 5 17 2 0 15 12 11 10 14 8) (8 7 11 2 1 10 13 12 3 15 17 9 6 5 16 0 14 4) (6 8 15 2 5 12 11 13 10 0 17 4 3 1 14 9 7 16) (4 3 9 15 14 11 16 13 5 17 12 10 7 6 1 0 8 2) (8 2 4 17 9 11 10 6 15 1 0 13 12 7 16 3 14 5) (17 6 11 3 4 14 1 13 12 5 7 2 10 8 0 9 16 15) (5 0 16 7 4 9 8 2 17 3 14 15 1 13 6 10 12 11) (8 17 16 15 13 10 4 14 12 3 0 11 9 5 6 1 2 7) (15 7 17 16 0 5 4 8 2 1 3 13 14 11 10 9 6 12) (5 9 0 7 8 3 6 10 12 4 17 16 14 13 2 11 1 15) (11 2 15 6 9 8 17 0 3 10 14 13 7 16 12 5 4 1) (5 4 7 14 15 0 13 10 17 16 6 2 9 3 1 8 12 11) (14 1 0 4 8 17 7 6 15 3 13 16 12 9 2 5 11 10) (12 6 16 13 7 1 17 5 15 10 4 8 0 11 2 9 3 14) (5 4 13 7 10 0 12 11 9 8 16 15 17 6 3 2 1 14) (9 8 7 4 14 13 6 12 5 10 2 11 17 1 0 3 15 16) (13 0 2 17 16 5 14 3 8 15 7 10 9 12 11 1 4 6) (2 15 16 9 3 17 8 11 10 14 5 0 1 4 6 7 12 13) (6 15 17 14 0 4 3 2 9 12 5 8 16 7 13 11 1 10) (17 16 6 4 12 5 0 9 1 3 2 11 10 8 7 14 13 15) (12 8 6 0 17 3 14 7 11 16 9 1 10 5 13 15 4 2) (1 14 13 8 5 7 12 2 15 17 4 10 11 3 9 0 16 6) (2 14 9 5 3 12 0 16 1 11 10 6 15 8 4 7 17 13) (6 3 7 16 13 10 9 0 5 15 14 4 11 12 2 1 8 17) (8 14 15 17 11 4 13 5 6 12 3 16 1 7 10 9 2 0) (5 7 13 1 6 4 2 0 9 10 3 17 16 8 15 12 14 11) (5 14 9 13 3 12 8 16 17 4 2 1 0 11 10 6 15 7) (7 2 6 12 0 15 3 14 9 13 4 5 10 1 11 8 16 17) (12 11 17 10 16 14 15 9 3 0 13 2 1 5 8 7 6 4) (15 3 2 8 7 16 14 11 10 12 0 6 5 9 4 17 13 1) (2 9 14 13 10 6 17 4 12 3 1 0 7 16 5 15 11 8) (5 4 3 8 12 15 7 6 11 10 9 16 17 0 13 2 1 14))
N-PT
(37.078 17 9 2 16 7 13 5 14 8 10 11 15 3 6 4 12 1 0)
0
nil
((1 8) (5 7) (10 9) (7 6) (15 9) (18 10) (16 9) (14 8) (4 2) (11 5) (9 4) (25 9) (30 10) (15 6) (25 7) (16 3) (25 2) (23 1))
p_best
(40.0686 17 16 15 8 7 6 11 12 9 13 10 5 4 14 3 2 1 0)