Мне очень нравится эта проблема. К сожалению, я не работал на Java много лет, поэтому этот ответ является псевдо-Java, и вам нужно будет исправить некоторый синтаксис. Вероятно, некоторые из параметров функции должны быть ссылками, а не копиями; вы это выясните (обновление: я добавил версию TESTED на питоне ниже).
// just a little thing to hold a set of coordinates
class Position
{
// not bothering with private/getters
public int x ;
public int y ;
public constructor (int x, int y)
{
this.x = x ;
this.y = y ;
}
}
class PathFinder
{
public void main (void)
{
// create a path with just the start position
start = new Position(0, 0) ;
path = new Vector() ;
path.add(start) ;
// create an empty path to contain the final shortest path
finalPath = new Vector() ;
findPath(path, finalPath) ;
print ("Shortest Path: ") ;
showPath (finalPath) ;
}
private void showPath (Vector path) {
// print out each position in the path
iter = path.iterator() ;
while (pos = iter.next()) {
print ("(%, %) ", pos.x, pos.y);
}
// print out the length of the path
print (" Length: %\n", path.size()) ;
}
// recursive function to find shortest path
private void findPath (Vector path, Vector finalPath)
{
// always display the current path (it should never be the same path twice)
showPath(path) ;
// where are we now?
here = path.lastElement() ;
// does the current path find the exit (position 4,5)?
if (here.x == 4 && here.y == 5) {
if (finalPath.size() == 0) {
//finalPath is empty, put the current path in finalPath
finalPath = path ;
} else {
// some other path found the exit already. Which path is shorter?
if (finalPath.size() > path.size()) {
finalPath = path ;
}
}
// either way, we're at the exit and this path goes no further
return ;
}
// path is not at exit; grope in all directions
// note the code duplication in this section is unavoidable
// because it may be necessary to start new paths in three
// directions from any given position
// If no new paths are available from the current position,
// no new calls to findPath() will happen and
// the recursion will collapse.
if (here.x > 0 && matrix[here.x-1][here.y] > matrix[here.x][here.y]) {
// we can move left
newPos = new Position(here.x-1, here.y) ;
newPath = path ;
newPath.add (newPos) ;
findPath(newPath, finalPath) ;
}
if (here.x < 4 && matrix[here.x+1][here.y] > matrix[here.x][here.y]) {
// we can move right
newPos = new Position(here.x+1, here.y) ;
newPath = path ;
newPath.add (newPos) ;
findPath(newPath, finalPath) ;
}
if (here.y > 0 && matrix[here.x][here.y-1] > matrix[here.x][here.y]) {
// we can move up
newPos = new Position(here.x, here.y-1) ;
newPath = path ;
newPath.add (newPos) ;
findPath(newPath, finalPath) ;
}
if (here.y < 5 && matrix[here.x][here.y+1] > matrix[here.x][here.y]) {
// we can move down
newPos = new Position(here.x, here.y+1) ;
newPath = path ;
newPath.add (newPos) ;
findPath(newPath, finalPath) ;
}
}
}
Вот проверенная версия того же алгоритма в python. (Я заметил, что использование x, y в качестве координат является своего рода вводящим в заблуждение x на самом деле является «вертикальным», а y «горизонтально» с массивом, индексированным так, как есть. Я установил матрицу с четырьмя путями к выходу и пару тупиков.)
import copy, sys
matrix = [
[5, 13, 17, 58, 2],
[17, 24, 32, 3, 24],
[23, 7, 33, 1, 7],
[45, 40, 37, 38, 70],
[47, 34, 12, 25, 2],
[52, 56, 68, 76, 100]]
def showPath(path):
for position in path:
sys.stdout.write("(" + str(position[0]) + ", " + str(position[1]) + "), ")
sys.stdout.write("\n\n")
sys.stdout.flush()
def findPath(path):
#showPath(path)
global finalPath
x = path[-1][0]
y = path[-1][1]
if x == 5 and y == 4:
showPath(path)
if len(finalPath) == 0 or len(finalPath) > len (path):
finalPath[:] = copy.deepcopy(path)
return
if x > 0 and matrix[x-1][y] > matrix[x][y]:
# we can move up
newPath = copy.deepcopy(path)
newPath.append([x-1, y])
findPath(newPath)
if x < 5 and matrix[x+1][y] > matrix[x][y]:
# we can move down
newPath = copy.deepcopy(path)
newPath.append([x+1, y])
findPath(newPath)
if y > 0 and matrix[x][y-1] > matrix[x][y]:
# we can move left
newPath = copy.deepcopy(path)
newPath.append([x, y-1])
findPath(newPath)
if y < 4 and matrix[x][y+1] > matrix[x][y]:
# we can move right
newPath = copy.deepcopy(path)
newPath.append([x, y+1])
findPath(newPath)
path = []
path.append([0, 0])
finalPath = []
findPath(path)
print "Shortest Path: " + str(len(finalPath)) + " steps.\n"
showPath(finalPath)
Если раскомментировать первый showPath() вызов findPath() вы можете увидеть на каждом шагу и увидеть, где мертвые концы получают заброшены. Если вы только показать пути, которые достигают выход, выход выглядит следующим образом:
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
Shortest Path: 10 steps.
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
вы можете идти влево и вверх или просто вниз и вправо. Что такое основной случай для вашей рекурсии, когда вы останавливаетесь? Я вижу две ситуации, когда вы «снизу» Каковы рекурсивные случаи? –
Если вы идете только направо и вниз, все возможные решения будут иметь одинаковую длину (10). Только если вы когда-либо поднимаетесь или уходите, пройденное число будет больше 10. – FredK
Да, вы можете идти вверх, вниз, вправо и влево. Мне нужно остановиться, когда я доберусь до конца матрицы или когда дойду до нижнего правого. Что вы имеете в виду рекурсивные случаи? – Uranus