[완료] 스택을 이용한 길찾기에서 효과적인 루프 회피?

linuxgeek의 이미지

예를들어 10x10 미로가 있습니다. 흔히 십자말 풀이판처럼 생긴 맵이라고 할게요.

대충 이렇게 생겼겠죠?

아래 그림의 [ ]는 통과 가능한 길, [x]는 벽, [.]는 루핑이 예상되는 구역입니다.

[S][x][x][x][x][ ][ ][x][ ][ ]
[ ][ ][ ][x][.][.][.][x][ ][x]
[ ][x][ ][x][.][x][.][x][ ][x]
[ ][x][ ][ ][.][.][.][ ][ ][ ]
[ ][ ][ ][x][x][x][x][x][x][ ]
[ ][x][x][x][ ][ ][ ][ ][x][ ]
[ ][ ][ ][x][ ][x][x][ ][ ][ ]
[ ][x][x][x][ ][x][x][x][x][ ]
[ ][x][ ][ ][ ][x][ ][x][ ][x]
[ ][x][ ][x][ ][ ][ ][ ][ ][G]

이 미로의 S에서 G까지 길이 존재하는지를 찾는 프로그램을 스택을 이용해서 구현하려고 합니다.
Stack에 현재 위치의 상,하,좌,우로 길이 있는지 보고 길이 열려 있는 방향(또는 좌표)를 스택에 넣어 둡니다.
이 중에서 방금 지나온 블록은 스택에 넣지 않아야 하겠죠?

코드를 공개할 수 없어 아래에 해당 함수의 프로토타입을 만들어 보았습니다.

bool isThereAnyPath(현재좌표, 목적지좌표) {
    if (현재좌표 == 목적지 좌표) {
        return true;
    } 
 
    for (int i = 0 ; i < 네방향 ; i++) {
         if (i방향으로 길이 있고 내가 지나온 방향이 아니다) {
             스택에 담는다.
         }
    }
 
    for (int i = 0 ; i < 스택의 사이즈 ; i++) {
         if (isThereAnyPath(스택에서 꺼낸 이웃 노드의 좌표, 목적지 좌표) == true) {
               return true;
         }
    }
 
    return false;
}

문제는 위 그림의 [.]부분에 해당하는 구역에서 계속 무한루프를 돈다는 겁니다.
루프를 방지하기 위한 방법으로 두 가지를 이용해 보았습니다.

하나는 TTL이고

다른 하나는 지나온 PATH를 Argument로 넘겨 주어 지금의 좌표가 지나온 좌표인지 아닌지를 계속해서 비교해 보는 겁니다.
네트워크 프로토콜인 BGP의 ASPath를 이용한 루핑방지 방법과 유사하게 말입니다.

이러한 길찾기 연산이 짧은 시간에 수십번씩 진행될 수도 있으며 미로의 크기도 10x10보다 클 수도 있습니다.

위 두 방법의 문제는
TTL의 경우 TTL값을 적게 줄 경우 신빙성이 없고 높게 줄 경우 Loop지역이 겹친 있는 곳에서 엄청난 병목현상을 만들어 낸다는 겁니다.
PATH를 누적해서 넘겨 주는 경우에는 정확도는 믿을 수 있는데, 누적되어 전달되는 데이터의 크기를 가늠할 수 없고 또한 병목현상 또한 꾸준히 심하다는 겁니다.

몇일을 고민을 하다가 이렇게 문의를 드립니다. 혹시 위와 같은 재귀함수와 스택을 이용한 길찾기에서 루프를 회피할 수 있는 좋은 알고리즘을 알고 계시나요?

winner의 이미지

BGP보고 어느쪽 용어인지 알았습니다.
아마 자료구조 책 보는게 가장 편할 거 같아요.
쉽게 설명드리자면 전역변수를 쓰세요.
BGP가 network에서 쓰이는 것은 network에서 전역변수를 쓰기가 어려워서예요.

linuxgeek의 이미지

답변 감사 드립니다.

자료구조책이라면 저도 한 열권 가지고 있는데 어떤 책의 어느 부분을 보면 좋을까요?

이유는 다르지만 제가 작업하는 환경도 전역변수를 쓰는게 좋지 않다고 판단되어 최소한의 공간만으로 시간을 아끼는 방법을 찾고 있는 것이랍니다.

