TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。

      假设现在有四个城市，0,1,2,3，他们之间的代价如图一，可以存成二维表的形式

                      图一                                                                                               

        现在要从城市0出发，最后又回到0，期间1，2，3都必须并且只能经过一次，使代价最小。

2.动态规划可行性

        设s, s1, s2, …, sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, …, sp, s一定构成一条从s1到s的最短路径，所以TSP问题是构成最优子结构性质的，用动态规划来求解也是合理的。

3.推导动态规划方程

        假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。

        推导：(分情况来讨论)

        ①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的 城市3->城市0(0为起点城市)。此时d(i, V’)=Cis(就是 城市i 到 城市s 的距离)、

        ②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一个，并求出最优解。

           d(i, V’)=min{Cik +  d(k, V’-{k})}

           注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。

        综上所述，TSP问题的动态规划方程就出来了：

4.实例分析

     现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)

    ①我们要求的最终结果是d(0,{1,2,3}),它表示，从城市0开始，经过{1,2,3}之中的城市并且只有一次，求出最短路径.

    ②d(0,{1,2,3})是不能一下子求出来的，那么他的值是怎么得出的呢？看上图的第二层，第二层表明了d(0,{1,2,3})所需依赖的值。那么得出：

       d(0,{1,2,3})=min  {

                                    C01+d(1,{2,3})

                                    C02+d{2,{1,3}}

                                    C03+d{3,{1,2}}

                                  }

     ③d(1,{2,3})，d(2,{1,3})，d(3,{1,2})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3})

       d(1,{2,3})=min{

                              C12+d(2,{3})                             

                              C13+d(3,{2})

                              }

       d(2,{1,3})，d(3,{1,2})同样需要这么求。

    ④按照上面的思路，只有最后一层的，当当V’为空集时，Cis的值才可以求，它的值是直接从

这张表里求得的。

     5.编程思路

        将d(i, V’)转换成二维表，d[i][j]

        在程序中模拟填表的过程，主要要考虑到j这个参数的表示，它要代表一个集合，可以用二维数组来表示。

   6.源代码

注：由于本人水平有限，并且主要在这里是体现思路，所以程序并不是很完善，代码质量也不高，很地方可以写得通用一些，所以这里只是提供一个参考，程序的进一步完善，由读者自由发挥。

#include 
#include

int IsIncluded(int x,int array[3])//x是否包含在数组中 
{ 
    if((array[0] != x) && (array[1] != x) && (array[2] != x)) 
        return 0; 
    return 1; 
} 
int Left(int k,int array[3],int V[8][3])//实现V'-{k} 的下标检索 
{ 
    int i = 0,index = 0,array_0_count = 0,array_1_count = 0,array_2_count = 0,array_3_count = 0; 
    int V_0_count = 0,V_1_count = 0,V_2_count = 0,V_3_count = 0; 
    int temp[3]; 
    for(i = 0; i < 3; i++) 
        temp[i] = array[i]; 
    for(i = 0; i < 3; i++) 
        if(temp[i] == k) 
            temp[i] = 0;  //相当于去掉k这个城市 
    for(i = 0; i < 3; i++) 
    { 
        if(temp[i] == 0) 
            array_0_count++; 
        else if(temp[i] == 1) 
            array_1_count++; 
        else if(temp[i] == 2) 
            array_2_count++; 
        else 
            array_3_count++; 
    } 
    for(index = 0; index < 8; index++) 
    { 
        for(i=0; i < 3; i++) 
        { 
            if(V[index][i] == 0) 
                V_0_count++; 
            else if(V[index][i] == 1) 
                V_1_count++; 
            else if(V[index][i] == 2) 
                V_2_count++; 
            else 
                V_3_count++; 
        } 
        if((array_0_count == V_0_count) && (array_1_count == V_1_count) 
            && (array_2_count == V_2_count) && (array_3_count == V_3_count)) 
            return index; 
        V_0_count = 0; 
        V_1_count = 0; 
        V_2_count = 0; 
        V_3_count = 0; 
    } 
    return 0; 
}

void TSP(int d[4][8],int c[4][4],int V[8][3],int n) 
{ 
    int i = 0,j = 0,k = 0;

    for(i = 1; i < n; i++)//V'为空时，给赋值， 
        d[i][0] = c[i][0];

    for(j = 1; j < 7; j++)//按列遍历不同集合，{1},{2},{3},{1,2},{1,3}..... 
    { 
        for(i = 1; i < n; i++)//遍历城市1，2，3 
        { 
            if( !IsIncluded(i,V[j]) )//i必须不在集合中，否则就属于经过两次，不符合题意 
            { 
                for(k = 0; k < 3; k++)//分别试探集合中的每一点，取最小值 
                { 
                    if((V[j][k] != 0) && ((c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)]) < d[i][j])) 
                        d[i][j] = c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)]; 
                } 
            } 
        }//end of     for(i = 1; i < n; i++)//遍历城市1，2，3 
    }//end of for(j = 1; j < ((int)pow(2,n)-1); j++) 
    for(k = 0; k < 3; k++)//分别试探下一步为集合中的任何一点，取最小值 
    { 
        if((V[7][k] != 0) && (c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)]) < d[0][7]) 
            d[0][7] = c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)]; 
    } 
} 
void main() 
{ 
    int V[8][3]= 
    { 
        0,0,0, 
        0,0,1, 
        0,0,2, 
        0,0,3, 
        0,1,2, 
        0,1,3, 
        0,2,3, 
        1,2,3 
    }; 
    int c[4][4]= 
    { 
        0,3,6,7, 
        5,0,2,3, 
        6,4,0,2, 
        3,7,5,0 
    }; 
    int d[4][8]={0},i=0,j=0;

    for(i=0; i<4; i++) 
        for(j=0; j<8; j++) 
            d[i][j]=1000;   //假设1000为无穷大 
    TSP(d,c,V,4); 
    printf("The least road is:%d/n",d[0][7]); 
}

