r*****e 发帖数: 4611 | 1 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。
问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999
定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的
,就是说不经过21到32的点的)
连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那
么abc就形成一个通路
现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也
就是说不存在断线
现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到
第10个线段即可)
谢谢
对了,补充一点,通路是不逆向走的,就是不会3到6,6到9,9又回到4什么的。只能向
数字更大的点走 |
S**I 发帖数: 15689 | 2 BFS
【在 r*****e 的大作中提到】 : 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。 : 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999 : 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的 : ,就是说不经过21到32的点的) : 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那 : 么abc就形成一个通路 : 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也 : 就是说不存在断线 : 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到 : 第10个线段即可)
|
l*****9 发帖数: 9501 | |
n*****t 发帖数: 22014 | 4 线段是已知的还是要计算?如果要计算怎么计算?线段 ab,a 是不是永远不大于 b?
这属于图的计算,是 CS 的基本功之一 ,数学问不着吧 。。。
【在 r*****e 的大作中提到】 : 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。 : 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999 : 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的 : ,就是说不经过21到32的点的) : 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那 : 么abc就形成一个通路 : 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也 : 就是说不存在断线 : 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到 : 第10个线段即可)
|
r*****e 发帖数: 4611 | 5 线段是已知的,线段包含的信息就是start和end,start永远小于end
这个程序输入就是一个线段的数组
输出的话应该是一个线段的数组的数组
【在 n*****t 的大作中提到】 : 线段是已知的还是要计算?如果要计算怎么计算?线段 ab,a 是不是永远不大于 b? : 这属于图的计算,是 CS 的基本功之一 ,数学问不着吧 。。。
|
b*******s 发帖数: 5216 | 6 最简单的就是bfs
【在 r*****e 的大作中提到】 : 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。 : 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999 : 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的 : ,就是说不经过21到32的点的) : 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那 : 么abc就形成一个通路 : 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也 : 就是说不存在断线 : 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到 : 第10个线段即可)
|
n*****t 发帖数: 22014 | 7 多叉树的遍历,俺不会 java,你看看这个有没有用
http://blog.csdn.net/shanzhizi/article/details/13022749
【在 r*****e 的大作中提到】 : 线段是已知的,线段包含的信息就是start和end,start永远小于end : 这个程序输入就是一个线段的数组 : 输出的话应该是一个线段的数组的数组
|
r*****e 发帖数: 4611 | 8 有一点点区别,因为多叉树好像每个节点只有一个parent节点。我的情况是允许多个
parent节点的。
说错了莫怪
iteration的话记录数组有点麻烦,我最后自己想出了个办法。
就是建立个通路的数组。先记录0点出发所有线段,每段建一个通路存入数组。
然后就用一个while循环不断遍历这个数组,根据数组最后一个节点的连接段情况增长
和添加新通路,如果某通路有10段或者连到999了就标记为完成。这样直到数组中所有
的通路都是完成了的才停止循环。这样最后就是所有通路的列表了。
【在 n*****t 的大作中提到】 : 多叉树的遍历,俺不会 java,你看看这个有没有用 : http://blog.csdn.net/shanzhizi/article/details/13022749
|
n*****t 发帖数: 22014 | 9 你这个树不关心父节点,而且不会形成回路死循环,每个父节点用数组记录子节点就行
了,遍历子节点算法上递归很简单。
你的算法我没太明白 。。。会不会漏掉?
【在 r*****e 的大作中提到】 : 有一点点区别,因为多叉树好像每个节点只有一个parent节点。我的情况是允许多个 : parent节点的。 : 说错了莫怪 : iteration的话记录数组有点麻烦,我最后自己想出了个办法。 : 就是建立个通路的数组。先记录0点出发所有线段,每段建一个通路存入数组。 : 然后就用一个while循环不断遍历这个数组,根据数组最后一个节点的连接段情况增长 : 和添加新通路,如果某通路有10段或者连到999了就标记为完成。这样直到数组中所有 : 的通路都是完成了的才停止循环。这样最后就是所有通路的列表了。
|
r*****e 发帖数: 4611 | 10 我想过一下,遍历一遍也许不难,但是我想不明白怎样能把通路经过全部分别保存下来。
我说的那种办法我觉得应该不会漏吧。说白了就是遇到岔路就把岔路保存下来。
【在 n*****t 的大作中提到】 : 你这个树不关心父节点,而且不会形成回路死循环,每个父节点用数组记录子节点就行 : 了,遍历子节点算法上递归很简单。 : 你的算法我没太明白 。。。会不会漏掉?
|
|
|
n*****t 发帖数: 22014 | 11 最脑残的办法,所有路径用 4 位数字打印每个节点编号,然后把长度超过 40 的行都
删了,哈哈
来。
【在 r*****e 的大作中提到】 : 我想过一下,遍历一遍也许不难,但是我想不明白怎样能把通路经过全部分别保存下来。 : 我说的那种办法我觉得应该不会漏吧。说白了就是遇到岔路就把岔路保存下来。
|
m**********e 发帖数: 12525 | 12 这个模型数学上叫random walk:
http://en.wikipedia.org/wiki/Random_walk
可以假设0,1,...10000是一个往下的台阶的编号,0台阶最高,势能最大,10000最低,
势能最低,一个球从0往下滚,可以滚0-1-3-7-....,也可以滚0-3-9-100-....,但是由
于能量守恒的原因,球不可能往上滚,这样的模型便符合你的要求
所以要穷尽10步就变得很简单的事情了,0取定后,产生随机数,根据运到方程随机选取
势能小的下一个台阶,滚下去.滚完后记录结果.然后再次循环
这个程序很简单,不要担心会产生遗漏,因为根据各态历经性,数学上遗漏可能是0.
【在 r*****e 的大作中提到】 : 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。 : 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999 : 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的 : ,就是说不经过21到32的点的) : 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那 : 么abc就形成一个通路 : 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也 : 就是说不存在断线 : 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到 : 第10个线段即可)
|
k********e 发帖数: 702 | 13 这个题很简单。矩阵运算就可以出来。图论基本知识。矩阵好处是可以无限scale。任
你数亿个路线,我map redunce在数万个机器上跑 一圈,就解决了。
解题要注意多用当前流行的术语唬人。不要抱着几十年前的技术不放。虽然好,但是不
唬人也没用。 |
m*******t 发帖数: 1060 | 14 A simple solution as shown below.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PathFinder {
private static void printPath(List path) {
for (int i = 0; i < path.size(); i++) {
System.out.format("%2d", path.get(i));
if (i != path.size() - 1)
System.out.print("->");
else
System.out.println();
}
}
private boolean shouldSkip(List curPath, Integer pos) {
if (curPath == null)
return false;
for (Integer i : curPath) {
if (pos <= i) {
return true;
}
}
return false;
}
public void findPaths(Map> graph, int curPos,
List curPath, int expectedPathLen) {
curPath.add(curPos);
if (curPath.size() == expectedPathLen) {
printPath(curPath);
} else {
List children = graph.get(curPos);
if (children != null) {
for (Integer i : children) {
if (this.shouldSkip(curPath, i))
continue;
findPaths(graph, i, curPath, expectedPathLen);
}
}
}
curPath.remove(curPath.size() - 1);
}
public static void main(String[] args) {
Map> graph = new HashMap
Integer>>();
// construct a graph
// 0 -> 1 -> 2 -> 3 ->4 ->5 ->6 ->7 ->8 -> 9 ->10 ->11
// 0 -> 2
// 1 -> 5
// 4 -> 6
// 7 -> 6 (a backward path)
for (int i = 0; i <= 10; i++) {
graph.put(i, new ArrayList());
graph.get(i).add(i + 1);
}
graph.get(0).add(2);
graph.get(1).add(5);
graph.get(4).add(6);
graph.get(7).add(6);
// a variable used to record current path
List curPath = new ArrayList();
new PathFinder().findPaths(graph, 0, curPath, 10);
// output
// 0-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9
// 0-> 1-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10->11
}
} |
b***i 发帖数: 3043 | 15 维持一个广度优先的对列,保持头,尾,和当前层次.
从头开始到尾,把队列中每个点的下一个点输入新的尾,这样增加下一个层次的所有点.
重复即可.第一次只有一个点.
【在 r*****e 的大作中提到】 : 俺不是程序员,不过因为一些需要自己得写这个程序。现在遇到点困难,求帮忙。 : 问题是这样的,我有一系列的点。假设1000个吧。就称为点0,点1,。。。,点999 : 定义线段,连接某两个点,比如说某线段连接点20和点33.(线段是不碰中间那些点的 : ,就是说不经过21到32的点的) : 连续的线段就形成通路,比如说线段a连接3到6,线段b连接6到9,线段c连接9到15,那 : 么abc就形成一个通路 : 现在我有一些线段,已经能够保证现存的每一个线段的前后都是存在连续的线段的,也 : 就是说不存在断线 : 现在我需要做的是列出所有从0点出发的10个线段以内的可能路径(就是说只需要列到 : 第10个线段即可)
|