Quote:
BGP가 network에서 쓰이는 것은 network에서 전역변수를 쓰기가 어려워서예요

BGP가 아니라 TTL 말씀 하시는거죠?

===================================================================
8-bit

===================================================================
8-bit

winner의 이미지

이 경우에서도 필요에 따라 쓰실 수 있지요.

미로찾기 문제는 web 검색을 잘 하시면 어디든지 찾을 수 있습니다. 제가 책으로 공부하는 것을 좋아해서 이렇게 썼습니다만 좋아하시는 공부법에 따라 정보를 찾기는 어렵지 않을 것 같네요.

제가 학교에서 배운 책이 Horowitz와 Shani가 저술하고 서울대 이석호 교수가 번역한 자료구조 책이고 이 책에 나와서 위처럼 써버렸네요.

솔직히 이해할 수가 없는 것이 network 관련 program을 작성하실 때 전역변수는 당연히 쓰실 거예요. 그런데 이것을 질문하셨다는 것이 도대체 어떤 식으로 공부를 해오셨는지 알 수가 없네요. 이야기해주실 수 있나요?

linuxgeek의 이미지

답변 감사합니다.

Horowitz와 Shani가 저술하고 서울대 이석호 교수가 번역한 자료구조 책을 한 번 찾아 보겠습니다.

저도 찾아본다고 찾아 보았지만 제가 웹 검색 능력이 모자라서 어쩔 수 없이 질문을 올려 보았습니다.

마지막 줄에 쓰신 전역변수 관련해서는 죄송하지만 질문의 내용을 파악하지 못하겠습니다.

학부는 컴퓨터공학을 전공하진 않았고, 공부는 그냥 남들 하는대로 했었으며 학창 시절엔 그렇게 뛰어난 학생이 못되었습니다.

===================================================================
8-bit

===================================================================
8-bit

SoftOn의 이미지

Quote:

이 중에서 방금 지나온 블록은 스택에 넣지 않아야 하겠죠?

이걸 방금 지나온 블록이 아니라 지나온 모든 블록으로 확장하면 됩니다.

저 같은 경우 예전에 전체 크기를 미리 안다는 조건하에서

따로 맵전체에 해당하는 자료구조에 지나간 여부 표시하여 회피했습니다.

덧. 자료구조를 스택만 사용해야 된다면 방법이 안 떠오르네요.

linuxgeek의 이미지

자료구조를 꼭 스택을 쓸 필요는 없습니다. 사실 저도 정확히 스택을 쓰는 것은 아니구요.

워낙에 듣보잡 언어들을 많이 사용해야 하는지라 다루는 언어마다 시퀀스라는 이름으로 함수형언어들에서 쓰이는 선형 자료구조를 만들어서 쓰고 있습니다.

지금 하고 있는 일에서는 해당 자료구조를 스택처럼 쓰고 있어서 스택이라고 표현하였습니다.

되도록이면 고정된 글로벌 변수가 없이 함수에 패러미터로 일정한 크기의 인자를 넘겨 주면서 처리하고 싶었는데 딱히 다른 방법이 없다면 공간을 팔아서 시간을 사는 방법을 쓰는 수 밖에 없겠네요.

아무튼 답변 감사 드립니다.

아, 해당 미로의 매트릭스를 굳이 전역적으로 쓰지 않으려고 했던 이유는 프레임이 한 번 업데이트 될 때마다 해당 길찾기 연산이 수십번 반복될 가능성이 있는데 그게 시작점(S)와 목적지(G)가 다수 존재하는 경우이기 때문입니다. 즉 길찾기가 S1~Sn 에서 G1~Gn으로 각각 이루어지기 때문에 (가로x세로)의 매트릭스를 N개 만큼 만드는게 너무 비효율적일것이라 생각되어서였습니다.

===================================================================
8-bit

===================================================================
8-bit

neogeo의 이미지

A* 나 D* 알고리즘으로 검색해보시면 좋은 힌트를 많이 얻으실 수 있을것 같습니다.

Neogeo - Future is Now.

Neogeo - Future is Now.

linuxgeek의 이미지

답변 감사 드립니다.

D*는 잘 모르지만 A*는 저도 취미생활(?)로 사용해 본 적이 있는 알고리즘이긴 합니다.

다만 지금의 프로젝트의 경우 최단거리를 찾는 것이 아니라 목적지로의 길이 있는지(boolean)만 알면 되기 때문에 굳이 A*를 사용하지 않았습니다.

