현재 위치

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

조언바랍니다. 빠른길 찾기? 최단거리 찾기

alwaysN00b의 이미지
글쓴이: alwaysN00b / 작성시간: 토, 2004/10/16 - 11:51오후

안녕하세요.

주제를 뭐라 써야 될지 모르겠네요.

학교서 프로젝트를 아무거나 하나 해오라고 하는데 조언바랍니다.

제가 할려는건
사용자가 지도에서 두지점을 입력하면
제일 빠른길 (안막히고 가까운길) 을 찾아 화면에 표시 해줄려고 합니다.

단순히 생각하기에
1. 일단 지도정보와 실시간 교통량은 이미 구축되어 있다고 가정하고
(시간이 된다면 이부분도 시뮬레이션 해보고 싶습니다)
2. 최단거리 탐색 알고리듬 등 을 이용해서 빠른길을 찾습니다.
(이부분에 사용할려고 하는건 너비 탐색 또는 깊이탐색 을 사용할려고 합니다.)
3. 결과를 지도 이미지위에 표시해 줄려고 합니다.

우선순위는 2,3,1 순으로 진행할려고 합니다.

저 혼자 아니면 2명이서 진행할려고 하는데 제가 프로젝트다운 프로젝트는 경험이 없는지라 이렇게 글을 올립니다.

( *nix 환경에서 웹 프로그래밍, system 프로그래밍만 하다보니 머리가 단순해진것 같습니다. 피치못할 사정으로 경험도 없는 윈도 환경에서 진행하게 되었습니다. 다른곳에 올릴수도 있으나 제가 항상 들리고 친숙한 곳이라... :oops: 리눅스 유저분들에게 죄송합니다. )

(구글형님께는 여러 알고리듬을 물어 공부중입니다. 되도록 현실성 있고, 실용가능한쪽으로 해볼려고 합니다.)

읽어 주셔서 감사합니다. 즐거운 주말 보내세요~

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

글쓴이: bass1ife / 작성시간: 일, 2004/10/17 - 12:53오전

질문이 좀 "두리뭉실한" 것 같네요
(제가 주위 사람들에게 질문할 때마다 지적받았던 거라서..ㅡㅡ;; )

조언 - 이라기보다 어떤 특정한(또는 명확하고 한정된 주제의) 문제에서 해결책을 질문하시는 것이
질문하신 분이나 답변하는 분들께도 좋을 것 같습니다만..

젠투, 젠투, 그리고 젠투.

Necromancer의 이미지

글쓴이: Necromancer / 작성시간: 일, 2004/10/17 - 10:25오전

먼저 거쳐야 되는 지점들을 고르고(사람도 어기 가기 위해서는 어디어디를 거친다
식으로 얘기하듯이... 그런 지점들을 찍어야겠죠)

그다음 거리계산에는 dijkstra (누구는 디지스트라-> 뒈져라 식으로 말하던데),
bellman-ford 알고리즘을 써야겠죠.

거쳐야 되는 지점이 많을 수록 좋지만 노가다에 계산시간도 더 걸리게 되니
잘 조정하시길 (두 알고리즘 다 O(n log n)의 복잡도입니다)

Written By the Black Knight of Destruction

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2004/10/17 - 11:15오전

참고자료를 검색하실 때 자동차가 최단거리 도로를 찾는 예제를 찾는 것 보다 네트웍 패킷이 최단거리 네트웍 경로를 선택하는 예제를 찾으시면 더 많은 정보를 얻을 수 있지 않을까 생각되네요.

제가 예전에 비슷한 것을 해 본적이 있는데 질문하신 유형의 예제는 매우 많았습니다.

좀 더 재미난 프로젝트를 해 보고 싶으시다면 이런 건 어떨까요?

두 개의 경로를 찾되, 두 개의 경로의 비용(시간)의 합이 최소가 되면서, 중복되지 않게 하는겁니다. 그러면 중간에 어느 한 부분에 문제가 생기더라도 (자동차라면 사고로 도로가 통제 된다거나, 네트웍이라면 선로가 절단된다거나) 즉시 다른 경로를 이용할 수 있으니까요.

이 경우 역시 다예스크라와 벨만-포드 알고리즘이 있습니다.

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2004/10/17 - 11:15오전

참고자료를 검색하실 때 자동차가 최단거리 도로를 찾는 예제를 찾는 것 보다 네트웍 패킷이 최단거리 네트웍 경로를 선택하는 예제를 찾으시면 더 많은 정보를 얻을 수 있지 않을까 생각되네요.

제가 예전에 비슷한 것을 해 본적이 있는데 질문하신 유형의 예제는 매우 많았습니다.

좀 더 재미난 프로젝트를 해 보고 싶으시다면 이런 건 어떨까요?

두 개의 경로를 찾되, 두 개의 경로의 비용(시간)의 합이 최소가 되면서, 중복되지 않게 하는겁니다. 그러면 중간에 어느 한 부분에 문제가 생기더라도 (자동차라면 사고로 도로가 통제 된다거나, 네트웍이라면 선로가 절단된다거나) 즉시 다른 경로를 이용할 수 있으니까요.

이 경우 역시 다예스크라와 벨만-포드 알고리즘이 있습니다.

choissi의 이미지

글쓴이: choissi / 작성시간: 일, 2004/10/17 - 11:27오전

길찾기 공부 할때 본 링크들인데
참고 하시길

http://www.ezdoum.com/stories.php?story=04/06/26/6508431

울랄라~ 호기심 천국~!!
http://www.ezdoum.com

alwaysN00b의 이미지

글쓴이: alwaysN00b / 작성시간: 일, 2004/10/17 - 4:50오후

답변 감사합니다.

진행하다 댓글 올리겠습니다. :D

언제나 시작

dhunter의 이미지

글쓴이: dhunter / 작성시간: 일, 2004/10/17 - 6:27오후

감사합니다. 지금까지도 이해 못하는 로직이지만 한번 배워봐야죠 :)

from bzImage
It's blue paper

댓글 달기

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

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