二维数组最短路径的java算法

hzbexzde  于 2021-07-07  发布在  Java
关注(0)|答案(2)|浏览(581)

请帮我实现下面的算法。我是个初学者，这个问题把我难倒了。
算法应该找到从左上角到右下角的最短路径。右下角的元素总是0。数组总是正方形的（如3x3）。
只能沿阵列向下或向右移动。当前位置和int元素，即所谓的跳跃力（例如，如果我们在点[0][0]的起点，对应的元素是2，那么我们可以向下移动2（d2）->[2][0]或向右移动2（r2）->[0][2]）。如果跳跃的力量把我们抛出场外（例如，一个3x3阵列，我们踩到了第5单元，那么在任何情况下，我们都会从两个方向飞离场），我们需要重新开始，寻找另一种方法。
一个算法应该计算出一个人必须跳跃/行走的路径/顺序，以便以最少的跳跃次数到达终点。
该算法如何工作的示例（因此，路径将是[d1，r2，d1]——向下移动一次，向右移动两次，向下移动一次）
我尝试过不同的方法，现在我在用输入int[][]构造一个隐式图之后正在与dfs作斗争，我得到的答案不是最短路径。我还听说动态规划可能会有帮助，但不知道如何实现这一点。
我的代码几乎没有测试，包括：

public class Main {

int indexError = 0;
int shortestPathLen = Integer.MAX_VALUE;
List<String> shortestPath = new ArrayList<>();
List<List<String>> allPaths;
List<String> solution = new ArrayList<>();

public List<List<String>> findAllPaths(int[][] map, int D, int R) {
int currentPosition = map[D][R]; //D - down, R - right
 if (currentPosition == 0) {
allPaths.add(solution);
return allPaths;
}
if (D + currentPosition <= indexError) {
solution.add("D" + currentPosition);
findAllPaths(map, D+currentPosition, R);
}
if (R + currentPosition <= indexError) {
solution.add("R" + currentPosition);
findAllPaths(map, D, R+currentPosition);
}
solution = new ArrayList<>();
return allPaths;
}  

public List<String> findPath(int[][] map) {
indexError = map[0].length - 1;
shortestPathLen = Integer.MAX_VALUE;
allPaths = new ArrayList<>();

List<List<String>> l = findAllPaths(map, 0, 0);
for (List<String> path : l) {
if (path.size() < shortestPathLen) {
    shortestPathLen = path.size();
    shortestPath = path;
}
}
return shortestPath;
}

public static void main(String[] args) {
Main main = new Main();
// int len = 3;
// int[] array =   {1, 2, 2,
//                 2, 10, 1,
//                 3, 2, 0}; // from example
int len = 9;
int[] array =
            {1, 10, 20, 1, 2, 2, 1, 2, 2,
            1, 10, 1, 10, 2, 2, 1, 2, 2,
            1, 10, 1, 1, 20, 2, 1, 2, 2,
            2, 1, 10, 1, 1, 20, 1, 2, 2,
            1, 2, 2, 10, 1, 1, 10, 2, 2,
            2, 1, 1, 1, 10, 1, 1, 20, 2,
            1, 2, 2, 1, 2, 10, 1, 1, 20,
            1, 1, 1, 1, 2, 2, 10, 1, 1,
            1, 2, 1, 1, 2, 2, 1, 1, 0};
int[][] map = new int[len][len];
int k = 0;
for (int i = 0; i < len; i++) {
   for (int j = 0; j < len; j++) {
    map[i][j] = array[k];
    k++;
  }
}
List result = main.findPath(map);
System.out.println("\n" + result + ", " + result.size() + " jumps");
// = must be [D1, D1, D1, D2, R2, D1, R2, D2, R2, R1, R1], 11 jumps
}}
JavaAlgorithmdynamic-programmingshortest-path

2条答案

按热度按时间
woobm2wo

woobm2wo1#

使用此代码（a*-搜索），您将无法获得最佳解决方案，但几乎可以。

//= D1, D1, D1, D2, D2, D1, R1, R2, R1, R2, R1, R1, 12 jumps

如果您可以更改distancetogoal（）-方法以更好地估计到目标的真实距离，您将得到最佳解决方案。

public class TestClass {
    private static class Position implements Comparable<Position>{
        private final int[][] map;
        private int x;
        private int y;
        List<String> path = new ArrayList<>();

        /**
         * Some Constructors
        */
        public Position(int[][] map) {
           this(map, 0, 0);
        }

        public Position(Position parent, Consumer<Position> consumer, String action) {
            this(parent.map, parent.x, parent.y);
            consumer.accept(this);

            this.path.addAll(parent.path);
            this.path.add(action);
        }

        private Position(int[][] map, int x, int y) {
            this.map = map;
            this.x = x;
            this.y = y;
        }

        /**
         * Returns Jumpforce of current position
         */
        public int getJumpForce() {
            return this.map[this.y][this.x];
        }

        /**
         * Returns steps taken till current position
         */
        public int steps() {
            return CollectionUtils.size(this.path);
        }

        /**
         * Method calculates the estimated way to the goal. In this case the mannhatten distance
         */
        private int distanceToGoal() {
            var height = ArrayUtils.getLength(this.map);
            var width = ArrayUtils.getLength(this.map);
            return (height - (y+1)) + (width - (x+1));
        }

        /**
         * Sum of steps taken and the estimated distance till the goal
         */
        private int totalCosts() {
           return this.steps() + this.distanceToGoal();
        }

        public boolean isGoal() {
            return this.map[this.y][this.x] == 0;
        }