다른 방법을 찾지 못한다면 A*처럼 지나온 블록들을 closed스택에 저장하면서 이동하는 방법을 쓰는 수 밖에 없겠네요.

제가 사용한 두 가지 방법 중에 두 번째 방법이 비슷한 방법이었는데 워낙에 길찾기가 동시에 많이 이루어지는지라 감당키 힘든 병목현상이 생기더군요.

===================================================================
8-bit

===================================================================
8-bit

winner의 이미지

linuxgeek님의 글을 읽어보니 제가 한 수 배워야 할 입장인 것 같습니다.
함수형 스타일을 좋아하신다면 stack과 유사한 자료를 계속해서 넘기는 것이 정답일 겁니다.

동시에 길찾기가 이루어진다고 했는데 혹시 게임프로그래머신가요? 동시적으로 이루어진다면 죄송하지만 제가 말한 전역변수를 쓰시라는 말은 취소입니다. 이거 타짜를 몰라본 것 같아서 죄송하네요.

글에 나타난 문제는 알고리즘과 그에 따른 자료구조인데 네트워크 용어를 쓰셔서 제가 몰라봤습니다.

제 생각에는 이 문제는 흔히 자료구조와 알고리즘 수업에서 예로 드는 미로찾기 개념으로 생각하면 안 될 것 같습니다. 차라리 색칠하기 개념(영역분할)을 생각해보는게 좋을 것 같네요.

linuxgeek의 이미지

혼란을 드려서 죄송합니다.

타짜나 그런건 전혀 아니구요, 원래 하는 일은 네트워크 관련 일인데 지금 본의 아니게 전혀 생소한 분야의 프로그래밍을 하는 중이라서 게다가 제가 지식의 깊이가 얕아서 달리 비교할 용어들을 못 찾았었습니다.

그나저나 말씀하신 색칠하기(영역분할)라는 부분은 제가 전혀 모르는 분야인거 같습니다만 뭔가 어감이 무척 마음에 들고 제가 찾고 있던 정보가 아닌가 하는 생각이 듭니다.

인터넷에서 검색 좀 해봐야 겠습니다.

답변 감사드립니다.

===================================================================
8-bit

===================================================================
8-bit

winner의 이미지

어디서 따온게 아니고, 제가 만든 말이니까요. 그래도 찾아보면 있을 듯. ^_^
세상 모든 것, 하늘 아래 새로운 것은 없으니까요.
길이 있는지 없는지를 찾는거라고 하셨으니까 적절할거라고 생각합니다.

bestyt의 이미지

Queue를 이용하신다면 flooding 방법이 있습니다. 이게 경험상 속도가 Stack이용하는거보다 많이 빨랐던 걸로 기억하네요.

http://en.wikipedia.org/wiki/Flood_fill

JuEUS-U의 이미지

기본적인 미로찾기입니다.
재귀함수 기준의 통상적인 해결 방법입니다만...

- 재귀하는 함수에서 항상 접근이 가능해야되기 때문에
전역변수/동적할당으로다가 map data를 담습니다.
(동적할당이라면 함수 호출시마다 포인터를 넘겨줘야 합니다.)

- 함수 구조가
global 맵[N,N];
함수(x,y){
맵[x,y]에 마킹한다. (다른 것과 구분되는걸로)
주변을 살핀다. 만약 이동가능하면 (' '이라면) 그 곳으로 함수 호출.
// ex) 맵[x+1,y]==' ' 이면 함수(x+1,y)
맵[x,y]의 마킹을 지운다.
}

------------------------------
방금 댓글들을 읽어봤는데,
경로가 필요 없다면 윗분 말씀대로 flood fill이 훨씬 적합합니다.

linuxgeek의 이미지

winner님, bestyt님, JuEUS-U님 및 답변 주신 모든 분들께 감사 드립니다.

bestyt님께서 주신 링크를 보고 fillFlood로 해결하였습니다.

매트릭스의 크기를 미리 가늠할 수 없어 색칠용 매트릭스 대신에 hash 테이블을 만들어서 인자로 넘기는 방식을 썼는데

고질적이던 병목현상이 대폭 개선되었습니다.

감사 드립니다.

===================================================================
8-bit

===================================================================
8-bit

winner의 이미지

