⑴ C++算法，动态规划法实现TSP问题
c++listmatrixiteratoriostream算法
[cpp] view plainprint?
#include
#include
using namespace std ;
typedef list<</SPAN>int> LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; //路径权值
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;j
{
i=list_org.begin();
for(int k=1;k
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalue
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout<<"旅行商问题动态规划算法"<<endl;
cout<<"路线长度的矩阵表示如下 （-1表示无限大）"<<endl;
for(int j=0;j
cout<<endl;
for(int k=0;k
cout<<" "<<d[j][k];
}
}
cout<<endl;
cout<<"计算结果:"<<getPath(4,list_org)<<endl;
list_result.push_front(1);
list_result.push_back(1);
cout<<"要走的路径:---->:";
for (h = list_result.begin(); h != list_result.end(); ++h)
cout << *h << " ";
cout << endl;
int i;
cin>>i;
return 0;
}
⑵ 算法的时间复杂度
时间复杂度的表示: O(执行次数)
一个有序的元素列表查找某个元素可以用二分查找，每次取中间元素进行比较大小，直到相等。因为每次不符合时总会排除一半的元素 ，所以查找的次数为log2n，那么时间复杂度为O(log2n)。如果是一个无序的元素列表，查找从位置0开始，那么简单查找的次数为n，那么时间复杂度为O(n)。
除此之外快速排序为O(n*log2n)，选择排序为O(n*n)。
旅行算法就是n个旅行地点，你可从某个地方出发到余下某下一个地点，走完所有地点。从最开始时走有n个地点可以选择，接下来再走就有n-1个地点可以选择，这样直到只有一个地点可以选择。那么所有你可走的路径就是一个阶乘，选择复杂度为O( n!)。
关于数组和链表的操作。先说数组，因为你有了元素的索引，可以随机访问，你就能快速找到这个元素，而且所有元素的读取都是一样的步骤，所以读取时间复杂度为O(1)，数组的插入和删除的时间复杂度为O(n)，因为要移动元素。链表的特性是每个都存储了下一个元素的地址，只能顺序访问。那么读取插入删除的时间复杂度分别是O(n)、O(1)、O(1)。
⑶ Dijkstra算法时间复杂度
我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。
对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。相关问题和算法
在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。
OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。
与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。
与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。
如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。