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