Flooding이라고 해서 P2P의 query flooding을 생각했었는데... -_-. (특히 Queue랑 Query 철자가 비슷하잖아요...)
Algorithm에서는 이렇게 불리는군요.

재미있네요. 역시 저도 algorithm을 잘 아는게 아니군요.

그런데 실제로 query flooding과 유사하군요.

nineye의 이미지


위에서 neogeo님이 말씀하신 A* 알고리즘이 괜찮아 보이네요.
floodfill은 갈 수 있는 모든 영역에 대해 검사하는데 비해,
적절한 heuristic값이 사용된 A* 알고리즘은 갈 수 있는 길을 빠르게
찾아주기 때문에 훨씬 더 효율적일 것 같습니다.
그런데 A* 비슷한 알고리즘을 썼는데 감당하기 힘든 병목현상이 있었다는 것은
이해하기 어렵네요...

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

winner의 이미지

길이 있는지 없는지를 찾아야하는 출발점과 도착점이 많다는 것이 이 문제의 병목요인입니다.
이 병목을 해결할 수 있는 적절한 응용기법이 A*에 있는지는 모르겠습니다만 A* 자체가 그렇게 쉬운 개념은 아닙니다.

비슷한 기법을 써서 C++로 약 200줄 정도를 들였던 기억이 있습니다. A*에 익숙해서 핵심을 잘 정리하면 100줄 정도로도 가능할 것 같긴 하네요.

하지만 floodfill은 제 생각에 50줄 정도면 충분합니다.

양이 2배니까 필요한 개념학습, debugging 등에 요구되는 복잡도는 4배 이상 아닐까요?

nineye의 이미지


글 내용을 보면 출발점과 도착점은 하나로 정의되어 있는 것 같은데요?
그래서 A*가 효율적이라 생각한 것입니다.

그리고 winner님 말씀처럼 단순한 테스트 용도의 prototype이라면 아무 알고리즘이나 빨리 구현할 수 있는 것을 선택하는 것이 맞는 것 같지만, 글 쓰신 분이 "이러한 길찾기 연산이 짧은 시간에 수십번씩 진행될 수도 있으며 미로의 크기도 10x10보다 클 수도 있습니다."라고 성능을 강조하셔서 A*를 쓰는 것이 어떠냐고 말씀드린 것입니다.

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

winner의 이미지

언제나 문제는 어디가 문제인지 모르기때문에 발생합니다.
괜히 의학드라마 House에서 "모든 환자는 거짓말을 한다"라고 말한 것이 아닙니다.
어떤 분들은 debugging에서 유사점을 발견했습니다만 알고리즘을 주로 한 제게는 알고리즘이 이런 문제로 보입니다.
우리가 idea를 찾는 과정은 과거를 버리는 창발적인 것이 아니라 이미 우리가 알고 있는 것들 중 적절한 것을 찾는 것일 때도 많습니다.

http://kldp.org/node/105252#comment-487171

저도 이 글을 보고 진짜 문제요인을 짐작할 수 있었습니다.
여기에 floodfill이 가능할 수 있는 길이 있는지 없는지를 판단할 뿐 경로가 필요한 것은 아니다라는 글은 발제글에 있었습니다.

그리고 저는 prototype으로서 단순 floodfill이 좋다고 말한 것이 아닙니다. 실제 업무에서도 단순한 것이 좋은 경우가 많다고 생각합니다. 정치적인 문제가 없다면 필요한만큼 단순하고, 필요한만큼 복잡한 것이 최고죠.

linuxgeek님의 글을 인용하신 부분("이러한 길찾기 연산이 짧은 시간에 수십번씩 진행될 수도 있으며 미로의 크기도 10x10보다 클 수도 있습니다.")을 볼 때 요구사항이 아직도 변할 수 있을 거라는 느낌이 듭니다. 어떻게 요구사항이 변경될지 모르는 상황에서 복잡도를 올리는 기술은 오히려 해가 될 가능성이 많습니다.

물론 복잡도가 높은 기술로 인하여 거꾸로 그것이 전화위복이 되어서 자신이 전체적인 정치를 주도할 가능성 또한 있기는 합니다.

nineye의 이미지


