#java #algorithm #dynamic-programming #shortest-path
#java #алгоритм #динамическое программирование #кратчайший путь
Вопрос:
Пожалуйста, помогите мне реализовать следующий алгоритм. Я новичок, и эта проблема сбивает меня с толку.
Алгоритм должен найти кратчайший путь от верхнего левого угла до нижнего правого. Нижний правый элемент всегда равен 0. Массив всегда квадратный (например, 3×3).
Перемещаться по массиву можно только вниз или вправо. Текущая позиция и элемент int, так называемая сила перехода (например, если мы находимся в начале в точке [0] [0], а соответствующий элемент равен 2, тогда мы можем переместить 2 вниз (D2 ) -> [2] [0] или 2 вправильно (R2) -> [0] [2]). Если сила прыжка выбрасывает нас за пределы поля (например, массив 3х3 и мы наступили на ячейку 5, то в любом случае мы вылетаем с поля в обе стороны), нам нужно начинать сначала и искать другой путь.
Алгоритм должен вычислять путь / порядок, в котором нужно прыгать / ходить, чтобы достичь конца с наименьшим возможным количеством прыжков.
Я пробовал разные подходы, теперь я борюсь с DFS после составления неявного графика из input int[][], и ответ, который я получаю, не является кратчайшим путем. Я также слышал, что динамическое программирование может помочь, но не знаю, как это реализовать.
мой код с небольшим тестом включен:
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
}}
Ответ №1:
Или с подходом поиска в глубину.
public List<List<String>> findAllPaths(int[][] map, int D, int R) {
System.out.printf("findPath(map, %d, %d) called %n", D, R);
// Get the limits of the map
int mapSize_Y = map.length;
int mapSize_X = map[0].length;
// If given coordinates are not in the map
// Since the moves are restircted to down and right, no need to check lower border
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();
}
// Move forward and call the function recursively
// Spoken - get all subpaths that are possible from this point on
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);
// Add the move that produced the subpaths to the result
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 no further path is found return
if (MapUtils.isEmpty(subPaths)) {
System.out.printf("No valid Subpaths at Point (%d, %d) %n", D, R);
return null;
}
// Change key-value structure to a list with the key as first entry
// and the values of the map value afterwards
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 resu<
}
Кроме того, вы можете удалить все атрибуты вашего основного класса, если измените метод 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;
}
Ответ №2:
С помощью этого кода (A *-Search) вы не получите оптимального решения, но почти.
//= 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
}
}