import random a=random.randint(0,1001)#这个生成的区间是 [0,1001] a=random.randrange(0,10001)#生成的是区间是[0,1001) print a

random.randrange([start], stop[, step])

Return a randomly selected element from range(start, stop, step). This is equivalent tochoice(range(start, stop, step)), but doesn’t actually build a range object.

And range(start, stop) returns [start, start+step, ..., stop-1], not [start, start+step, ..., stop]. As for why... zero-based counting rules and range(n) should return n elements, I suppose. Most useful for getting a random index, I suppose.

While randint is documented as:

random.randint(a, b)

Return a random integer N such that a <= N <= b. Alias for randrange(a, b+1)

So randint is for when you have the maximum and minimum value for the random number you want.

s1 = "hello,world" 
如果要写成多行，那么就要使用/ (“连行符”)吧，如 
s2 = "hello,/ 
world" 
s2与s1是一样的。如果你用3个双引号的话，就可以直接写了，如下： 
s3 = """hello, 
world, 
hahaha."""，那么s3实际上就是"hello,/nworld,/nhahaha.", 注意“/n”

The algorithm2e package (first released 1995, latest updated December 2009 according to the v4.01 manual) allows typesetting algorithms with a lot of customization. The package is loaded like

\usepackage[options]{algorithm2e} 

and a simple example, taken from the v4.01 manual, is

\begin{algorithm}[H]
 \SetAlgoLined
 \KwData{this text}
 \KwResult{how to write algorithm with \LaTeX2e }
 initialization\;
 \While{not at end of this document}{
  read current\;
  \eIf{understand}{
   go to next section\;
   current section becomes this one\;
   }{
   go back to the beginning of current section\;
  }
 }
 \caption{How to write algorithms}
\end{algorithm}

which produces 

http://www.mathworks.com/help/matlab/ref/plot.html 

例子：

还是举简单的例子个大家：在0≤x≤2p区间内，绘制曲线y1=2e-0.5x和y2=cos(4πx)，并给图形添加图形标注。 
x=0:pi/100:2*pi;
y1=2*exp(-0.5*x);
y2=cos(4*pi*x);
plot(x,y1,x,y2)
title('x from 0 to 2{\pi}');                %加图形标题    
xlabel('Variable X');                       %加X轴说明          
ylabel('Variable Y');                       %加Y轴说明 
text(0.8,1.5,'曲线y1=2e^{-0.5x}');          %在指定位置添加图形说明 
text(2.5,1.1,'曲线y2=cos(4{\pi}x)'); 
legend('y1','y2')                           %加图例 
复制代码
 

plot

Syntax

 
Reshape a 3-by-4 matrix into a 2-by-6 matrix.
A =     1    4    7    10
        2    5    8    11
        3    6    9    12            

B = reshape(A,2,6)            
B =     1    3    5    7    9   11     
        2    4    6    8   10   12 
B = reshape(A,2,[])
 
B =     1    3    5    7    9   11     
        2    4    6    8   10   12 

Matlab 方括号“[ ]”的作用
 1定义矩阵（向量，数组）。
                例如 a=[1 2 3;4 5 6] 
2.定义函数的返回参数列表（输出变量宗量）。
               例如 [m,n]=size(a)                如果函数的返回参数只有一个，中括号一般省略。即  [n]=rand(1,2); 可写作  n=rand(1,2);

str = raw_input("Enter your input: "); print "Received input is : ", str

del dict['Name']; # remove entry with key 'Name' dict.clear();     # remove all entries in dict del dict ;        # delete entire dictionary

演示代码：

\documentclass{article}
\setlength\textwidth{245.0pt}
\usepackage{CJK}
\usepackage{indentfirst}
\usepackage{amsmath}

\begin{CJK*}{GBK}{song}
\begin{document}
方法一：

$$ f(x)=\left\{
\begin{aligned}
x & = & \cos(t) \\
y & = & \sin(t) \\
z & = & \frac xy
\end{aligned}
\right.
$$

方法二：

$$ F^{HLLC}=\left\{
\begin{array}{rcl}
F_L       &      & {0      <      S_L}\\
F^*_L     &      & {S_L \leq 0 < S_M}\\
F^*_R     &      & {S_M \leq 0 < S_R}\\
F_R       &      & {S_R \leq 0}
\end{array} \right. $$

方法三:

$$f(x)=
\begin{cases}
0& \text{x=0}\\
1& \text{x!=0}
\end{cases}$$

\end{CJK*}
\end{document}

问题描述