일상 생활에서의 수학 : 위성 항해자

위성 내비게이터는 확실히 매우 일반적인 도구이며, 종종 그 작동이 단순히 "길을 보여주는"위성으로부터 정보를 수신하는 것이라고 가정합니다. 실제로 목적지에 도달 할 수있는 경로를 설정하는 능력은 우리가 어느 순간에 있는지 정확하게 식별하는 능력, 정확하고 업데이트 된 로드맵의 가용성과 관련된 다양한 기술의 조합의 결과입니다. 무엇보다도 목적지에 도달하기위한 최적의 경로를 계산하는 기능입니다. 이 기사에서는이 계산의 기초에 매우 정확한 수학적 이론 인 "그래프 이론“두 지점 사이의 최단 경로를 식별하는 방법을 이해할 수 있습니다. 실제로, 우리는 추상적 과학적 개념이 어떻게 실용적이고 실제적이며 무엇보다도 매우 유용한 대상의 기초가되는지를 봅니다.

우선, 맨 아래부터 시작하겠습니다 : 그래프 란 무엇입니까?

실제로는 서로 연결된 일련의 요소에 지나지 않습니다. 각 요소를 "노드"라고하고 연결을 "아크"라고합니다. 그래프의 예는 고속도로 네트워크를 통해 서로 연결된 일련의 도시를 요소로 갖는 그래프입니다.이 경우 노드는 도시이고 호는 도시 자체 사이의 고속도로 세그먼트입니다. 그래프를 선 (호)으로 연결된 일련의 컬러 공 또는 원 (노드)으로 상상할 수 있습니다. 원호는 방향이 될 수도 있고 방향이 지정되지 않을 수도 있습니다. 무 방향 아치는 양방향으로 통과 할 수있는 아치입니다. 네비게이터 예제에서 도로는 한 방향 인 경우 방향 호로 간주 될 수 있지만 양방향 인 경우 방향이없는 아치로 간주 될 수 있습니다.

가중치라고하는 값이 각 호와 연관되면 그래프에 가중치가 부여된다고합니다. 이 값은 일반적으로 양수 또는 음수 일 수 있습니다. 이전의 도시 및 고속도로 예를 참조하면 각 고속도로 구간을 킬로미터 단위의 길이와 연결하여 가중치 그래프를 얻을 수 있습니다. 그래프에서 이론적으로 노드 A에서 노드 B로 이동하는 것은 실제로 다른 도로를 사용하여 한 도시에서 다른 도시로 이동할 수있는 것처럼 서로 다른 호를 사용하여 여러 가지 방법으로 가능합니다. 그런 다음 노드 A를 노드 B에 연결하는 "최단 경로"를 "최단 경로"라고합니다.

위성 내비게이터의 경우 시작점과 끝점 사이의 경로를 찾는 것은 그래프 내에서 최단 경로를 찾는 것과 같습니다. 그래프의 수학적 이론에서는 최단 경로 계산 문제가 모든 관점에서 연구되고 분석되었으며 많은 알고리즘이 생성되었습니다. 예를 들어 가장 많이 사용되는 것 중 하나는 Dijkstra의 알고리즘, 그러나 다른 많은 것들이 있습니다. 따라서 가장 적절하다고 판단되는 알고리즘을 선택하는 것은 브라우저 제조업체의 선택입니다. 이 선택에서 두 노드 사이의 최단 경로 검색의 기초가되는 이론은 특히 매우 복잡한 로드맵에서 계산을 수행 할 때 매우 복잡 할 수 있다는 점을 확실히 고려해야합니다. 예를 들어, 각 노드에 대한 "통계적 추정"을 사용하여 최단 경로를 검색하는 A * 알고리즘이 개발되었습니다. "어려운 단어"로 말하면이 추정치는 최종 목적지로가는 도중에 한 노드를 다른 노드보다 통과하는 이점에 대한 사전 평가를 나타냅니다. 어쨌든 알고리즘의 세부 사항에 들어가는 것은 다소 복잡해지고 특정 지식이 필요합니다. 우리는 어떤 경우 에든 문제에 대한 기본적인 비전을 제공하고 아마도 일상 생활에 많은 실질적인 영향을 미치는 수학적 이론에 대한 관심을 자극하기를 바랍니다.

Giovanni Calcerano 저