색다른 미로 찾기 알고리즘 ...

Sailor_moon의 이미지

안녕하세요 , 미로찾기 알고리즘을 보던중에 ... 색다른 미로를 찾는것에 대한 흥미가 돋아 , 의견 나누어 보고자 올립니다.
미로를 행렬로 표현 한다고 해보죠 , n x n 의 matrix 에 maze 가 perfect maze 라는 가정 하에 ... ( 한 지점부터 , 다른 한 지점으로 가는 루트가 단 하나 밖에 없는 미로 )

여러 명의 사람이 이 미로안에 떨어져 있을때, 서로를 찾는 가장 빠른 알고리즘이 뭐가 될 수 있을까요 ?
(단, 미로 안의 사람들은 서로의 좌표를 서로에게 브로드 캐스팅 해줄 수 있다)

처음 생각했던 것은 ,

미로안의 한명의 위치를 exit 으로 설계하고 , 나머지는 모두 right hand 알고리즘을 사용하여 , 그 exit 을 향해 나아가는 것인데,
너무 비효율 적이라는 생각이 들더군요.

이 exit 이 될 위치에 있는 사람도, 좌표상으로는 가까워 보일 지 몰라도 , 실제로는 뱅 돌아가야하는 미로에 있는 것일 수도 있어서,
함부로 어느 사람을 선택해야 할지도 ... 문제구요 .

혹시 다른 좋은 아이디어 있으신가요 ?

snowall의 이미지

한 지점에서 다른 지점으로 가는 루트가 단 하나밖에 없다면, 위상적으로 그 미로는 긴 직선에 가지가 여러개 있는 형태겠네요.

긴 직선 위에 한줄로 늘어놓는다고 생각하면, 그중 가운데 있는 사람에게 모이도록 하면 될 것 같은데요..

모이려면, 각자 자기가 미로의 출구쪽으로 가야 하는지 입구쪽으로 가야 하는지만 알면 됩니다. 안되면 결국 모든 사람이 입구나 출구로 가도록 해야겠죠.

만약 그 줄 위에 있지 않다면, 즉 루트 위에 있는게 아니든가 루트의 가지 위에 있는게 아니라면 아예 만날 수가 없습니다.

복잡도를 따진다면, 그냥 모두 출구를 찾아 가는 것이나 한사람에게 모이는 것이나 같겠네요.

피할 수 있을때 즐겨라! http://melotopia.net/b

juwon123의 이미지

right hand로 한 사이클을 돌때마다 가운데 지점을 새로 계산해서, 그 점을 목적지로 계속 나아가면 되지 않을까요??

cleansugar의 이미지

트리 모양 그래프 탐색하기 문제랑 같아지죠.

트리 모양 그래프를 탐색하는 에이전트에 대한 알고리듬을 찾아보면 될 듯합니다.

그런데 승객들이 전체 지도를 알고 있는지 여부를 말씀하시지 않았습니다.

전체 지도를 알고 있으면 실시간으로 브로드캐스트할 필요 없이 고정된 한 지점에서 만나면 됩니다.

도로나 지하철에서 사람들이 정모할 장소를 찾는 프로그램 만드는 중이신가요?

재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.

아이디의 아이디어 무한도전
http://blog.aaidee.com

귀태닷컴
http://www.gwitae.com

태훈의 이미지

'최단 경로 찾기' 문제를 풀기위한 알고리즘으로 [url=http://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98]A* 알고리즘[/url]이 많이 쓰입니다.

A* 알고리즘에서는 휴리스틱 함수를 어떻게 설정하느냐?가 주요 이슈가 되는대요. '최단 경로 찾기' 문제에서는 출발지와 목적지 사이의 직선거리를 휴리스틱 함수로 사용합니다.

자세한 내용은 키워드를 알려드렸으니 구글신께 물어보시길...:-)

Just do it!