현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

길찾기 알고리즘 때문에 그러는데 꼭좀 알려주세요

임용운의 이미지
글쓴이: 임용운 / 작성시간: 수, 2006/12/13 - 10:14오후

친구들과 프로젝트를 하나 하게 되었습니다
주제는 자세히는 말씀을 드릴수 없고 지도를 이용하게 되었습니다
근데 지도를 이용하는중 부가 서비스로 출발지로 부터 도착지까지 도로 최단거리를
구하는 알고리즘을 하나 구현하려다 일단 시간이 촉박한 관계로 기존에 나와 있는
알고리즘을 이용하기로 했습니다

내용은 이렇습니다 네이버 지도를 다운받아서

지도를 이진화를 시켜서 도로는 흰색이 나오게 하고 길을 찾아가 길을 찾은 부분에 대해 색으로 표현을
하려고 합니다

이리 저리 찾아보는데 어떤 알고리즘이 좋다고생각하시는지

고수분들의 조언을 구합니다
도와주시옵소서 ㅠㅠ

Forums: 
프로그래밍 QnA
moonlit의 이미지

글쓴이: moonlit / 작성시간: 수, 2006/12/13 - 11:45오후

를 많이 쓴다고 하던데, 안써봐서 잘 모르겠습니다.

moonend의 이미지

글쓴이: moonend / 작성시간: 목, 2006/12/14 - 12:27오전

a*이 가장 낫다고는 하지만 구현하려면 골이 지끈지끈해지실 겁니다.
넓이우선탐색이나 깊이우선탐색은 확실하지만 시간이 오래 걸리고...

우선 제일 간단한 검색은 '언덕 오르기hill climbing'기법입니다.
A 지점에서 나아갈 길에 대한 평가값을 구한 후, 적절한 값을 택해 B로 갑니다.
문제는 중간에 튀는 값이 있을 경우, 목적지 C로는 영원히 갈 수 없다는 것이죠...
[A와 C의 좌표값을 설정하면 대충 맞아들어가는데, 억지로 돌아가야하는 길에서는 쥐약이죠]

혼자서 하는 프로젝트면 A*을 구현하라고 하겠지만,
여럿이 하는 경우에는 그거 이야기하다가 마감기간이 넘어갈 겁니다... ^^;;

sphawk의 이미지

글쓴이: sphawk / 작성시간: 목, 2006/12/14 - 12:41오전

둘 다 자료 구하기도 쉽고 구현도 쉬운 알고리즘입니다.
노드수가 그리 많지 않다면 저걸로 한번 해보심이 어떠할지요?
그리고 A*는 기본적으로 휴리스틱 알고리즘이라, 찾아낸 해가 반드시 최적이라고는 할 수 없습니다.
노드 수가 수십개 단위라면 위의 알고리즘들을 써도 그리 느리지는 않을 듯 합니다.

seoleda의 이미지

글쓴이: seoleda / 작성시간: 목, 2006/12/14 - 6:55오후

오해의 소지가 있어 추가합니다.
결론을 먼저 말씀드리면 최단거리에 대한 A* 알고리즘은 최적해를 구합니다.
기본적으로 딕스트라나 A*모두 BFS를 변형한 알고리즘으로써, 휴리스틱 함수가 0인 경우, A*와 딕스트라 알고리즘은 동일하다고 볼 수 있습니다.

A*의 평가함수를 살펴보면, 시작점 s 부터 목적지 e 가지의 비용 현재노드(m)으로부터의 알려진 비용 f(s,m)와 목적지 까지의 추정된 비용 g(m,e)의 합으로 구성됩니다. 여기서 g(m,e)를 휴리스틱 함수라고 하며, 이 함수가 admissible 한 경우 A*는 최적 해를 도출합니다.

admissible의 의미는 추정한 비용(g(m,e))은 실제 비용(f(m,e))보다 작거나 같다.)입니다. 따라서 딕스트라 알고리즘은 휴리스틱함수가 g(m,e)==0 이라고 할 수 있으므로, "f(m,e)은 항상 영보다 같거나 크다" 라고 할 수 있기때문에 항상 최적해를 보장하는 것입니다.

최단거리 문제로 돌아와서 두 지점간의 직선 거리는 임의의 노드를 경우해서 가는 거리의 합보다 항상 작거나 같기 때문에 (admissible) 휴리스틱함수로 두 지점간의 직선거리를 사용한다면 최적해를 구할 수 있습니다.

p.s. 부등호를 본문에 어떻게 쓰죠?

coremaker의 이미지

글쓴이: coremaker / 작성시간: 목, 2006/12/14 - 1:24오전

정확히 말해 해당 지도의 거리 정보획득이 어렵지 않다면..
A*를 추천합니다..

윗분 말대로.. 노드수가 많지 않다면..
무엇을 쓰던 길만 찾기만 하면.. 성능과 크게 관계가 없겠습니다만..

노드수가 많아지고.. 재사용성의 효과가 반드시 필요하다면..
(A*를 이용해 한번 검색으로 시작 노드에서 다른 노드까지의..
최단거리(반드시는 아님니다만)를 재검색 없이 사용할 수 있겠습니다..)

지도엔 어차피 좌표가 있을 것이구요..
straight distance 는 어렵지 않게 바로 산출이 가능할 것이구요..

노드간 거리도 충분히 유추가 가능함으로.. A*를 사용하는데..
별지장이 없을 것으로 사료됩니다..

그리고 A* 생각보다 구현이 어렵진 않습니다...
단지 쉽게 문서상으로 이해하기 어렵기 때문이지 않을까 싶은데요..

note.
A* 로 구현할때.. Sort를 필요로 할 가능성이 높은데..
무조건 일반적 성능이 좋다고 quick sort 를 쓰시면 좋지 않습니다..
모든 알고리즘 중 best한 것은 모든 환경에 best 하지 않다는걸
명심하시고.. 선별해 사용하시는 센스가 필요합니다..

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.