问题描述
打个比方，我要去北京，有好多景点，比如A,B,C,D,E,F，每个点都有坐标，1：假设从A开始，D结束，求出一个路线最短的方案。2：假设从A开始，结束点任意，求出一个路线最短的方案。
解决方案
解决方案二：
动态规划~我猜是这个。
解决方案三：
这第一个问题和第二个问题有区别吗，简直一模一样两点间直线距离最短，做一个排序，哪个最短去那个
解决方案四：
假如说从交通大学出发，天坛公园结束，要走完每一个其他景点，求最短路径。这不是经典的最短路径的题，也不是图的遍历，反正我也不懂，求大神帮忙
解决方案五：
引用2楼ziweixinghello的回复:
这第一个问题和第二个问题有区别吗，简直一模一样两点间直线距离最短，做一个排序，哪个最短去那个
是差不多一样的，就好像小学的应用题，两个问一个意思，但是就要出两个问题
解决方案六：
引用2楼ziweixinghello的回复:
这第一个问题和第二个问题有区别吗，简直一模一样两点间直线距离最短，做一个排序，哪个最短去那个
你没明白我的意思，我不是只去一个地方，而且所有点
解决方案七：
要用代码实现吗，貌似不难吧，可以定义任意数字，从控制台输入，写一个算法模块，最后输出最短路径，距离根据输入的坐标点算出来，我也不知道最短路径用的啥算法，让计算机自己算去就可以了，只要解决问题就行，要不就百度好好研究最短路径实现的原理
解决方案八：
这可以用迭代法解决：1.先用贪心法，每次都选择距离当前点最近的没去过的点2.对于每3个点，一定有2条边已经选择过，你尝试打破一条边而去连另一条，同时查看是否有环产生。如果新的边比老的短而且无环，那就采纳，否则继续3.不断重复2这个过程，直到你找不到任何可采纳的新边，那这就是最优解了
解决方案九：
引用7楼lcf的回复:
这可以用迭代法解决：1.先用贪心法，每次都选择距离当前点最近的没去过的点2.对于每3个点，一定有2条边已经选择过，你尝试打破一条边而去连另一条，同时查看是否有环产生。如果新的边比老的短而且无环，那就采纳，否则继续3.不断重复2这个过程，直到你找不到任何可采纳的新边，那这就是最优解了
修改一下。。之前的是错的1.贪心法要找距离当前点最近且没去过且不是终点的点，最后一步才连终点2.是在路径上顺序取4个点而不是任意选3个点，变更路径的方式是中间两个点连接不改，前后两个点假设本来是1连2，4连3，现在变成1连3，4连23.重复2，注意步进为1而不是4没有求证过，但是看上去难道不是很靠谱？啊哈哈哈。。
解决方案十：
另外一个思路就是min-cutmax-flow理论，取起点和终点为source和sink，然后所有点两两相连，每一条边的权重就是管道的容量，假设source有水流出到sink，这个算法就是找出所有通路里面容量最少的那一条。算法有点复杂，找篇论文看看吧。。关键词：graph-cuts
解决方案十一：
回溯是不是有点吃力
解决方案十二：
解决方案十三：
引用9楼lcf的回复:
另外一个思路就是min-cutmax-flow理论，取起点和终点为source和sink，然后所有点两两相连，每一条边的权重就是管道的容量，假设source有水流出到sink，这个算法就是找出所有通路里面容量最少的那一条。算法有点复杂，找篇论文看看吧。。关键词：graph-cuts
大牛！
解决方案十四：
引用9楼lcf的回复:
另外一个思路就是min-cutmax-flow理论，取起点和终点为source和sink，然后所有点两两相连，每一条边的权重就是管道的容量，假设source有水流出到sink，这个算法就是找出所有通路里面容量最少的那一条。算法有点复杂，找篇论文看看吧。。关键词：graph-cuts
看着很带劲，不过这能遍历到每个点吗？如果不能的话就是最短路径了这种类型的题叫做旅游路线或者旅行商算法，是比较难，一般作为建模或者小论文的题目。我一个算法同学在亚马逊工作，说这个可以作为面试题，我的天啊，谁能在面试那一个小时解决出来啊，有个思路就不错了
解决方案十五：
弱弱的问一句，用两个循环把所有的可能都算出来之后比较总长可以不。
解决方案：
引用13楼rt77777的回复:
Quote: 引用9楼lcf的回复:
另外一个思路就是min-cutmax-flow理论，取起点和终点为source和sink，然后所有点两两相连，每一条边的权重就是管道的容量，假设source有水流出到sink，这个算法就是找出所有通路里面容量最少的那一条。算法有点复杂，找篇论文看看吧。。关键词：graph-cuts看着很带劲，不过这能遍历到每个点吗？如果不能的话就是最短路径了这种类型的题叫做旅游路线或者旅行商算法，是比较难，一般作为建模或者小论文的题目。我一个算法同学在亚马逊工作，说这个可以作为面试题，我的天啊，谁能在面试那一个小时解决出来啊，有个思路就不错了
是不容易的。。
解决方案：
引用13楼rt77777的回复:
Quote: 引用9楼lcf的回复:
另外一个思路就是min-cutmax-flow理论，取起点和终点为source和sink，然后所有点两两相连，每一条边的权重就是管道的容量，假设source有水流出到sink，这个算法就是找出所有通路里面容量最少的那一条。算法有点复杂，找篇论文看看吧。。关键词：graph-cuts看着很带劲，不过这能遍历到每个点吗？如果不能的话就是最短路径了这种类型的题叫做旅游路线或者旅行商算法，是比较难，一般作为建模或者小论文的题目。我一个算法同学在亚马逊工作，说这个可以作为面试题，我的天啊，谁能在面试那一个小时解决出来啊，有个思路就不错了
我觉得直接套用min-cut是错的。。。网上查了一下可以用geneticalgorithm。。具体没有研究。。总之很难有效率地解决。。
解决方案：
嗯。。刚才又wiki了一下，发现如果要发现确切解，复杂度是NP，也就是找出所有可能性逐一比较是目前最优的算法，也就是暴力法。其他一些算法都有各种局限性。所以。。这个题目的思路就是看破它是个NP问题，或者提供一个简单的贪心算法作为趋近解，或者其他的找出近似解的算法。。我能想到一个，就是假设路径互不相交总是比相交路径来得近。于是就沿着Y轴向下扫描，建立很多三角形，然后再改变三角形的构成，再用贪心法找最短边。虽然跟直接用贪心法算结果一样，但是会比直接用贪心法快一些。还有一些复杂的算法，看看wiki。。我暂时没时间研究。。
解决方案：
最短路径在算法中有两种，prim算法和Dijkstra算法，楼主可以wiki下基本的思路和代码样例
解决方案：
引用17楼lcf的回复:
嗯。。刚才又wiki了一下，发现如果要发现确切解，复杂度是NP，也就是找出所有可能性逐一比较是目前最优的算法，也就是暴力法。其他一些算法都有各种局限性。所以。。这个题目的思路就是看破它是个NP问题，或者提供一个简单的贪心算法作为趋近解，或者其他的找出近似解的算法。。我能想到一个，就是假设路径互不相交总是比相交路径来得近。于是就沿着Y轴向下扫描，建立很多三角形，然后再改变三角形的构成，再用贪心法找最短边。虽然跟直接用贪心法算结果一样，但是会比直接用贪心法快一些。还有一些复杂的算法，看看wiki。。我暂时没时间研究。。
这是正解。暴力法是直观的了，但是复杂度是n！。我同学给出了一个n*n的，但是我看不懂，也挺复杂的。
解决方案：
对于一个NP问题，任何小于N!的确切算法都是错的。要么就是算法有限制，要么就是算法只是取近似值。介意分享一下你同学的算法不？这问题挺有意思的
解决方案：
我记得好像是离散数学里的内容吧。记得实现过。用最暴力的办法。
解决方案：
引用20楼lcf的回复:
对于一个NP问题，任何小于N!的确切算法都是错的。要么就是算法有限制，要么就是算法只是取近似值。介意分享一下你同学的算法不？这问题挺有意思的
蛮复杂的，而且我觉得不太对。我可以发私信给你看看
解决方案：
好，拜托了，贴出来也行
解决方案：
引用20楼lcf的回复:
对于一个NP问题，任何小于N!的确切算法都是错的。要么就是算法有限制，要么就是算法只是取近似值。介意分享一下你同学的算法不？这问题挺有意思的
没关注发不了。。。下面是我同学想的//////////////////////////////////////////////////////////////////////每个位置要么是0要么是10代表还没走过1代表已经走过了比如举个例子这个二进制序列1001最右边是第一位他等于1代表1号点已经访问过了右边倒数第二位等于0代表2号点还没访问过以此类推初始的状态肯定是000000。。。1就是说只有最右边的一位是1也就是刚上来只有1号点被访问过了那么我们最终想要的状态是什么呢每个点都被访问过也就是状态11111.。。。111也就是都是1对吧？状态之间是可以转移的比如n=5刚上来是00001比如我从1可以走到2那么状态就是00011我也可以从1走到4那么状态就是01001有一点需要明确你给出了每个点的坐标那么其实就可以认为任意两点之间都可以互相到达我们先想想这个状态怎么转移也就是说怎么从00001不断的生成新的状态直到生成1111100001可以生成哪些状态？可以生成10001010010010100011并且只能生成这四种状态就是说从1出发下一步要么走到2要么走到3等等比如说11001=10001+x这个x代表从1号点走到4号点的距离或者5号点走到4号点的距离10001代表1和5都走过了也就是说现在要么在1要么在5下一步要走到4号点也就是说要么从1号点走到4要么从5号点走到4那么我们的状态方程就可以得到了假设已知dp(i)他可以得到dp(j)这个j是i的二进制数中的某一个为0的位变为1举个例子假设i=17假设已知dp[17]=35二进制就是10001他可以生成状态10011也就是19dp[19]=dp[17]+从x到4号点的距离的最小值这个x可以取什么呢就是1或者5dp[19]=dp[17]+min{1到4的距离,5到4的距离}同理10001也可以生成状态10101也就是21dp[21]=dp[17]+从x到3号点的距离的最小值///////////////////////////////////////////////////////////////////////////////////我觉得有问题，而且我也理解不了这种逻辑。你看看吧，有感想跟我说一说
解决方案：
首先觉得这个逻辑很简单，没必要用二进制包装。其次我认为这个逻辑是错的，问题在于，他假设你能从你去过的任意一点出发再到别的点。他说这个：dp[19]=dp[17]+min{1到4的距离,5到4的距离}，就是说当你起点在1，然后走到了5，这时候如果你想去4，你可以选择从1或者5出发，而这是不对的
解决方案：
引用25楼lcf的回复:
首先觉得这个逻辑很简单，没必要用二进制包装。其次我认为这个逻辑是错的，问题在于，他假设你能从你去过的任意一点出发再到别的点。他说这个：dp[19]=dp[17]+min{1到4的距离,5到4的距离}，就是说当你起点在1，然后走到了5，这时候如果你想去4，你可以选择从1或者5出发，而这是不对的
看来这个题就是np问题了。还是暴力解决吧
解决方案：
楼主在没在，
解决方案：
蚁群算法，无压力
解决方案：
至于蚁群算法的介绍和代码，网上很多的，多看几遍都能看懂。
解决方案：
引用楼主rt77777的回复:
打个比方，我要去北京，有好多景点，比如A,B,C,D,E,F，每个点都有坐标，1：假设从A开始，D结束，求出一个路线最短的方案。2：假设从A开始，结束点任意，求出一个路线最短的方案。
楼主提出的需求不全你少权重你缺少了每两点之间距离吧？有种笨方法（适合计算机处理能力强的）就是算出所有可能情况下的路径的距离取最小的嘿嘿
解决方案：
引用30楼u010444251的回复:
Quote: 引用楼主rt77777的回复:
打个比方，我要去北京，有好多景点，比如A,B,C,D,E,F，每个点都有坐标，1：假设从A开始，D结束，求出一个路线最短的方案。2：假设从A开始，结束点任意，求出一个路线最短的方案。楼主提出的需求不全你少权重你缺少了每两点之间距离吧？有种笨方法（适合计算机处理能力强的）就是算出所有可能情况下的路径的距离取最小的嘿嘿
穷举法·····