컴퓨터 교수가 탐욕적 알고리즘을 사용하여 납치된 차량을 회수하는 것이 얼마나 실용적일까요?

Super Neuro에서

작년 크리스마스 휴가 동안, 노트르담 대학교 컴퓨터 과학과의 종신 교수이자 박사 과정 지도 교수이며, 전자공학과의 종신 교수이기도 한 시이위는 할리우드 스타일의 자동차 검색을 경험했습니다.

차량이 납치된 지 24시간 이내에 Shi 교수는 차량 자체에서 제공하는 퍼지 위치 지정 기능을 사용하여 탐욕스러운 접근 방식, 빠르고 정확하게 차량을 찾아내고, 차를 되찾았습니다.

사례 검토

 

사우스 벤드 

시카고

출발하다

 

점심시간

1일차 오전 12시 차량 강탈 시 교수는 타이어에 공기를 넣기 위해 주유소에 들렀습니다. 시 교수가 차량 상태를 점검하던 중, 두 갱단이 틈을 타 차량을 납치했습니다. 당황한 시 교수는 몰래 휴대폰을 좌석 뒤 주머니에 넣었다.
	1일차 오후 5시 추적 시작 경찰에 신고했지만 소용이 없자, 시 교수는 가능한 한 빨리 스스로 차의 위치를 찾기로 결심했습니다. 학교로 돌아와서 추적을 시작했지만 휴대폰의 위치를 더 이상 알 수 없었습니다.

2일차 오전 5시 퍼지 포지셔닝 시 교수는 차량에 내장된 마쓰다 모바일 스타트(MMS)를 이용해 차량의 위치를 알아냈는데, 그 위치는 자신으로부터 80km 이상 떨어져 있었고, 시스템 오차는 6~7m였다.

2일차 오전 7시 60미터 떨어져 있어요! 시 교수는 탐욕 알고리즘을 통해 빠르게 추론을 내렸습니다.상대적 거리가 더 이상 감소하지 않으면 시간을 멈추고 수직 방향으로 검색을 계속합니다. 이 방법을 사용하여 시 교수는 거리를 단 60m로 줄였고, 마침내 차고에서 정확한 위치를 찾아냈습니다.

2일차 오전 9시 경찰은 무력하다 경찰이 도착하기를 기다리는 동안 시 교수와 샤오 왕은 강도들이 뭔가 이상한 것을 알아차리고 차를 몰고 도망갔을지도 모른다는 것을 알게 되었습니다. 시 교수는 경찰에 휴대전화를 건네주고 차량을 계속 추적했지만 경찰은 시 교수의 알고리즘에 따라 수색하지 못했습니다.

2일차 오전 10시 차를 돌려받으세요! 시 교수는 휴대전화를 되찾은 후, 차량 찾기 알고리즘을 계속 사용하여 마침내 주차장에서 도난당한 차량을 찾아냈습니다. 경찰은 차량을 시 교수에게 성공적으로 돌려주었습니다.

시 교수의 궁극의 자동차 추격 기술: 탐욕 알고리즘

이 긴박했던 자동차 강탈 사건은 시 교수의 처형과 정확한 알고리즘 추론 덕분에 단 24시간 만에 해결되었습니다.

경찰조차도 시 교수가 얼마나 빨리 문제를 해결할 수 있었는지 놀랐습니다.

"컴퓨터공학 교수들을 건드리면 안 됐어! 멍청한 거야? 어떻게 컴퓨터공학 교수들을 털 수 있지?"

시 교수는 차량 위치 지정의 핵심 기술은 실제로 컴퓨터 알고리즘에서 가장 직접적인 탐욕적 접근 방식이라고 설명했습니다.

탐욕 알고리즘,탐욕 알고리즘이라고도 불리며, 수학 및 컴퓨터 과학에서 가장 유명하고 고전적인 알고리즘 중 하나입니다.

문제를 해결할 때는 그 전이나 후에 무슨 일이 일어났는지에 관계없이 현재 상태에만 관심이 있고 현재 하위 문제에 대한 최적의 솔루션만 얻습니다. 그러나 매번 얻어진 지역적 최적해를 활용할 수 있다면 전역적 최적해 또는 최적 목표를 도출할 수 있다.

시 교수는 탐욕적 알고리즘을 자동차 찾기 기술에 적용했습니다.
  운전 중, 자신과 차량 사이의 상대적 거리가 더 이상 줄어들지 않는다면 즉시 운전을 멈추세요.
  그런 다음 수직 방향으로 검색을 계속합니다.