의학 얘기와 정치 얘기는 잘 모르겠고...
제가 평소에 가진 견해를 말씀드리면,
어떠한 문제를 해결함에 있어, 여러 가지 방법이 있을 때,
저는 컴퓨터 공학을 전문 분야로 하고 있기 때문에 항상 문제를 해결할 수 있는
방법들 중, 가장 효율적(성능 및 메모리 사용량)인 알고리즘을 선택하려고 노력합니다.

물론, 이익 집단에 속해 있는 사람으로써, 빠른 시간 내에 개발해야 조직의
이익에 부합한다는 조건이 있으면 어쩔 수 없겠지만, 글 쓰신 분이 그러한 조건은 말씀하시지 않았기 때문에 조금 더 시간이 걸려도 최대한 효율적인 알고리즘을 선택하는 것이 어떻냐고 제안한 것입니다.

그리고 winner님 말씀 중, 동의하지 못하는 내용에 대해 말씀드리면,
1. 글 쓰신 분의 댓글 내용을 보고 진짜 문제 요인을 짐작할 수 있다고 하셨는데, 제가 보기엔 그 댓글의 내용 중, 가장 중요한 부분은 알고리즘의 성능인 것 같은데요...
2. A*알고리즘은 경로를 찾는 알고리즘이기 때문에 필요한 것이 아니다.. 라고 하셨는데 경로를 찾는 것은 퍼즐의 해법이기도 하니 사용해도 되는 것 아닌가요?
3. 요구사항이 변하기 때문에 복잡도가 높은 기술은 해가 될 수 있다.. 라고 하셨는데, 우선 인용한 글을 보더라도 요구사항은 더 높은 성능을 요구하는 쪽으로 변경될 수 있을 것 같습니다. 어떤 요구사항을 예상해서 그런 말씀을 하셨는지 잘 모르겠네요.. 그리고 복잡도가 높은 기술이라서 요구사항을 쉽게 수용하기 어렵다는 것은 더더욱 이해가 잘 안되네요.. 복잡도가 높다는 것을 소스가 복잡해 진다고 생각해서 그렇게 말씀하신 것 같은데, 구조적인 설계를 할 수 있다면 상관없는 얘기 같습니다.
4. 복잡도가 높은 기술로 인하여 자신이 전체적인 정치를 주도할 가능성이 있다라... 제가 받아들이기에는 평소에는 대충(성능에 상관 없이) 개발하고, 뭔가 자신의 입지가 필요할 때에만 좀 신경써서 개발한다는 말로 들리는데.. 몇 십년을 개발하셔서 쌓인 노하우로 말씀하시는 것인지는 모르겠지만, 고작 5~6년 개발한 저로서는 좀 화가 나네요...

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

winner의 이미지

죄송합니다. 제가 정치적인 문제로 좀 디였다는 피해의식이 있다보니 그런 글이 나와버렸습니다.
사실 제 심성문제인데 말이지요.

확실히 글 쓰신 분은 성능을 중요시 여기고 있습니다. 저 또한 이쪽 방면의 다양한 알고리즘을 알지 못합니다. 당장 다른 분이 말씀하신 D*를 모르니 말입니다. A*는 확실히 후보대상이라고 생각합니다.

nineye의 이미지


저도 좀 오버해서 너무 공격적인 댓글이 되었다는 느낌이 드네요... 죄송합니다...
저 또한 정치적인 문제로 피해 받는 게 없지 않아 있긴 하지만,
아직은 개발 능력을 중시하는 개발자로 남고 싶다는 생각이 강해서 좀 심한 말을 한 듯 하네요.
사실 winner님 말씀도 맞습니다. 사실 개발자는 갖가지 정치적인 문제로 엮일 수 밖에 없는 것 같아서 씁쓸하긴 합니다만 현실적인 얘기를 빼 놓을 수가 없죠.. 저는 지극히 이상적인 얘기만 했고요.
winner님이 말씀하신 현실을 제대로 이해한 상태에서, 제가 말한 이상을 추구하면 좀 더 좋은 개발 환경을 만드는 것도 가능할 것이라 생각되네요.

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

sblade의 이미지

A* 를 쓰면 안됩니다. A* 는 최단경로를 "보장" 하기 위해 exponential complexity 를 감수하는 algorithm 입니다. 만약 출발에서 도착까지의 길이 없다고 가정하면, A* 는 가능한 모든 "경로" 를 뒤지게 되는데 이때 가능한 모든 경로의 수는 이 문제의 경우 미로가 n x n 그리드일때 4방향 찾기의 경우 "최소" O(n^3) 을 넘어갑니다. 대신 플러딩은 아무리 멍청하게 짜고 최악의 경우를 감안해도 n^2 이내에 끝납니다.

