发现蛇顺序XY图 - Java的 [英] Finding snake sequence in XY graph - Java
问题描述
我的工作有问题，试图找到所谓的蛇序列中的一个典型的XY图（又名格）。蛇序列被定义为一系列数字，其中每一个新号码，它只能位于右侧或当前数量的下降，或者是加或减一。例如，如果你在图的中心，您可以向右移动（如果该号码是+或 - 1）或向下移动（如果该号码是+或 - 1）。问题的目标是找到通过图中的最长路径（又名蛇序列）（记住只能开辟一条道路，以一个新的小区，其值为+ - 1与当前小区）。
于是，以下XY图，最长的蛇顺序是： 9，8，7，6，5，6，7
9，6，5，2
8，7，6,5
7，3,1，6
1，1，1，7
下面是我的code，这似乎并没有工作。
问：你将如何解决上述这个问题？ （我提供我的code显示什么我迄今，但它不工作）
进口的java.util.ArrayList;
公共类SnakeSequence {
私人最终诠释MAXX = 3;
私人最终诠释MAXY = 3;
私人最终诠释[] []板=新INT [] [] {
{1，2，3，4}，
{2，1，-1，5}，
{3,0，-1，6}，
{6,2，1,7}
};
私人的ArrayList＆LT;整数GT; findSequence（INT XPOS，
INT yPos，ArrayList的＆LT;整数GT; currentPath）{
currentPath.add（板[yPos] [XPOS]）;
ArrayList的＆LT;整数GT; pathRight =新的ArrayList＆LT;整数GT;（currentPath）;
ArrayList的＆LT;整数GT; pathDown =新的ArrayList＆LT;整数GT;（currentPath）;
如果（XPOS＆LT; MAXX || yPos＆LT; MAXY）{
如果（yPos＆其中; MAXY＆安培;及（板[yPos + 1] [XPOS〕+ 1 ==板[yPos] [XPOS] ||
板[yPos + 1] [XPOS] - 1 ==板[yPos] [XPOS]））{
pathDown = findSequence（XPOS，yPos + 1，currentPath）;
}
如果（XPOS＆其中; MAXX＆安培;及（板[yPos] [XPOS + 1] + 1 ==板[yPos] [XPOS] ||
板[yPos] [XPOS + 1] - 1 ==板[yPos] [XPOS]））{
pathRight = findSequence（XPOS + 1，yPos，currentPath）;
}
如果（pathDown.size（）＆GT; pathRight.size（））{
返回pathDown;
} 其他 {
返回pathRight;
}
}
返回currentPath;
}
私人无效某个getSequence（）{
ArrayList的＆LT;整数GT; currentPath =新的ArrayList＆LT;整数GT;（）;
ArrayList的＆LT;整数GT;结果;
结果= findSequence（0，0，currentPath）;
的for（int i = 0; I＆LT; result.size（）;我++）{
的System.out.println（result.get（一））;
}
}
公共静态无效的主要（字串[] args）{
SnakeSequence序列=新SnakeSequence（）;
sequence.getSequence（）;
}
}
您能想象你的表作为的向图，那么你的问题就是找到最长路径。
Fortunatly对你的，只有向下移动，右是允许的，所以你的图是非周期性，这样你就可以像使用关键路径法算法。
这是你的图怎么会是这样的：
不过，你想找到的任意的两个小区之间的最长路径。为了做到这一点，我会计算每个单元格开始在该小区的最长路径。这是simmilar为你做什么，但你计算同一件事倍。试想一下：
6 - ＆GT;五
| |
v v
7 - ＆GT; 6
在这两个 5 和 7 你计算多久是从路径6 的降权，这是无用的重复计算。在最坏的情况下，这可能会导致指数时间消耗，同时该问题可以在线性时间内解决！
此外，也不能保证最长路径将开始在（0,0）。
（一种可能）的解决方法：
计算每个单元最长的路径，从右下角开始左上角。在每个CEL ..记得多久，从电池的最长路径是，从该小区内的道路通向巫婆的方法。 （我将测量细胞就可以了数路径长度）。因此，例如，对于仅 8 在grapth，我们的记住 [长度= 8，方向=右]
为什么这么复杂？的因为现在extramly容易计算最长的路径在一个单元格，如果我们知道了细胞向右和向下的最长路径。示例（我做了）：
其正确性的 2 现在是 [长度= 4，方向=向下] ，因为不能从 2 到 4 。
您还可以保持全球最长的路径，它的开始。计算完成后，只是走的最长路径从开始通过方向，写的号码，位置，或任何你需要的。
I am working on a problem to try to find what is called a Snake Sequence in a typical XY graph (aka grid). A Snake sequence is defined as a sequence of numbers where each new number, which can only be located to the right or down of the current number, is either plus or minus one. For example, if you are in the center of the graph, you can either move right (if that number is + or - 1) or move down (if that number is + or - 1). The goal of the problem is to find the longest path (aka Snake Sequence) through the graph (keeping in mind you can only chart a path to a new cell whose value is +- 1 with the current cell).
So, for the following XY graph, the longest snake sequence is: 9, 8, 7, 6, 5, 6, 7
9, 6, 5, 2
8, 7, 6, 5
7, 3, 1, 6
1, 1, 1, 7
Below is my code, which does not seem to work.
Question: How would you solve this problem above? (I offer my code showing what I have thus far, but it does not work)
import java.util.ArrayList;
public class SnakeSequence {
private final int maxX = 3;
private final int maxY = 3;
private final int[][] board = new int[][]{
{1, 2, 3, 4},
{2, 1, -1, 5},
{3, 0, -1, 6},
{6, 2, 1, 7}
};
private ArrayList<Integer> findSequence(int xPos,
int yPos, ArrayList<Integer> currentPath) {
currentPath.add(board[yPos][xPos]);
ArrayList<Integer> pathRight = new ArrayList<Integer>(currentPath);
ArrayList<Integer> pathDown = new ArrayList<Integer>(currentPath);
if (xPos < maxX || yPos < maxY) {
if (yPos < maxY && (board[yPos + 1][xPos] + 1 == board[yPos][xPos] ||
board[yPos + 1][xPos] - 1 == board[yPos][xPos])) {
pathDown = findSequence(xPos, yPos + 1, currentPath);
}
if (xPos < maxX && (board[yPos][xPos + 1] + 1 == board[yPos][xPos] ||
board[yPos][xPos + 1] - 1 == board[yPos][xPos])) {
pathRight = findSequence(xPos + 1, yPos, currentPath);
}
if (pathDown.size() > pathRight.size()) {
return pathDown;
} else {
return pathRight;
}
}
return currentPath;
}
private void getSequence() {
ArrayList<Integer> currentPath = new ArrayList<Integer>();
ArrayList<Integer> result;
result = findSequence(0, 0, currentPath);
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
public static void main(String[] args) {
SnakeSequence sequence = new SnakeSequence();
sequence.getSequence();
}
}
You can imagine your table as an oriented graph, then you problem is just to find the longest path.
Fortunatly for you, only moving down and right is allowed, so your graph is acyclic, so you can use algorithms like critical path method.
This is how your graph would look like:
However, you want to find longest path between any two cells. To do that, I would compute for each cell the longest path starting at that cell. It is simmilar to what you do, but you compute same thing more times. Consider this:
6 -> 5
| |
v v
7 -> 6
At both 5 and 7 you compute how long is the path from 6 at down right, and that is useless repeated computation. In worst case scenario, this could lead to exponential time consumption, while the problem can be resolved in linear time!
Moreover, there is no guarantee that the longest path will start at (0,0).
(one possible) Solution:
Compute longest path from each cell, starting from bottom-right to upper-left. At each cel.. remember how long the longest path from that cell is, and witch way from that cell the path leads. (I will measure path length by number of cells on it). So for example, for the only 8 in your grapth, we would remeber [length=8, direction=right].
Why so complicated? Because it is now extramly easy to compute longest path at a cell, if we know the longest path of the cells to the right and down. Example (I made up):
The correct data for 2 now would be [length=4, direction=down] because can't go from 2 to 4.
You can also keep globally longest path and it's start. After the computation is complete, just walk the longest path from that start through the direction and write the numbers, position or whatever you need.
这篇关于发现蛇顺序XY图 - Java的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
