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个线段即可）
|
