볼랜드포럼: [자바] 외판원 문제에 대하여

	C++Builder \| Delphi \| FireMonkey \| C/C++ \| Free Pascal \| Firebird

경고! 게시물 작성자의 사전 허락없는 메일주소 추출행위 절대 금지

분야별 포럼

볼랜드포럼 홈

회원 메뉴

자유게시판		세상 살아가는 이야기들을 나누는 사랑방입니다.

[22001] [자바] 외판원 문제에 대하여
즈티브삽스 [horudoga]	5710 읽음 2012-10-09 03:34

예를들어 랜덤의 도시 위치가 좌표에 뜹니다.

도시1(0, 100)
도시2(200, 300)
도시3(500, 400)
.....

"나"는 좌표 (0.0)에서 시작을 하구요. 랜덤으로 형성된 도시 좌표를 모두 1번씩 방문하고 제자리(0,0)으로 '최단거리'로 돌아오는 코드를 짜야 하는데.
외판원 문제(Traveling Salesman Problem)이 이 문제를 해결하기에 적합할 것 같거든요. 그래서 나름 책이다 구글이다 찾아보고 있는데 생각만큼 녹록치가 않습니다.

일반적으로 설명하고 있는 외판원 문제는 저런 좌표가 아니라 a, b, c, d 같은 점으로 표현하고 있어서. x축과 y축으로 위치를 나타내는 좌표를 외판원 문제에 어떻게 적용하고 이걸 어떻게 코드로 구체적으로 구현해야 할 지 감이 서질 않습니다..

조언해 주실 분 있으신가요?
부탁드립니다.

Trackback : http://www.borlandforum.com/impboard/impboard.dll/trackback?sn=139176

civilian [civilian] 2012-10-09 08:25 X

Traveling salesman problem

이라 검색하면 엄청난게 나오는데 뭐가 더 필요한가요?

[oranke] 2012-10-09 10:11 X

아~ 전산 비전공자다보니, 이런 주제 나오면 흥미가 솟아요~~
출근길에 뒤져보니 아래 사이트에 설명과 함께 C#으로 된 구현이 하나 있네요.

http://www.lalena.com/AI/Tsp/

Lyn [tohnokanna] 2012-10-09 10:37 X

귀찮으면 풀스캔 ㅋㅋ

어차피 이거 NP 문제 아님?

[oranke] 2012-10-09 10:47 X

풀스캔 하고 싶지만... 20!만 되도... 2,432,902,008,176,640,000 ... 제 컴은 똥컴... ㅋㅋㅋ...

신동승,無敵 [moojuck] 2012-10-09 15:30 X

질문하시는 분은 x,y 좌표를 점 a, b, c, d에 어떻게 매핑시키는지와 같은 기초적인 질문을 하고 계시는데 댓글들은 어째 산으로 가는 답변같은.. ㅋ

간단히 점 a = 좌표 (x,y)로 표현합니다.
점 a와 b의 거리는 (x_a, y_a) 좌표와 (x_b, y_b) 좌표를 이용해서 구하면 되고요.
두 점 사이의 거리를 구하는 방법은 수학 책 찾아 보시거나 검색 한번 해 보면 나오고요.
나머지는 salesman problem 적용하면 될 겁니다.

Lyn [tohnokanna] 2012-10-09 16:06 X

신동승 // 에이 설마 그런걸 물어보시려구요 ... 두점간의 거리구하는건 중학교 산수문제인데 ...