실제적으로도 이런 문제에 A* 를 적용해 보면 n 이 커질수록 감당할 수 없이 느려집니다.

휴리스틱을 잘 찾으면 A* 가 좀 빨라지긴 하는데, 문제는 좋은 휴리스틱을 찾는 것은 최단경로 문제를 푸는 것과 거의 동등한 문제입니다. 닭-달걀이죠.

일반적으로 사용할 수 있는 Euclidean distance 를 쓰게 되면, 결국 길을 찾긴 하지만 막힌 부분에서 한참 헤멜 겁니다.

경험상 이런 문제에서 가장 좋은 방법은 출발점에서 도착점으로 무작정 돌진하는 겁니다. 단 진행 방향에 확률적으로 perturbation 을 조금 넣어야 합니다.

winner의 이미지

A*가 일반적으로는 경로를 찾을 수 있는지 없는지 확실히 알 수 없는 상황에서 heuristic을 적용하여 길찾기를 하는 것으로 알고있습니다. 그래서 인공지능 길찾기 알고리즘으로 불리기도 하지요. 지수시간복잡도(exponential complexity)를 감수한다고 했지만 실제로 이렇게 하는 경우는 없을 거라고 생각합니다. 대게 중간에 길찾기 포기로 끝내버리겠지요.

따라서 활용배경이 원리적으로 다른 flooding과 A*를 같이 쓸 이유는 없을 것 같습니다. 하지만 필요에 따라(요구사항이 변하여 경로가 필요하다던가 혹은 더 높은 성능을 위하여) 섞어 쓸 수 있는 부분 idea들이 있다고 봅니다. 밑에 다른 분이 말씀하신 directional flooding도 그러한 생각 중 하나겠지요. 이렇게 하다보면 더이상 어디가 A*고, 어디가 flooding인지 알 수 없는 독자적인 알고리즘이라고도 할 수 있겠지만 말입니다.

저는 이 글타래가 말 그대로 사람들간의 이해소통을 위한 미로찾기라는 생각이 듭니다. 그래서 더욱 재미있었습니다만, 제가 쓴 글들이 다른 분에게 어떤 감정의 미로를 만들어냈는지 불안하기도 합니다.
적절한 복잡도의 기술을 사용할 것을 이야기했었지만 제 설명은 복잡도를 너무 올렸더군요.

최근 sblade님의 글은 제 관심의 대상입니다. 앞으로도 흥미로운 글 부탁드립니다.

----------------------------------------------------------------------------------------------

ㅋㅋ... directional flooding은 sblade님이 적으셨군요... 아놔..

nineye의 이미지


A*알고리즘이 최소 O(n^3)을 넘어간다고 하셨는데, A*알고리즘은 일반적인 경우 O(n^2)이며, 최악의 경우 O(n^3)이 될 수 있습니다. 그리고 목적지가 존재하지 않는다는 최악의 조건에서도 한번 방문한 칸은 다시 방문하지 못하는 조건이 있으면 O(n^3)까지는 소요되지 않을 것 같네요.
A*알고리즘의 특징은 최소의 확장으로 목적지까지의 경로를 찾는 것입니다. sblade님께서 말씀하신 것처럼 과연 nXn에서 n이 커질수록 A*알고리즘이 성능상으로 더 불리할까요? floodfill이 열려 있는 모든 칸을 방문해야 하는데 비해, A*는 열려 있는 칸들 중, 필요한 칸만 방문하면 됩니다. 즉, 논리적인 확장 모습만 따져보아도 더 유리하다고 생각되지 않나요? 결국 n이 클수록 감당할 수 없는 건 floodfill이 될 것입니다.
제가 생각할 때는, floodfill에 heuristic function이 추가된다면 A*와 비슷해 지지 않나 생각합니다. 구현 방식은 다르겠지만 목적지를 찾아가는 모습 자체는 비슷해 지니까요.. 그래서 floodfill알고리즘을 써서는 안된다고 단언하지는 않고, A* 알고리즘을 사용하는 것도 괜찮을 것 같다고 제안한 것입니다.
어떤 알고리즘이든, 그것을 실제 사용할 때에는 프로젝트의 성격에 맞게 변형 및 추가적인 기능을 넣어야 합니다. 뭔가 추가하면 가능한 것을 알고리즘의 본래 모습때문에 안된다.. 라고 단언해 버리는 것은 좀 성급한 판단이 아닐까요?

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

