[C언어] 최단시간 경로 문제 (몬테카를로 방법)

소개글

최단시간으로 갈 수 있는 경로를 몬테카를로 방법을 이용해 구한 예제입니다.
프로그램은 Microsoft Visual C++ 환경에서 작성했습니다.

목차

(1) 문제
영호는 바닷가를 지나다가 물에 빠진 사람을 발견하고 구하려고 한다. 영호와 조난자의 위치는 위 그림과 같고, 영호는 평지에서 8m/s, 백사장에서 4m/s 속력으로 달리고, 바다에서 2m/s 속력으로 헤엄친다고 한다. 이 때 영호가 조난자에게 가장 빨리 가는 경로를 구하라.

(2) 문제 분석
영호가 각 구간을 직선으로 달려간다면, 각 구간별 걸린 시간은

본문내용

(2) 프로그램


앞의 변분을 이용한 풀이에서는 인 점을 찾아내면(단, , 인 경우) 것으로 해를 구할 수 있지만 손으로 풀기가 쉽지 않다. 다음 프로그램에서는 몬테카를로 법으로 a,b를 0~100m 범위에서 무작위로 찍어 시간을 비교한다.
0~100m 범위의 모든 점들을 확인하는 것은 시간 낭비이므로 1차로 시간이 덜 걸리는 경로를 대충 얻고, 범위를 점점 좁혀가는 방법을 썼다. 범위를 좁혀가는 정도와 각 주기당 검사횟수를 잘 조절하는 것이 요령이다. 어느 정도 계산을 진행하면 double형 변수의 유효 자리수 한계에 부딪히게 된다.


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

const int Freq=(int)pow(10,5); // 한 주기당 검사 횟수

double ran(); // 0과 1 사이의 난수를 만드는 함수

void main()
{
double x_init=0, y_init=0; // 출발점
double ax,bx; // 난수로 만들 a,b
double ay=100, by=170; // 1,2 및 2,3 구간 경계선의 y좌표
double x_final=100,y_final=220; // 도착점

double l1,l2,l3; // 각 구간을 이동한 거리
double v1=8,v2=4,v3=2; // 각 구간에서의 속력
double t1,t2,t3; // 각 구간에서 걸린 시간
double t=1e+4; // 걸린 총 시간 (최소값 구하기 위해 초기값을 크게 잡아줌)

double t_a, t_b; // t_a, t_b : t를 a와 b로 편미분한 값
double partial_t; // partial_t = t_a+t_b (t의 도함수)

참고 자료

없음