        /**
         * Returns a list of all successor states
         */
        public List<Position> successors() {
            var s = new ArrayList<Position>();
            if (ArrayUtils.getLength(this.map) > (this.y + this.getJumpForce())) {
                s.add(new Position(this,
                        p -> p.y += this.getJumpForce(),
                        String.format("D%d", this.getJumpForce())));
            }
            if (ArrayUtils.getLength(map[y]) > (x + this.getJumpForce())) {
                s.add(new Position(this,
                        p -> p.x += this.getJumpForce(),
                        String.format("R%d", this.getJumpForce())));
            }
            return s;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;

            if (o == null || getClass() != o.getClass()) return false;

            Position position = (Position) o;

            return new EqualsBuilder()
                    .append(x, position.x)
                    .append(y, position.y)
                    .isEquals();
        }

        @Override
        public int hashCode() {
            return new HashCodeBuilder(17, 37)
                    .append(x)
                    .append(y)
                    .toHashCode();
        }

        @Override
        public int compareTo(Position o) {
            return Comparator.comparing(Position::totalCosts).compare(this, o);
        }

        @Override
        public String toString() {
            return String.join(", ", path);
        }
    }

    public static Position findShortestPath(int[][] map) {
        var visited = new HashSet<Position>();
        var fringe = new PriorityQueue<Position>(){{
            add(new Position(map));
        }};

        // As long as there is a position to check
        while (CollectionUtils.isNotEmpty(fringe)) {
            // Get that position
            var position = fringe.poll();
            //If we didn't look already at this position
            if (!visited.contains(position)) {
                // Check if its the goal
                if (position.isGoal()) {
                    return position;
                } else {
                    //Mark position as visited
                    visited.add(position);
                    //Add all successors to be checked
                    fringe.addAll(position.successors());
                }
            }
        }

        // If no solution is found
        return null;
    }

    public static void main(String[] args) {
        // int len = 3;
        // int[] array =   {1, 2, 2,
        //                 2, 10, 1,
        //                 3, 2, 0}; // from example
        int[][] map = { {1, 10, 20, 1, 2, 2, 1, 2, 2},
                        {1, 10, 1, 10, 2, 2, 1, 2, 2},
                        {1, 10, 1, 1, 20, 2, 1, 2, 2},
                        {2, 1, 10, 1, 1, 20, 1, 2, 2},
                        {1, 2, 2, 10, 1, 1, 10, 2, 2},
                        {2, 1, 1, 1, 10, 1, 1, 20, 2},
                        {1, 2, 2, 1, 2, 10, 1, 1, 20},
                        {1, 1, 1, 1, 2, 2, 10, 1, 1},
                        {1, 2, 1, 1, 2, 2, 1, 1, 0} };

        Position position = findShortestPath(map);
        if (Objects.nonNull(position)) {
            System.out.printf("%s, %d jumps%n", position, position.steps());
        } else {
            System.out.println("No solution found");
        }
        // = must be [D1, D1, D1, D2, R2, D1, R2, D2, R2, R1, R1], 11 jumps
    }

}

赞(0）分享  回复(0）举报  2021-07-07
kg7wmglp

kg7wmglp2#

或者用深度优先的搜索方法。

public List<List<String>> findAllPaths(int[][] map, int D, int R) {
    System.out.printf("findPath(map, %d, %d) called %n", D, R);
    int mapSize_Y = map.length;
    int mapSize_X = map[0].length;

    if (R >= mapSize_X || D >= mapSize_Y) {
        System.out.printf("Point at (%d, %d) not in the map%n", D, R);
        return null;
    }

    int jumpStrength = map[D][R]; //D - down, R - right

    if (jumpStrength == 0) {
        System.out.printf("Found goal at (%d, %d)%n", D, R);
        return Collections.emptyList();
    }

    var subPathsDown = findAllPaths(map, D + jumpStrength, R);
    System.out.printf("subpaths after findPath(map, %d, %d) returned -> %s%n", D + jumpStrength, R, subPathsDown);
    var subPathsRight = findAllPaths(map, D, R + jumpStrength);
    System.out.printf("subpaths after findPath(map, %d, %d) returned -> %s%n", D, R + jumpStrength, subPathsRight);

    var subPaths = new HashMap<String, List<List<String>>>() {{
        if (Objects.nonNull(subPathsDown)) {
            put("D" + jumpStrength, subPathsDown);
        }
        if (Objects.nonNull(subPathsRight)) {
            put("R" + jumpStrength, subPathsRight);
        }
    }};

    if (MapUtils.isEmpty(subPaths)) {
        System.out.printf("No valid Subpaths at Point (%d, %d) %n", D, R);
        return null;
    }

    List<List<String>> result = subPaths.entrySet()
            .stream()
            .flatMap(e -> {
                if (CollectionUtils.isEmpty(e.getValue())) {
                    return Stream.of(new ArrayList<String>() {{
                        add(e.getKey());
                    }});
                }

                return e.getValue()
                        .stream()
                        .map(sp -> new ArrayList<String>() {{
                            add(e.getKey());
                            addAll(sp);
                        }});
            })
            .collect(Collectors.toList());

    return result;
}

此外，如果将findpath方法更改为：

public List<String> findPath(int[][] map) {
    int shortestPathLen = Integer.MAX_VALUE;
    List<String> shortestPath = new ArrayList<>();

    List<List<String>> l = findAllPaths(map, 0, 0);
    for (List<String> path : l) {
        if (path.size() < shortestPathLen) {
            shortestPathLen = path.size();
            shortestPath = path;
        }
    }
    return shortestPath;
}
赞(0）分享  回复(0）举报  2021-07-07
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com