winner의 이미지

.

nineye의 이미지


놀리시는 거죠?

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

nineye의 이미지


한가지 더 첨언을 드리면,
문제의 성격상 해법은 A*가 더 맞지 않나 생각합니다.
A*는 경로를 찾는 것을 목적으로 하는 알고리즘이고, floodfill은 열린 공간을 채우는 것을 목적으로 하는 알고리즘입니다. 이 글에서의 문제는 목적지까지 갈 수 있는 길이 존재하냐.. 이기 때문에 floodfill보다는 A*가 더 적합하지 않나 생각합니다.
또한, directional floodfill에 대해서 말씀하셨는데, directional 이라는 것은 칸을 확장하는 순서를 정하겠다는 말과도 같은 것 같습니다. floodfill에서는 이러한 개념이 없기 때문에 새로운 개념에 대한 적용 방식을 만들어야 하는 반면, A*에서는 이미 priority queue라는 자료구조로 heuristic function에 의해 정해지는 순서를 이미 반영하고 있습니다.
결국 알고리즘은 자신이 해결하고자 하는 문제에 특화된 방향으로 발전되는 것이 일반적인 알고리즘의 모습인 것 같기 때문에 향후 요구사항이 많아 질수록, 동일한 목적을 추구하는 A* 알고리즘을 사용하는 것이 요구사항을 효율적으로 처리하는데 도움을 주지 않나..라고 생각합니다.

_________________________________________________________

nineye's blog

_________________________________________________________

nineye's blog

블루스크린의 이미지

미로 길찾기에서는 한손 벽 짚고 가기 방법을 쓰면
반드시 빠져나갈수 있다고 봤었는데

지금 문제에도 적용가능하다고 생각합니다

단 목적지가 문제와 같이 한쪽 바깥쪽에 붙어있는 경우에만 가능할것 같네요

최적화된 길은 아니겟죠...

-------------------------------------------------------------------------------
이 댓글(comment)의 수정 및 삭제를 위해 이 글에 답글(reply)을 쓰지 말아 주십시요.
의견이 있으시면 원 글에 댓글(comment)로 써 주세요.

-------------------------------------------------------------------------------
이 댓글(comment)의 수정 및 삭제를 위해 이 글에 답글(reply)을 쓰지 말아 주십시요.
의견이 있으시면 원 글에 댓글(comment)로 써 주세요.

bugiii의 이미지

벽 짚기는 맴돌기 가능성이 있습니다.

마이크로 마우스 대회 맵에 항상 적용되고 있는 것이죠.

tinywolf의 이미지

댓글들을 다 읽어보니 여러개의 목적지 중 도착할 수 있는 목적지 걸러내기에는 flooding이 정말 효율적이겠네요.
아주 예전에 홈페이지에 자바 애플릿으로 페인터만들때 사용했었는데, 목적에 따라 다양하게 사용할 수 있는 것이로군요. 하나 배웠습니다.

ㅡ_ㅡ;

sblade의 이미지

혹시 더 공부하시려면 참고하시라고 올립니다. 원글에 있는 스택에 "열린 길" 을 넣는 방법은 Depth-first search 라 불립니다. 이 경우 루프를 회피하는 방법은, 지나온 모든 노드만이 아니라, 모든 "방문한" 노드를 기억하면 됩니다. (visited list 라고 불립니다.) 즉 스택에 넣는 모든 노드를 기억하면 됩니다.

그리고 flooding 을 할 때, 맵이 크고, 특별한 구조가 없고, 목적지까지의 방향은 알 수 있는 경우 다음 방문 노드를 정할 때 목표쪽으로 향하는 노드가 높은 확률로 선택되도록 하면 상당히 도움이 될 겁니다. 즉 directional flooding 을 해야 합니다. 일반적인 방법은 목적지를 중심으로 potential field 를 만드는 건데, 물이 높은 곳에서 낮은 곳으로 흘러가도록 만드는 것을 상상하시면 되겠습니다. flooding 해나가는 방향을 확률적으로 선택해야 막다른 길에서 시간을 허비하는 것을 줄일 수 있습니다.

bestyt의 이미지

.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.