이는 거리가 감소하는 방향으로 단조로운 탐색을 항상 수렴할 수 있도록 보장하는 나선형 탐색 구조입니다.

결국 차에 두 사람만 타고 있던 상황에서 시 교수는 내비게이션 소프트웨어의 안내를 받아 오차 범위 3km 내에서 신속하게 도난당한 차량을 찾아냈습니다. 탐욕적 알고리즘은 가장 정확한 도구였습니다.

탐욕 알고리즘의 다른 고전적 응용 프로그램

탐욕 알고리즘은 고전적 알고리즘 중 하나로 널리 사용되지 않습니다.

탐욕 알고리즘은 지역적 최적 솔루션 전략을 해결해야만 전역적 최적 솔루션을 얻을 수 있기 때문입니다. 따라서 우리는 문제가 탐욕적 알고리즘 전략에 적합한지 여부와 찾아낸 해가 반드시 문제에 대한 최적 해인지 여부에 주의를 기울여야 합니다.

예를 들어 배낭 문제와 경로 문제에서 탐욕의 아름다움을 설명하는 데는 다음과 같은 고전적 알고리즘이 사용됩니다.

다익스트라 알고리즘이는 컴퓨터 과학자 에드거 다이크스트라가 1956년에 고안하여 1959년에 발표한 가중 방향 그래프에서 단일 소스 최단 경로(SSSP)를 계산하는 알고리즘입니다.

이를 통해 해결되는 문제는 다음과 같습니다.
그래프 G와 소스 정점 v가 주어졌을 때, v에서 그래프의 모든 정점으로 가는 최단 경로를 구하시오.

다익스트라 알고리즘은 탐욕 알고리즘 패러다임을 사용하여 설계되었습니다.

경로 길이가 증가하는 순서대로 각 정점에 대한 최단 경로를 하나씩 생성합니다.알고리즘을 수행하는 동안 가장 짧은 경로를 찾은 정점을 저장하는 정점 집합 SS를 유지해야 합니다. 또한 거리 배열 dist를 유지하는 것이 필요한데, dist[i]는 i번째 정점과 소스 노드 s 사이의 거리 길이를 나타냅니다.

• S가 초기화되면 소스 노드 s만 포함됩니다. dist[]dist[]가 초기화됩니다: dist[i]= arc[s][i], arc는 그래프의 인접 행렬입니다. V−SV−S는 최단 경로를 찾지 못한 정점 집합을 나타냅니다.

• distdist를 증가하는 순서로 정렬하고, 최단 경로를 선택하고, V−SV−S에서 S에 해당하는 정점을 추가하고, 새로운 정점 u가 S에 추가될 때마다 distdist를 업데이트해야 합니다. 즉, s가 정점 u를 통해 더 가까운 다른 정점에 도달할 수 있는지 여부를 업데이트해야 합니다. 
  즉, dist[u] + arc[u][v] < dist[v]이면 dist[v]=dist[u]+arc[u][v]로 업데이트됩니다. 

• S=VS=V가 될 때까지 위의 단계를 반복합니다. 

이스터 에그: 탐욕 알고리즘의 새로운 질문 유형

그날은 마침 H국의 국경일이었고, 왕은 대신 n명을 초대하여 상품을 걸고 게임을 하게 했습니다. 먼저 그는 각 대신에게 왼손과 오른손에 정수를 하나씩 쓰라고 했고, 왕 자신도 왼손과 오른손에 정수를 하나씩 썼습니다.

그런 다음, 왕이 팀의 앞에 서도록 하여 n명의 대신을 한 줄로 세웁니다. 줄을 선 모든 대신들은 왕으로부터 보상으로 금화를 받게 됩니다. 각 장관이 받는 금화의 수는 다음과 같습니다.결과는 장관 앞에 있는 모든 사람의 왼손에 있는 숫자를 곱하고, 장관의 오른손에 있는 숫자로 나눈 다음, 반올림한 것입니다.

왕은 어느 한 신하가 특별히 많은 보상을 받는 것을 원하지 않으시므로, 가장 많은 보상을 받는 신하가 가능한 한 적은 보상을 받도록 팀의 순서를 재조정하는 데 도움을 주시기를 바랍니다.

(왕은 항상 줄의 앞에 있다는 점에 유의하세요.)