最远能走多远

aimisiyou

n个人，第i个人携带的食物为ei，第i个人行走单位距离消耗的食物为ci，给定n个人的一个排列（1,2,3……n）,则最后一人能走的最远距离为
f(1,2,3,……n)=e1/(c1+c2+……+cn)+e2/(c2+c3+c4+……cn)+e3/(c3+c4+……+cn)+……+en/cn，可简单理解为大家一起出发，先共用第一人的食物（不消耗自己的食物），直至消耗完第一人的食物，此时第一人停在该处并脱离队伍，接着剩下的n-1个人共用第二人的食物继续前行，直至第二人离队……直至最后一人独自消耗完自己的食物。
求如何排列，使得最后一人走的距离最远？

tzfcn

预测一下商情能够发展的程度，什么时候基本**住。

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_bestnew)))