. 불행히도 저는 몇 년 동안 Java에서 일하지 않았습니다. 따라서이 대답은 의사 Java이며 일부 구문을 수정해야합니다. 아마도 함수 매개 변수 중 일부는 참조가되어야하며 복사본이 아니어야합니다. 당신은 그것을 알아낼 것이다 (업데이트 : 나는 파이썬에서 테스트 된 버전을 아래에 추가했다).
// 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) ;
}
}
}
다음은 파이썬에서 동일한 알고리즘을 테스트 한 버전입니다. (나는 x, y을 좌표로 사용하는 것이 오도 된 것임을 알았습니다. x은 실제로 "수직"이고 y은 "수평 적"인 배열로 배열되어 있습니다. 나는 4 개의 출구와 한 쌍의 행렬을 설정했습니다 막 다른 골목으로.)
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)
당신이 findPath()의 첫 showPath() 전화 주석을 제거하면 모든 단계를 확인하고 막 다른 골목 포기받을 위치를 확인할 수 있습니다. 당신은 모든 가능성에 나무를 구축하고 짧은 다음 걸릴 수 있습니다 여기에
(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