수정된 단순 방법의 예. 수정된 심플렉스 방법. 새로운 참조 계획으로 이동

소개

1. 이론부 6

1.1 그래프 이론의 기본 개념 6

1.2 여행하는 판매원 문제에 대한 해결책의 공식화 및 일부 속성. 8

1.3 그래프 10의 문제로서 여행하는 외판원 문제에 대한 설명

1.4 해밀턴 회로의 존재 조건 10

1.5 분기 및 바인딩 방법 .............................................................. 열하나

1.6 여행하는 외판원 문제의 실제 적용 .............................. 17

2. 실무 20

결론

서지

소개

의사결정 이론은 수학, 경제, 경영 및 심리학의 개념과 방법을 포함하는 연구 분야입니다. 다양한 종류의 문제를 해결하기 위해 사람들이 선택하는 방법의 패턴을 연구하고 가장 수익성이 높은 솔루션을 찾는 방법도 탐구합니다.

이 과정에서는 여행하는 외판원 문제를 해결하는 몇 가지 방법과 솔루션 알고리즘에 대해 논의합니다.

일상 생활에서 접하게 되는 많은 작업은 다변량입니다. 많은 것 중에서 가능한 옵션시장 상황에서는 자연적, 경제적, 기술적 능력에 부과된 제한을 고려하여 최상의 솔루션을 찾는 것이 필요합니다. 이러한 점에서 경제 상황과 시스템을 분석하고 종합하기 위해서는 수학적 방법과 현대 컴퓨터 기술을 사용할 필요가 있게 되었습니다.

이것의 목적 코스 작업여행하는 세일즈맨 문제와 그 해결 방법을 고려하는 것입니다.

여행하는 외판원 문제를 고려하고, 여행하는 외판원 문제를 해결하기 위한 분기 및 경계 방법에 대한 알고리즘을 제공합니다.

이론적인 부분

1.1 그래프 이론의 기본 개념

많은 의사결정 문제는 그래프 이론을 사용하여 해결할 수 있습니다.

그래픽 표현은 연구된 프로세스 시스템이나 현상을 평면에 시각적으로 표시하는 것입니다(그림, 드로잉, 다이어그램 및 블록 다이어그램, 다이어그램, 그래프). 그래프 이론의 언어에서는 많은 문제가 형성되고 해결됩니다. 기술적 문제, 경제, 사회학, 경영 등 분야의 과제 그래프는 개체와 개체 간의 관계를 시각적으로 나타내는 데 사용됩니다.

허락하다 G- 방향이 없는 그래프. 기하학적으로 그래프는 일련의 정점(점)으로 표현될 수 있으며, 특정 쌍은 선으로 연결됩니다. 예를 들어, 도시를 연결하는 도로망, ,,,, 다음과 같은 그래프로 표현될 수 있다. 도시는 점(정점)으로 표시되고 도로는 방향이 정해지지 않은 선으로 표시됩니다(그림 1.1).

그림 1.1 도시 간 도로망.

방향이 없는 노선은 해당 도시 쌍 사이의 양방향 교통을 나타냅니다. 선의 교차점은 정점으로 간주되지 않습니다.

그래프를 그릴 때 평면 위의 정점 위치, 모서리의 곡률 및 길이는 중요하지 않습니다(그림 1.2).

그림 1.2 그래프 이미지

그래프의 꼭지점은 문자 또는 자연수로 지정됩니다. 그래프의 가장자리는 숫자 쌍입니다.

라우팅 대상 G모든 인접한 두 모서리가 끝점을 갖도록 유한 또는 무한 모서리 시퀀스가 ​​호출됩니다. 게다가 같은 엣지 이자형경로를 따라 여러 번 나타날 수 있습니다.

순환경로(Cyclic Route)는 출발지와 도착지가 일치하는 경로이다.

회로는 각 모서리가 최대 한 번 발생하는 경로입니다. 체인의 정점은 한 번만 반복될 수 있습니다. 체인의 모든 부분이 체인입니다. 비순환 체인은 정점이 반복되지 않으면 단순 체인입니다.

그래프의 각 정점 , , 사이에 경로의 초기 정점인 경로()가 있고 최종 정점인 경우 그래프가 강하게 연결되어 있다고 합니다.

한 쌍의 꼭지점 사이에 이 시퀀스의 인접한 요소가 공통 꼭지점을 갖는 일련의 요소(호 또는 모서리 또는 호와 모서리 모두)가 있는 경우 그래프를 연결이라고 합니다. 분명히, 강하게 연결된 그래프는 모두 연결되어 있습니다. 순환이 없는 연결된 무방향 그래프를 트리라고 합니다. 트리에서는 임의의 두 정점이 단일 체인으로 연결됩니다.

1.2 여행하는 외판원 문제에 대한 해결책의 공식화 및 일부 속성

여행하는 세일즈맨(떠돌이 상인)은 첫 번째 도시를 떠나 알 수 없는 순서로 도시를 한 번 방문해야 합니다. 2,1,3.. N그리고 첫 번째 도시로 돌아갑니다. 도시 간의 거리가 알려져 있습니다. 여행하는 세일즈맨의 폐쇄 경로(투어)가 최단이 되도록 도시를 어떤 순서로 돌아야 합니까?

문제를 과학적인 형태로 가져오기 위해 몇 가지 용어를 소개합니다. 도시는 숫자로 번호가 다시 매겨집니다. 제이 티=(1,2,3..N) . 여행하는 세일즈맨의 여행은 순환 순열로 설명할 수 있습니다. 티=(제이 1 , 제이 2 ,.., 제이 N , 제이 1 ) , 그리고 모든 것 제이 1 .. 제이 N – 다른 숫자; 처음과 끝을 반복 제이 1 , 순열이 순환적임을 보여줍니다. 정점 쌍 사이의 거리 와 함께 ij매트릭스를 형성하다 와 함께. 도전은 그런 투어를 찾는 것입니다 티:

(1)

여행하는 외판원 문제의 수학적 공식화와 관련하여 두 가지 언급을 하는 것이 적절합니다.

1) 단계적 와 함께 ij거리를 의미하므로 음수가 아니어야 합니다. 즉, 모든 제이 티:

와 함께 ij  0; 씨 젭 = ∞ (2)

(마지막 평등은 투어의 루프 금지를 의미합니다.) 대칭형, 즉 모든 나, 제이:

와 함께 ij = C 지 (3)

그리고 삼각형 부등식을 만족시킵니다. 즉, 모든:

와 함께 ij + 씨 jk  씨 나는 (4)

수학적 공식은 임의의 행렬을 말합니다. 사람이 많아서 이렇게 된거임 응용 문제, 이는 메인 모델에 의해 설명되지만 모든 조건 (2)-(4)를 만족하지는 않습니다. 조건 (3)은 특히 자주 위반됩니다(예를 들어 다음과 같은 경우). 와 함께 ij-거리가 아니라 요금: 종종 티켓 가격이 하나이고 왕복 티켓 가격이 다른 경우가 많습니다. 그러므로 우리는 여행하는 외판원 문제의 두 가지 버전, 즉 조건 (3)이 만족되는 경우의 대칭 문제와 그렇지 않은 경우의 비대칭 문제를 구별할 것입니다. 조건 (2)-(4)는 기본적으로 충족된 것으로 간주됩니다.

2) 비대칭 여행 외판원 문제에서는 모든 투어가 티=(제이 1 , 제이 2 ,.., 제이 N , 제이 1 ) 그리고 티’=(제이 1 , 제이 N ,.., 제이 2 , 제이 1 ) 길이가 다르므로 두 가지를 모두 고려해야 합니다. 분명히 다른 투어 (N-1)! .

첫 번째 문제를 해결하고 마지막 장소순환 순열 수에서 제이 1 , 그리고 나머지 N-1 우리는 모든 숫자를 다시 정렬할 것입니다 (N-1)! 가능한 방법. 결과적으로 우리는 모든 비대칭 투어를 얻습니다. 대칭 투어는 다음에서 가능합니다.

두 배 더 적으니까 각각은 두 번 계산됩니다. 어떻게 티 그리고 어떻게 티’ . C가 1과 0으로만 구성되어 있다고 상상할 수 있습니다. 그 다음에 와 함께가장자리가 그래프로 해석될 수 있습니다. (나, 제이) 경우에 수행 와 함께 ij =0 다음과 같은 경우에는 수행되지 않습니다. 와 함께 ij =1 . 그런 다음 길이가 0인 투어가 있으면 모든 정점을 한 번 포함하는 사이클을 거치게 됩니다. 이러한 순환을 해밀턴 순환이라고 합니다. 닫히지 않은 해밀턴 순환을 해밀턴 체인(해밀턴 경로)이라고 합니다.

그래프 이론의 관점에서 대칭 문제여행하는 세일즈맨은 다음과 같이 공식화될 수 있습니다.

다나 완전한 네트워크와 함께 N정점, 모서리 길이 (나, 제이)= 와 함께 ij. 최소 길이의 해밀턴 사이클을 찾습니다. 비대칭 외판원 문제에서는 "cycle" 대신 "contour"라고 말하고, "edges" 대신 "arcs" 또는 "arrows"라고 말해야 합니다.

일부 응용 문제는 순회 판매원 문제로 공식화되지만, 이 문제에서는 해밀턴 사이클이 아닌 해밀턴 체인의 길이를 최소화해야 합니다. 이러한 문제를 개방형이라고 합니다. 일부 모델은 여러 명의 출장 판매원의 문제로 축소되지만 여기서는 고려하지 않습니다.

1.3 여행하는 외판원 문제를 그래프로 표현한 문제

공식: 많은 도시:
. 도시 i와 j 사이의 거리:
. P – 요소 A의 순열 집합, 순열

도시에 그래프의 꼭지점과 이를 도로에 연결하는 호가 할당된 경우 그래프 이론의 관점에서 문제는 최소 길이의 해밀턴 윤곽선을 결정하는 것입니다. 해밀턴 윤곽선은 시작 꼭지점이 끝 꼭지점과 일치하는 그래프의 모든 꼭지점을 통과하는 경로입니다. 여기서 윤곽선의 길이는 윤곽선에 포함된 호의 개수가 아니라 그 길이의 합으로 이해됩니다. 해당 도로의 길이는 가장자리의 무게입니다. 그래프는 완전해야 합니다. 즉, 가능한 모든 모서리를 포함합니다. 그래프가 완전하지 않은 경우 다음과 같은 가중치를 갖는 누락 간선으로 그래프를 보완할 수 있습니다.
.

1.4 해밀턴 회로의 존재 조건

찾아야 할 시퀀스(경로)는 유향 그래프에서 최소 가중치의 단순 주기에 걸쳐 지향됩니다. 이러한 주기를 해밀턴이라고도 합니다. 분명히 완전한 이중 그래프에는 위에 표시된 유형의 주기가 포함되어 있습니다. 완전한 수음표에 대한 여행하는 외판원 문제의 특별한 경우로서 수음표에 해밀턴 사이클이 존재하는지에 대한 질문을 고려하는 것으로 충분하다는 점에 유의하십시오. 실제로 주어진 이중 그래프가 완전하지 않은 경우 누락된 모서리를 보완하여 완성할 수 있으며 추가된 각 모서리에 가중치를 할당할 수 있습니다. 이것이 "컴퓨터 무한대"입니다. 고려되는 모든 가능한 숫자의 최대값. 이제 새로 구성된 완전 이중 그래프에서 가장 가벼운 해밀턴 사이클을 찾으면 가중치가 있는 간선이 있으면 이 원래 그래프에는 "여행하는 세일즈맨 사이클"이 없다고 말할 수 있습니다. 완전한 이중 그래프에서 가장 가벼운 해밀턴 사이클의 무게가 유한한 것으로 판명되면 이는 원래 그래프에서 원하는 사이클이 됩니다. 해밀턴 윤곽선은 시작 꼭지점이 끝 꼭지점과 일치하는 그래프의 모든 꼭지점을 통과하는 경로입니다. 여기서 윤곽선의 길이는 윤곽선에 포함된 호의 개수가 아니라 그 길이의 합으로 이해됩니다.

해밀턴 사이클.

허락하다 G-그래프. 해밀턴 사이클은 주어진 그래프의 모든 정점을 포함하는 간단한 사이클입니다.

정리 1.

해밀턴 사이클이 그래프에 존재하려면 그래프가 연결되어 있어야 합니다.

정리 2.

전체 그래프에서 , n>=3이면 해밀턴 사이클은 완전한 이분 사이클입니다.
m>=1이면 해밀턴 사이클이 있습니다.

1.5 분기 및 바인딩 방법

세다 두 개의 부분 집합으로 구성된 비어 있지 않은 유한 집합입니다. . 첫 번째 하위 집합
(정점)은 임의의 요소 집합으로 구성됩니다. 두 번째 하위 집합(호)은 첫 번째 하위 집합 요소의 순서쌍으로 구성됩니다.
. 꼭지점
그리고
그렇게
, 그러면 이들은 인접한 꼭지점입니다.

그래프의 경로는 일련의 정점입니다.
반드시 쌍별로 구별되는 것은 아닙니다.
인접한 . 경로의 모든 가장자리가 쌍별로 구별되는 경우 경로를 체인이라고 합니다. 만약에
그런 다음 경로를 폐쇄라고 합니다. 폐쇄 회로를 사이클이라고 합니다.

문제의 공식화

여행하는 세일즈맨은 여행을 떠나야 한다 N 도시. 비용을 줄이기 위해 그는 모든 도시를 정확히 한 번만 돌고 최소한의 비용으로 원래 도시로 돌아올 수 있는 경로를 만들고 싶어합니다.

그래프 이론의 관점에서 문제는 다음과 같이 공식화될 수 있다. 세트 N정점과 행렬( 씨 ij), 여기서 씨 ij ≥0 – 호의 길이(또는 가격)( 나, 제이),
. 아래에 여행하는 세일즈맨 루트지사이클을 이해해보자 나 1 , 나 2 ,…, 나 N , 나 1개 점 1,2,…, n. 따라서, 노선호의 집합입니다. 도시 간 경우 나그리고 제이전환이 없으면 "무한대" 기호가 행렬에 배치됩니다. 대각선으로 배치해야 합니다. 즉, 이미 통과한 지점으로 되돌아가는 것이 금지되어 있음을 의미합니다. 여행하는 세일즈맨 루트, 경로 길이 엘(지)는 경로에 포함된 호 길이의 합과 같습니다. 허락하다 지– 가능한 모든 경로의 집합입니다. 초기 피크 나 1 – 고정. z 0  경로를 찾아야 합니다. 지, 그렇게 엘(지 0)=최소 엘(지), 지  지.

문제의 해결

분기 및 경계 방법의 주요 아이디어는 먼저 경로 집합 Z의 길이에 대해 하한 Φ를 구성하는 것입니다. 그런 다음 경로 집합을 두 개의 하위 집합으로 나누어 첫 번째 하위 집합이 일부 호(i, j)와 다른 하위 집합을 포함하는 경로로 구성됩니다. 이 호를 포함하지 않았습니다. 각 하위 집합에 대해 하한은 원래 경로 집합과 동일한 규칙에 따라 결정됩니다. 하위 집합의 결과 하한 그리고 모든 경로 집합의 하한보다 작지 않은 것으로 밝혀졌습니다. 즉, ψ(Z)≤ ψ(), ψ(Z) ≤ ψ().

하한 비교 φ () 그리고 φ (), 우리는 경로의 하위 집합을 선택할 수 있습니다 가능성이 더 높음최소 길이의 경로를 포함합니다.

그런 다음 하위 집합 중 하나를 유사한 규칙에 따라 두 개의 새로운 집합으로 나누고 . 하한값이 다시 발견됩니다. φ (), 그리고 φ () 등. 단일 경로를 찾을 때까지 분기 프로세스가 계속됩니다. 최초의 기록이라고 합니다. 그런 다음 그들은 찢어진 가지 사이로 살펴봅니다. 하한이 첫 번째 레코드의 길이보다 크면 문제가 해결됩니다. 하한이 첫 번째 레코드의 길이보다 작은 경우, 하한이 가장 작은 하위 집합은 최상의 레코드를 포함하지 않는다고 확신할 때까지 추가 분기를 거칩니다. 노선.

하나가 발견되면 경로 길이의 새 값과 관련하여 끊어진 분기 분석이 계속됩니다. 두 번째 기록이라고 합니다. 모든 하위 집합이 분석되면 솔루션 프로세스가 종료됩니다.

순회 판매원 문제와 관련된 분기 및 경계 방법의 실제 구현을 위해 하위 집합의 하한 경계를 결정하고 경로 집합을 하위 집합으로 분할(분기)하는 기술을 나타냅니다.

하한을 찾기 위해 우리는 다음과 같은 고려 사항을 사용합니다. 여행하는 외판원 문제 매트릭스의 임의 행(행 또는 열)의 요소에서 특정 숫자를 더하거나 빼면 계획의 최적성은 유지되지 않습니다. 변화. 어떤 길이 여행하는 세일즈맨 루트이 금액만큼 변경됩니다.

각 줄에서 이 줄의 최소 요소와 동일한 숫자를 뺍니다. 각 열에서 해당 열의 최소 요소와 동일한 숫자를 뺍니다. 결과 행렬을 행과 열로 축소라고 합니다. 뺀 모든 숫자의 합을 감소 상수라고 합니다.

캐스팅 상수는 경로 길이의 하한으로 선택되어야 합니다.

경로 집합을 하위 집합으로 분할

분기가 수행되는 호 세트에 포함될 후보를 식별하기 위해 주어진 행렬에서 모든 요소를 ​​​​고려합니다. 0과 같음. 이 행렬의 0 요소의 각도 Θ ij를 찾아보겠습니다. 0 요소 Θ ij의 차수는 행의 최소 요소의 합과 같습니다. 나열의 최소 요소 제이(이 최소값을 선택할 때 씨 ij – 고려되지 않음). 가장 높은 확률로 필요한 경로는 최대 각도가 0인 호에 속합니다.

호를 포함한 경로의 지불 매트릭스를 얻으려면 ( 나, 제이) 우리는 행렬의 행을 지웁니다 나및 열 제이, 경로에서 순환이 형성되는 것을 방지하기 위해 현재 체인을 무한대로 닫는 요소를 대체합니다.

호를 포함하지 않는 많은 경로( 나, 제이)는 요소를 교체하여 얻습니다. 씨 ij에서 무한대로.

분기 및 경계 방법을 사용하여 여행하는 외판원 문제를 해결하는 예

여행하는 세일즈맨은 6을 여행해야 합니다. 도시. 비용을 줄이기 위해 그는 모든 도시를 정확히 한 번만 돌고 최소한의 비용으로 원래 도시로 돌아올 수 있는 경로를 만들고 싶어합니다. 소스 도시 A. 도시 간 이동 비용은 다음 매트릭스로 제공됩니다.

문제의 해결

표시의 편의를 위해 결제 매트릭스 아래의 모든 도시 이름(A, B, ..., F)을 해당 행과 열의 번호(1, 2, ..., 6)로 대체합니다.

모든 경로 집합의 길이에 대한 하한을 찾아보겠습니다. 각 행에서 이 행의 최소 요소와 동일한 숫자를 뺀 다음 각 열에서 이 열의 최소 요소와 동일한 숫자를 빼서 행과 열에 행렬을 표시해 보겠습니다. 행 최소값: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

한 줄씩 빼면 다음과 같은 결과를 얻습니다.

열 최소값: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.

이를 열별로 뺀 후 다음 행렬을 얻습니다.

하한값을 구해보자 φ (지) = 15+1+0+16+5+5+5 = 47.

분기가 수행되는 호 세트에 포함될 후보를 식별하기 위해 이 행렬의 0 요소(행과 열의 최소값의 합)의 각도 Θ ij를 찾습니다. Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. 가장 높은 차수는 Θ 14 = 10입니다. 호 (1, 4)를 따라 분기를 수행합니다.

집합의 하한
47과 동일하게 유지됩니다. 세트의 모든 경로에 대해 도시 A에서 도시 D로 이동하지 않습니다. 행렬에서 이는 셀 (1, 4)에 기호 를 배치하여 표시됩니다. 이 경우 도시 A를 떠나면 하한의 추정치가 다음과 같이 추가됩니다. 적어도첫 번째 행의 가장 작은 요소입니다. φ () = 47 + 10.

해당 매트릭스에 우리는 씨 14 = ∞.

r 1 = 10으로 축소 절차를 수행한 후 57 + 10 = 67의 새로운 하한을 얻습니다.

에 해당하는 행렬에서 첫 번째 행과 네 번째 열을 지우고 씨 41 = 1→ 4 → 1 주기가 발생하는 것을 방지하기 위해 새로운 보수 행렬( 씨 1ij ):

줄이려면 첫 번째 열의 최소값(h 1 =1)을 빼야 합니다. 여기서 결론 47+1 = 48과 같아집니다. 하한 비교
φ () = 67 및 φ () = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

쌀. 1.4 첫 번째 단계의 분기

다음으로 분기 프로세스를 계속합니다. 이 행렬의 0 요소 Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2의 차수 Θ ij를 찾아보겠습니다. 가장 큰 차수는 Θ 21입니다. 그런 다음 세트는 호(2, 1)를 따라 두 개의 새로운 세트로 분할됩니다.
그리고 .

행렬에서 행 2와 열 1을 지웁니다. 호(1, 4)와 (2, 1)은 연결된 경로(2, 1, 4)를 형성합니다. 씨 42 = 무한 2→1→ 4 → 2 사이클이 발생하는 것을 방지합니다.

줄이려면 4번째 줄에서 최소값을 빼야 합니다. r 4 =2. 이 경우 하한은 48+2 = 50이 됩니다.

하한 이전 분기 단계에서 얻은 는 48 + 16 = 64와 같습니다. 하한 비교 φ () = 64 및 φ () = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

쌀. 1.5 두 번째 단계의 분기

에 대해 주어진 지불 매트릭스

이 행렬의 0 요소의 차수 Θ ij는 Θ 36 = 5, Θ 45 = 0, Θ 56 = 22, Θ 62 = 13, Θ 63 =7, Θ 65 = 0입니다. 가장 높은 차수는 Θ 56입니다. 세트는 두 개의 새로운 및 .

하한 50 + 22 = 72와 같습니다. 행렬에서 5행과 6열을 지우고 다음을 입력합니다. 씨 65 = 무한. 우리는 행렬을 얻습니다:

줄이려면 라인 3을 따라 최소값을 빼야 합니다. r 3 =5. 이 경우 하한은 50 + 5 = 55가 됩니다. 추가 분할을 위해 경로의 하위 집합을 선택합니다.

쌀. 1.6 세 번째 단계의 분기

에 대해 주어진 지불 매트릭스

줄이려면 4행에서 최소값을 빼야 합니다(r4=7). 이 경우 하한은 55+7 = 62가 됩니다. 축소 후 우리는 다음을 얻습니다.

22 행렬에서 길이가 0인 두 개의 전이((4, 3) 및 (6, 2))를 얻습니다.

쌀. 1.7 네 번째 단계의 분기

쌀. 1.8 추정치가 있는 가지 트리

받았다 여행하는 세일즈맨 루트지 0 = (1, 4, 3, 5, 6, 2, 1) 또는 (A-D-C-E-F-B-A).

1.6 여행하는 외판원 문제의 실제 적용

실제로 여행하는 외판원 문제를 명백하게 적용하는 것 외에도 여행하는 외판원 문제를 해결하기 위해 축소할 수 있는 다른 문제가 많이 있습니다.

페인트 생산 문제.

n개의 페인트 생산을 위한 생산 라인이 있습니다. 다른 색깔; 이 색상을 숫자 1,2...n으로 지정하겠습니다. 모두 생산 라인하나의 프로세서를 고려하겠습니다. 또한 프로세서는 한 번에 하나의 페인트만 생산하므로 페인트는 특정 순서로 생산되어야 합니다. 생산은 순환적이므로 페인트는 순환 순서로 생산되어야 합니다.  = ( j 1, j 2,.., j n, j 1). 페인트 i 생산을 마친 후 페인트 j 생산을 시작하기 전에 페인트 i에서 장비를 세척해야 합니다. 이를 위해서는 시간 C가 필요합니다. C가 i와 j 모두에 의존하고 일반적으로 C≠C라는 것이 명백합니다. 특정 주문을 선택하면 페인트 생산 주기에 시간을 투자해야 합니다.

여기서 t k는 k번째 페인트의 순 생산 시간입니다(전환은 계산하지 않음). 그러나 우변의 두 번째 합은 일정하므로 풀 타임총 전환 시간과 함께 생산 주기당 최소화됩니다.

따라서 순회판매원 문제와 교체시간 최소화 문제는 하나의 문제일 뿐이고, 그 변형들만 다른 말로 설명하고 있다.

펀칭 프레스 문제.

홀 펀칭 프레스는 다수의 동일한 패널(구멍이 한 번에 하나씩 순차적으로 펀칭되는 금속 시트)을 생산합니다. 다른 모양그리고 규모. 개략적으로, 프레스는 x, y 좌표를 따라 독립적으로 움직이는 테이블과 테이블 위에서 회전하는 디스크로 표현될 수 있으며, 그 주변에는 다양한 모양과 크기의 구멍을 뚫는 도구가 있습니다. 각 장비는 하나의 사본으로 제공됩니다. 디스크는 두 방향(회전 좌표 z)으로 동일하게 회전할 수 있습니다. 실제로 공구를 아래로 가져갈 때 그 아래에 매달린 공구를 누르는 프레스가 있습니다. 원하는 지점잎.

j번째 구멍을 펀칭하는 작업은 4개의 숫자(x j,y j,z j,t j)를 특징으로 합니다. 여기서 x j,y j는 좌표입니다. 희망 직군표에서 z j 는 원하는 디스크 위치의 좌표이고 t j 는 j 번째 구멍을 펀칭하는 시간입니다.

패널 생산은 본질적으로 순환적입니다. 각 시트 처리의 시작과 끝에서 테이블은 (x 0, y 0) 위치에 있어야 하고 디스크는 z 0 위치에 있어야 하며 이 위치에는 구멍이 없습니다. 만들어진. 시스템의 초기 상태는 가상의 제로 홀을 펀칭하는 것으로 간주될 수 있습니다. 매개변수 사용(x 0 ,y 0 ,z 0 ,0).

i번째 구멍 바로 뒤에 j번째 구멍을 펀칭하려면 다음 단계를 수행해야 합니다.

x 축을 따라 x i 위치에서 x j 위치로 테이블을 이동하고 시간 t (x) (|x i -x j |)=t i, j (x) 를 소비합니다.

y축을 따라 동일한 작업을 수행하고 시간 t i, j(y)를 소비합니다.

두 개의 호 중 가장 짧은 호를 따라 머리를 위치 z i에서 위치 z j로 회전시키면서 시간 t i, j (z)를 소비합니다.

j번째 구멍을 뚫고 시간 t j 를 보냅니다.

함수 t(x), t(y), t(z)의 특정 형태는 프레스의 기계적 특성에 따라 다르며 상당히 번거롭습니다. 이러한 함수를 명시적으로 작성할 필요는 없습니다.

동작 1-3(i번째 홀에서 j번째 구멍으로 전환)이 동시에 발생하며, 이러한 동작 중 가장 긴 동작이 완료된 직후 펀칭이 발생합니다. 그렇기 때문에

C = 최대(t(x), t(y), t(z))

이제 이전 사례와 마찬가지로 컴파일 작업은 최적의 프로그램홀 펀칭 프레스의 경우 여행하는 세일즈맨 문제(여기서는 대칭)로 줄어듭니다.

실용적인 부분

30만 화폐 단위를 가진 투자자는 자동차 회사 A와 건설 회사 B의 주식에 자신의 자본을 투자할 수 있습니다. 위험을 줄이려면 B의 주식보다 A의 주식을 최소 두 배 이상 구매해야 하며 후자는 그럴 수 없습니다. 10만 화폐 단위를 초과하지 않고 구매할 수 있습니다. A주 배당금은 연간 8%, B주 배당금은 10%입니다. 첫해에 얻을 수 있는 최대 이익은 얼마입니까?

A와 B의 주가가 동일하고 CA = CDB = 1,000이라고 가정합니다.

해결책 작업분기 및 경계 방법을 사용하여 최적 경로 찾기

교과과정 >> 수학

수학적 진술 작업 여행하는 세일즈맨 5 1.2.분기 및 바인딩 방법. 5 1.3. 연산 솔루션 6 1.4. 계획 솔루션 작업 6 ... 허용되는 세트 솔루션(계획) 일부에게 방법중단... 이 문제와 그녀의 해결책분기 방법을 사용하여 ...

개미 알고리즘 적용 결정 작업최적화

업무 >> 컴퓨터 과학

중앙 집중식 관리 및 그녀의특징은 교환... 조건입니다 작업. 왜냐면 모두를 위해서 작업 방법숙소... 결정 작업최적화. 1.1.개미 알고리즘의 사용 작업 여행하는 세일즈맨. 일다음과 같이 공식화 일 ...

NP-완전 적용 작업비대칭 키 암호화에서

교과 과정 >> 컴퓨터 과학

사진 방법 솔루션주어진 작업그리고 입는다... 변환 중 그녀의 c 1. 증인은 그러한 집합입니다. 일영형... 해결책"태그" 크기 일 여행하는 세일즈맨그래프 색상 문제 일정점 덮음에 대해 일세트 커버에 대해 일클릭에 대해 일 ...

프로그래밍 언어(6)

개요 >> 컴퓨터공학

에 존재하는 가상 개념 그녀의프레임워크 내 - 테이블, 테이블스페이스... 인텔리전스. 여기에는 개발이 포함됩니다. 방법 솔루션 작업비유하자면, 공제 방법은 다음과 같은 목적으로 사용됩니다. 솔루션 NP-완전 작업, 예를 들어, 작업 여행하는 세일즈맨. AI가 하고 있다...

					1.9 OOP 14090 – 07 KR PZ
	시트	№ 문서	서명	날짜
개발됨		코베시니코프 D.V.			여행하는 세일즈맨 문제 해결	리테라			시트	시트
Rukov.		셀류티나 O.N.

투표: 25, 14

그것은 무엇입니까?

때로는 결과적인 NP-완전 문제를 해결해야 하는 경우도 있습니다. 이 경우, 첫째, 알고리즘이 최악의 경우 기하급수적으로 유지되면서 다음과 같이 작동하도록 전체 검색을 단축하는 것이 때때로 가능합니다. 허용되는 시간실제 데이터에. 둘째, 정확한 해결책은 아니지만 이에 대한 일부 근사치는 만족스러울 수 있습니다. 이러한 솔루션을 제공하는 알고리즘을 근사라고 합니다.

"무차별 대입" 문제를 해결하는 방법은 여러 가지로 나눌 수 있습니다. 일반적인 방법무차별 대입 개선.

어려운 문제를 해결하는 방법

• 분기 및 바인딩 방법일부 추정에 따라 전체 클래스에서 명백히 최적이 아닌 솔루션을 폐기하는 것으로 구성됩니다.
• 일부 현재 솔루션 근처에서 보다 최적의 솔루션을 찾는 것으로 구성됩니다.
• 대략적인 방법과 경험적 방법결정 요소를 선택하기 위해 경험적 방법을 사용하는 것으로 구성됩니다.
• 의사다항식 알고리즘서브클래스를 표현하다 동적 프로그래밍
• 방법 무작위 검색 선택을 일련의 무작위 선택으로 표현하는 것으로 구성됩니다.

근사 알고리즘의 품질 평가

최적화 문제를 해결해 보겠습니다. 즉, 비용 함수가 지정된 개체 집합 중에서 비용이 가장 높거나 낮은 개체를 찾습니다. 나타내자 최적의 솔루션 C*처럼요. 그리고 알고리즘이 우리에게 제공하는 솔루션은 C입니다.

다음과 같은 경우 알고리즘이 ρ(n)회 이하의 오류로 문제를 해결한다고 말할 수 있습니다.

최대(C ⁄ C *, C * ⁄ C) ≤ ρ (n)

두 개의 상호 역수량의 최대값은 1보다 작지 않으므로

때로는 |로 정의된 상대 오류를 사용하는 것이 더 편리합니다. C − C *| ⁄ C *

다음과 같은 경우 알고리즘의 오류는 ε(n)보다 크지 않다고 말할 수 있습니다.

| C − C *| ⁄ C * ≤ ε (n)

ε(n)이 함수 ρ(n), 즉 ε(n) ≤ ρ(n) − 1을 통해 위에서부터 제한될 수 있다는 것을 쉽게 확인할 수 있습니다. 실제로 최소 문제의 경우 이 불평등은 평등으로 변합니다. 최대 문제의 경우 ε (n) = (ρ (n) − 1) ⁄ ρ (n) (또한 ρ (n) ≥ 1이라는 점을 기억해야 합니다.

많은 문제에 대해 대략적인 알고리즘이 알려져 있습니다. 문제 해결(입력 길이에 관계없이) 고정된 횟수 이하의 오류가 발생합니다. 다른 경우에는 그러한 알고리즘이 알려져 있지 않으며 오류 추정치가 n에 따라 증가하는 알고리즘에 만족해야 합니다.

일부 문제의 경우 연산 시간을 늘리는 대신 근사의 품질을 향상(상대 오류 감소)하는 것이 가능합니다. 이에 대한 근사 방식 최적화 문제문제 조건에 더해 양수 ε을 받고 상대 오차가 ε 이하인 솔루션을 제공하는 알고리즘입니다.

고정된 ε > 0에 대해 작동 시간이 n의 일부 다항식을 초과하지 않는 경우 근사 방식을 다항식이라고 합니다. 근사 방식은 작동 시간이 n과 1 ⁄ ε의 일부 다항식에 의해 제한되는 경우 완전 다항식이라고 합니다.

여행하는 외판원 문제는 최적화 방법을 위한 시험장입니다.

여행하는 외판원 문제의 공식화(1934):

여행하는 세일즈맨은 첫 번째 도시를 떠나서 알 수 없는 순서로 도시 2, 3, ..., n을 한 번 방문한 후 첫 번째 도시로 돌아가야 합니다. 도시 간의 거리가 알려져 있습니다. 여행하는 세일즈맨의 폐쇄 경로(투어)가 최단이 되도록 도시를 어떤 순서로 돌아야 합니까?

그래프 이론의 관점에서 문제는 다음과 같이 공식화될 수 있습니다. 완전한 유향 그래프 G = (V, E)가 있고 각 호(u, v)는 가중치 c(u, v)와 연관되어 있습니다. 이 그래프에서 최소 비용의 해밀턴 윤곽선을 찾아야 합니다.

문제 해결을 위한 알고리즘에 매우 중요한 세부 사항에 주목해 보겠습니다.

1. 두 공식 모두 c(u, v) ≥ 0이라고 가정합니다. 모든 u에 대해 c (u, u) = , v ∈ V.
2. 순진한 공식은 모든 u, v ∈ V에 대해 c(u, v) = c(v, u)를 가정합니다. 즉, 그래프는 방향이 없는 것으로 간주될 수 있습니다. 이 문제를 대칭형 여행 세일즈맨 문제라고 합니다. 그러나 일반적인 경우, 의무사항은 아닙니다.
3. 순진한 공식에서 우리는 모든 u, v, w ∈ V c (u, v) ≤ c (u, w) + c (w, v) (삼각형 부등식)라고 가정합니다. 실질적인 문제. 그러나 일반적으로 이것은 사실이 아닙니다.

정리

P ≠ NP, ρ ≥ 1이라고 가정합니다. 그러면 ρ배 이하의 오류로 일반적인(게다가 대칭) 여행하는 세일즈맨 문제를 해결하는 다항식 근사 알고리즘이 없습니다.

증거.증명을 위해, 임의의 그래프 G = (V, E)를 취하고 (u, v) ∈ E 및 ρ | 뷔 | + 1 그렇지 않으면. 다항식 알고리즘이 그래프 G에 해밀턴 사이클이 포함되어 있는지 여부를 결정하는지 확인하겠습니다. 이는 불가능합니다.

분기 및 바인딩 방법("역추적")

이 방법은 최초의 효과적인 암시적(개선된) 열거 방식 중 하나이며, 그 아이디어는 극한 문제를 해결할 때 명백히 최적이 아닌 솔루션을 삭제하여 완전한 열거를 피할 수 있다는 것입니다.

이 방법의 아이디어는 다음과 같습니다. 이산 극단 문제를 해결할 때 가능한 모든 옵션 세트를 클래스로 나누고 이에 대한 추정치를 구성합니다. 결과적으로 점수가 특정 기록 값보다 나쁠 경우 전체 솔루션 클래스를 폐기하는 것이 가능해집니다.

일반적인 형태의 이산 극단(명확성, 최소) 문제를 고려해 보겠습니다.

이산 집합 A가 주어지고 그것에 함수 f가 정의되어 있다고 가정합니다. X에 대한 함수 f의 최소값을 F(X)로 표시하겠습니다.

x 0 ∈ A를 구해야 합니다: f (x 0) = F (A)

참고 1

A = A 0 ∪ A 1 ∪ … ∪ A k , A i ∩ A j = Ø, i ≠ j 라고 가정합니다. 게다가 F(A)< F (A 0), т. е. на A 0 минимум не достигается.

그러면 다음이 참입니다: F (A) = min ( F (A i) | i ∈ 1: k )

노트 2

Φ를 Φ (X) ≤ F (X) ∀ X ⊂ A가 되도록 집합 A의 부분 집합 모음에 정의된 함수라고 가정합니다.

x *를 A의 임의 요소로 두고 f * = f(x *)로 둡니다.

그러면 다음이 참입니다: F (A) = min ( f *, min ( F (A i) | i ∈ 1: k, Φ (A i) ≤ f *) )

이러한 두 가지 고려 사항을 통해 우리는 최소값을 찾는 기술을 다음과 같이 제안할 수 있습니다. 집합 A를 일부 부분 집합 A i로 나누고 각각에 대한 Φ의 하한을 찾아보겠습니다. 집합 A의 요소에 대해 함수 f의 값을 계산하고 가장 작은 값을 레코드 값으로 기억합니다. 함수의 레코드 값(f*)보다 점수가 높은 모든 하위 집합을 하위 집합 A 0으로 결합하여 더 이상 고려하지 않도록 하겠습니다.

이제 A i, i > 0인 집합 중 하나를 선택해 보겠습니다. 이 집합을 여러 개의 작은 하위 집합으로 나누어 보겠습니다. 동시에, 우리는 계속해서 기록적인 f* 값을 향상시킬 것입니다. 이 프로세스는 모든 세트 A i, i > 0이 검사될 때까지 계속됩니다.

분기 및 경계 방법(역추적)은 가능성 트리를 사용하여 더 명확하게 설명할 수 있습니다. 이러한 트리의 노드는 구성 모음(집합 A의 하위 집합 A i)으로 간주될 수 있으며 특정 노드의 각 하위 항목은 이 모음의 하위 집합을 나타냅니다. 마지막으로 각 시트는 서로 다른 구성을 나타냅니다.

예제 1. 여행하는 외판원 문제(Little의 알고리즘)

구체적인 예를 사용하여 이 알고리즘의 작동을 살펴보겠습니다.

인접 행렬로 정의된 그래프가 있다고 가정합니다.

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

다음은 사실입니다. 행렬 C의 모든 행 또는 열의 모든 요소에서 상수를 빼면 최소 투어는 최소로 유지됩니다. 이와 관련하여 각 행에서 최소 요소를 빼는 프로세스(라인별 캐스팅)는 최소 투어에 영향을 주지 않습니다. 마찬가지로 동일한 속성을 갖는 열 축소 개념이 도입되었습니다.

원래 행렬을 행별로 제시해 보겠습니다.

원래의

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

한 줄씩 나열됨

—	2	0	4	3	10	|4
0	—	1	5	1	4	|6
1	4	—	1	0	7	|3
4	7	0	—	1	7	|4
4	4	0	2	—	4	|3
7	3	3	4	0	—	|7

선택된 굵은 글씨로원래 행렬의 숫자는 사전 편찬 검색을 통해 얻은 이상적인 여행입니다.

(환원 상수의 합은 4 + 6 + 3 + 4 + 3 + 7 = 27입니다.)

그런 다음 열별로 다음을 수행합니다.

—	0	0	3	3	6
0	—	1	4	1	0
1	2	—	0	0	3
4	5	0	—	1	3
4	2	0	1	—	0
7	1	3	3	0	—
—	—	—	—	—	—
0	2	0	1	0	4

(여기서 환원 상수의 합은 0 + 2 + 0 + 1 + 0 + 4 = 7이고 모든 상수의 합은 27 + 7 = 34입니다.)

이제 비용이 0인 가장자리만 통과하는 투어는 분명히 최소화됩니다. 비용을 결정하기 위해 방금 계산한 상수 34를 0에 추가합니다.

따라서 우리는 가능한 모든 투어의 수업 비용에 대한 더 낮은 추정치를 얻었습니다. 즉, 이 문제의 최소 라운드 비용은 34보다 작을 수 없습니다.

전화하자 평가행렬의 (i, j) 위치에 있는 0은 i번째 행과 j번째 열에 있는 최소 요소의 합입니다(이 0 자체는 계산하지 않음). 이제 주어진 행렬의 각 0을 평가해 보겠습니다.

	1	2	3	4	5	6
1	—	0 1	0	3	3	6
2	0 1	—	1	4	1	0
3	1	2	—	0 1	0	3
4	4	5	0 1	—	1	3
5	4	2	0	1	—	0
6	7	1	3	3	0 1	—

0과 같은 점수는 보고되지 않습니다. 점수 k 0, 위치 (i, j)는 문자 그대로 다음을 의미합니다. 투어에 i에서 j까지의 경로(비용 0)가 포함되지 않은 경우 최소 k를 지불해야 합니다. 그러므로 우리는 가능한 모든 여행의 클래스를 두 가지, 즉 가장자리(i, j)를 포함하는 여행과 그것을 포함하지 않는 여행으로 나눌 수 있습니다. 후자의 경우 최소 점수는 k만큼 증가합니다.

최대 점수로 0에 해당하는 가장자리를 고려하십시오. 안에 이 경우이것이 가장자리 (1, 2)입니다. 따라서 방금 언급한 것처럼 모든 투어의 클래스는 가장자리(1, 2)를 포함하는 클래스와 이를 포함하지 않는 클래스로 나뉩니다. 두 번째 투어 클래스의 비용에 대한 하한 추정치는 35로 증가합니다. 첫 번째 투어 클래스에 대한 추정치를 결정하려면 행렬에서 행 1과 열 2를 제거합니다(이를 C [(1,2)]로 표시하겠습니다). :

행렬을 1(첫 번째 열)로 줄일 수 있으므로 가장자리(1, 2)가 있는 투어 클래스의 추정치는 1만큼 증가하여 35와 같습니다.

수업 구분과 평가 자체는 트리로 표현될 수 있습니다.

따라서 클래스(ALL)를 2개로 나누어 해당 점수를 계산하였다.

이제 점수가 가장 낮은 클래스를 선택하고 이 과정을 반복해 보겠습니다. 그런 다음 결과로 나온 두 클래스 중에서 최소 점수를 가진 클래스를 선택하여 분할합니다. 우리는 나무의 잎사귀에 도달할 때까지 이것을 반복할 것입니다. 즉, 0×0 행렬을 얻을 때까지:

C [(1, 2); [-](a 1 , b 1); [-](a 2 , b 2); … [-](ak , b k)]

여기서 (각각) −(x, y)는 행렬이 가장자리 (x, y)를 포함하지 않는 클래스에 해당함을 의미합니다. 행렬 표기법에서 −(x, y) 형식의 요소를 제거하면 다음을 얻습니다. :

(c 0 , d 0); (c1, d1); … (c n , d n)

트리의 정점 (5, 4)는 가장자리를 포함하는 클래스에 해당합니다: (1, 2); (3, 1); (6, 5); (2, 6); (4, 3); (5, 4). 이 클래스는 비용 = 36인 하나의 전체 투어(1, 2, 6, 5, 4, 3, 1)로 구성됩니다(전체 투어의 경우 최소 점수는 정확한 비용과 동일합니다).

이 결과를 기록적인 결과로 기억하고 점수가 방금 찾은 것보다 크거나 같은 모든 꼭지점을 "교차하여"(즉, 모든 클래스를 추가 고려에서 제외) 트리 위로 이동해 보겠습니다. 또한 평가에도 불구하고 해당 하위 항목이 모두 지워지더라도 꼭지점을 지울 것입니다. 우리는 다음을 얻습니다:

두 번째 열에 제공된 가장자리(1, 2)를 포함하지 않는 투어 클래스에 해당하는 행렬은 다음과 같습니다.

	1	2	3	4	5	6
1	—	—	0 3	3	3	6
2	0 1	—	1	4	1	0
3	1	1	—	0 1	0	3
4	4	4	0 1	—	1	3
5	4	1	0	1	—	0
6	7	0 1	3	3	0	—

요소 (1, 2) 대신 대시(무한 비행 비용을 나타냄)를 삽입하여 모든 투어의 클래스에 해당하는 행렬에서 얻었습니다. 저것들. 1,2 = 무한대입니다. 이를 C [-(1,2)]로 표시하겠습니다.

최대 점수 0은 3(요소 1,3)이므로 분기 −(1,3)의 점수는 38과 동일하다는 것을 얻습니다.

첫 번째 행과 첫 번째 열을 지우면 네 번째 행에서 1로 감소되는 행렬을 얻습니다. 즉, 분기 −(1,2)(1,3)의 점수는 36이 됩니다. 발견된 레코드 값(36)을 고려하여 추가 분기를 계속할 것입니다.

따라서 정점이 남아 있지 않아 검색이 완료됩니다. 그리고 그 과정에서 발견된 기록값과 해당 라운드가 문제의 해결책이다.

Little 알고리즘 및 이와 유사한 다른 알고리즘에 대한 만족스러운 이론적 추정치는 없지만 실습에 따르면 최신 기계에서는 정점 수가 100개인 여행하는 외판원 문제를 해결할 수 있습니다. 또한 분기 및 경계 알고리즘은 효과적인 경험적 절차입니다. . 완료할 수 없는 경우.

예시 2. 회로 개방 문제

회로 개방 문제에도 동일한 접근 방식을 적용할 수 있습니다. 문제의 공식화:

그래프 G = (V, E)가 주어지고 각 호 (u, v)는 양수 c (u, v) - 이 호의 가중치와 연관됩니다.

그래프(V , E 0)에 등고선이 없고 호의 가중치 합(E 0부터)이 최대가 되도록 E 0 ⊂ E를 찾아야 합니다.

방금 공식화된 것과 유사한 보조 문제((E , E *)로 나타냄)를 고려해 보겠습니다. 추가 매개변수— 호를 제거할 수 없는 집합 E * ⊂ E(이 경우 그래프(V , E *)에 윤곽선이 포함되지 않아야 함).

문제(E, E *)가 있는 경우 전체 솔루션 세트를 다음과 같이 두 클래스로 나눌 수 있습니다.

그래프 (V, E* ∪ (u, v))에 등고선이 없는 원호 (u, v) ∈ E\E*를 생각해 보세요.

그러면 문제에 대한 해결책 세트는 두 가지로 나눌 수 있습니다.

1. 문제에 대한 해결책 세트 (E \ (u, v), E *)
2. 문제에 대한 해의 집합(E , E* ∪ (u , v))

윤곽선을 여는 원래 문제는 분명히 문제입니다(E, Ø).

이제 est(E , E 0) 함수를 다음과 같이 소개하겠습니다.

1. 그래프 (V , E)에 사이클이 포함되어 있지 않으면 est(E , E 0) = 0입니다.
2. 그렇지 않으면 E cyc를 사이클로 두고: est(E , E 0) = est(E \ E cyc , E 0) + c cyc, 여기서 c cyc = min( c (u , v) | (u , v ) ∈ E cyc \ E 0 ) (즉, 이 사이클을 여는 데 사용할 수 있는 최소 무게)

그것을 보여주는 것은 쉽습니다.

V (E , E 0) ≥ est(E , E 0),

여기서 v (E, E 0)는 호 가중치의 최소 합이며 E \ E 0에서 제거하면 그래프의 모든 윤곽이 열립니다.

지역 개선 방법('지역 검색')

이 방법의 아이디어는 극단 문제 x ∈ X의 각 솔루션에 대해 가까운 솔루션 A(x)의 이웃이 결정되고 주어진 현재 솔루션 x에 대한 계산 프로세스의 각 반복에서 다음을 찾으려고 시도한다는 것입니다. 그 이웃에는 다음과 같은 솔루션이 있을 것입니다. 최고의 가치 목적함수. 그러한 솔루션을 찾을 수 있으면 해당 솔루션 자체가 현재 솔루션이 됩니다. 그렇지 않으면 검색이 종료됩니다.

좀 더 구체적으로 전략을 지역 검색이것은:

• 무작위 솔루션으로 시작
• 현재 솔루션을 개선하려면 주어진 변환 집합의 변환을 적용하세요. 이 개선된 솔루션이 현재의 솔루션이 됩니다.
• 주어진 세트의 어떤 변환도 현재 솔루션을 개선하지 않을 때까지 이 절차를 반복합니다.

주어진 변환 집합에 가능한 모든 변환(모든 솔루션에서 다른 변환을 얻을 수 있음)이 포함되어 있으면 정확한(전역적으로 최적) 솔루션을 얻을 수 있지만 이러한 알고리즘의 복잡성은 모든 솔루션을 열거하는 것보다 나을 것이 없습니다. .

실제로 정확한 해결에 기하급수적인 시간이 필요한 문제를 해결할 때 변환 세트는 제한됩니다. 이들의 도움으로 여러 임의의 솔루션에서 지역적으로 최적의 솔루션을 얻고 가장 좋은 솔루션을 선택합니다.

지역 검색 방법을 사용하여 그래프에서 최소 스패닝 트리를 찾는 정확한 알고리즘을 고려해 보겠습니다. 로컬 변환은 다음과 같습니다. 현재 스패닝 트리와 관련되지 않은 하나 또는 다른 에지를 가져와 트리에 추가한 다음(사이클을 얻음) 이 사이클에서 하나의 에지를 제거합니다(가장 높은 비용으로). 이는 트리 외부의 모든 가장자리가 최고 비용트리에 추가할 때 형성되는 루프의 모든 가장자리 중에서 (이 검사에만 O(|V||E|) 시간이 걸립니다). 이 알고리즘은 Prim과 Kruskal의 알고리즘보다 느리며 예제로 사용됩니다. 비합리적인 사용 NP-완전이 아닌 문제에 대한 지역 검색.

예제 2. 여행하는 외판원 문제(이중 선택)

대칭형 여행 외판원 문제에 사용할 수 있는 가장 간단한 변환은 소위 "이중 선택"입니다. 이는 두 개의 모서리(예: (a, b) 및 (c, d))를 선택하고 이를 삭제한 다음 이들로 연결된 점을 "재전환"하여 새로운 경로가 형성된다는 사실로 구성됩니다. 두 개의 새로운 가장자리 비용의 합이 두 개의 이전 가장자리보다 적다면 개선된 경로를 찾은 것입니다.

스패닝 트리를 구축한 동일한 그래프를 고려해 보겠습니다. (a, b, c, d, e)를 초기 경로로 선택하고 여기에 “이중 선택”을 적용해 보겠습니다. 그림 "c"에서 한 쌍의 모서리를 다른 모서리로 유리하게 교체하여 제거하는 것이 불가능하다는 것을 쉽게 확인할 수 있습니다.

이중 선택은 k-선택으로 일반화될 수 있습니다. 이 경우에는 최대 k개의 모서리를 제거하고 나머지 요소를 순서에 관계없이 "재전환"하여 경로를 얻으려고 합니다. 일반적으로 제거할 가장자리가 인접하지 않을 필요는 없습니다.

수량 확인이 쉽습니다. 다양한 변신, k 선택을 위해 고려해야 할 것은 O(|V|k)입니다. 그러나 어떤 것을 획득하는 데 필요한 시간은 최적의 경로, 훨씬 더 많은 것으로 판명 될 수 있습니다.

실제로는 "가변 깊이 선택"이 매우 효과적입니다. 최적의 경로를 제공할 가능성이 높습니다 | 뷔 | = 40 – 100.

예시 3: 블록 배치 문제

1차원 블록 배치 문제의 공식화: 무방향 그래프 G = (V, E)의 꼭지점을 모서리 c (u, v)의 가중치로 정렬하고 숫자 1 ... n으로 번호를 매겨야 합니다. ∑ i를 최소화하려면 j = 1 ... n | 나는 - j | c(vi,vj); n = | V|.

그래프의 정점은 일반적으로 "블록"이라고 하며, 가중치는 블록 사이의 "와이어" 수로 해석됩니다. 그러면 문제의 본질이 분명해집니다. 요소를 연결하는 데 필요한 와이어의 길이가 최소화되도록 요소를 직선으로 배열해야 합니다.

이는 유사한 2차원 문제와 마찬가지로 로직 보드를 연결하고 집적 회로를 만드는 데 적용됩니다.

블록 배치 문제에 대한 지역적으로 최적의 솔루션을 찾으려면 다음 지역 변환을 사용할 수 있습니다.

1. 결과 순서의 비용이 더 낮은 경우 인접한 블록 v i 및 v i +1의 상호 재배열을 수행합니다. 허락하다

   L (j) = ∑ k =1… j −1 c (v k , v j);
   R (j) = ∑ k = j +1… n c (v k , v j).

   다음과 같은 경우 개선이 가능합니다.

   L(i) − R(i) + R(i +1) − L(i +1) + 2c(vi , v i +1)< 0

2. 블록 vi를 가져와서 i와 j의 일부 값에 대해 v i와 v i +1 블록 사이에 삽입합니다.
3. 두 블록 vi와 v j의 상호 재배열을 수행합니다.

여행하는 외판원 문제와 마찬가지로 국소 최적점을 찾는 데 필요한 시간을 정확하게 추정할 수 없습니다. 우리 자신을 변환으로 제한하면 ( 1 ), O(|V|) 시간은 수행 중인 변환이 개선되는 변환인지 확인하고 L(i) 및 R(i)를 계산하는 데 충분합니다. 변환의 경우( 2 ) 그리고 ( 3 ) 이번에는 O(|V|2)로 증가합니다. 그러나 이는 각 개선이 새로운 개선의 기회를 창출할 수 있기 때문에 지역적 최적점을 찾는 데 걸리는 시간을 추정한 것이 아닙니다.

대략적인 방법과 경험적 방법

이 섹션에서는 우리에게 알려진 다항식 시간에서 작동하고 우리에게 알려진 일부 오류가 있는 "무차별 대입" 문제를 해결하는 알고리즘을 고려합니다. 대략적인 방법과 경험적 방법 사이의 경계가 모호해졌습니다. 일부에서는 오류를 조정할 수 있는 알고리즘, 즉 근사 방식을 근사 알고리즘으로 구별합니다.

경험적 방법에서는 겉보기에 자연스러워 보이는 특정 권장사항을 사용하여 의사결정 요소를 선택합니다. 선택 규칙, 휴리스틱. 종종 그러한 규칙은 선택의 탐욕 조건과 결합됩니다. 즉, 선택한 선택은 나중에 수정되지 않습니다. 더 강력한 다양성이 접근법은 분기 및 경계 방법에서 우리에게 친숙한 옵션 트리가 타당하지만 공식적으로 정당화되지 않는 일부 규칙을 기반으로 인위적으로 축소되는 축소 검색입니다.

예제 1. 여행하는 외판원 문제(나무 알고리즘)

오류가 2배(ρ = 2) 이하인 삼각형 부등식을 사용하여 대칭형 여행 외판원 문제를 해결하는 세 가지 경험적 알고리즘을 고려해 보겠습니다.

그 중 첫 번째, 소위 트리 알고리즘은 다음과 같습니다. Prim의 알고리즘을 사용하여 그래프에 대한 최소 스패닝 트리를 구축한 다음 트리를 순서대로 탐색합니다. 루트-왼쪽-오른쪽, 중복 정점을 제거합니다.

이 알고리즘의 실행 시간은 Θ(E) = Θ(V 2)입니다.

예제 1. 여행하는 외판원 문제(탐욕스러운 알고리즘과 Karg-Thompson 알고리즘)

여행하는 외판원 문제를 해결하기 위한 가장 확실한 알고리즘은 탐욕스러운 알고리즘입니다. 현재 도시에서 아직 방문하지 않은 가장 가까운 도시로 이동합니다. 삼각형 부등식이 성립한다면 이 알고리즘이 최대 두 배만큼 틀렸다는 것을 증명하는 것은 어렵지 않습니다. 이 알고리즘의 복잡도는 O(V 2)입니다.

Karg-Thompson 알고리즘(가장 가까운 지점 휴리스틱)은 다소 덜 명확합니다. 먼저 가장 가까운 두 정점(퇴화 투어)을 선택한 다음 이미 구성된 투어의 모든 가장자리에 대한 루프에서 각 가장자리(u, v)에 대해 c(u,w)+c(w,v)−c(u,v)가 최소가 되도록 자유 정점 aw에서 선택하고 u와 v 사이의 투어에 w를 포함합니다. 이 방법의 경우에도 ρ = 2이지만 복잡성은 이미 O(V 3)입니다.

예 2. 정점 커버 문제

방향이 지정되지 않은 그래프 G =(V , E)의 정점 커버는 다음 속성을 갖는 정점 V ′의 특정 패밀리입니다. 그래프 G의 모든 간선(u , v)에 대해 적어도 하나의 끝 u 또는 v는 V'에 포함됩니다. 정점 덮음의 크기는 포함된 정점의 수입니다.

정점 커버 문제는 최소 크기의 정점 커버를 찾는 것으로 구성됩니다. 이 문제는 NP-hard이지만 아래의 간단한 알고리즘은 2번 이하의 오류로 이 문제를 해결합니다.

C를 꼭짓점 덮개의 이미 구성된 부분으로 두고, E'는 그래프의 가려지지 않은 가장자리를 포함한다고 가정합니다. 각 단계에서 우리는 E'에서 모서리를 가져와 그 끝점 u와 v를 C에 추가하고 E'에서 끝점 u 또는 v가 있는 모든 모서리를 제거합니다. 그리고 집합 E'가 비워질 때까지 계속됩니다. 이 알고리즘의 실행 시간은 O(E)입니다.

이 알고리즘이 실제 알고리즘보다 두 배 이상 나쁘지 않다는 것을 증명하려면 알고리즘에 의해 선택된 두 개의 모서리에 공통 꼭지점이 없다는 점만 알아두면 충분합니다. 이는 C의 꼭지점 수가 해당 모서리 개수의 두 배라는 것을 의미합니다. . 최적의 피복에는 각각의 꼭지점이 하나 이상 포함되어 있으며 이러한 꼭지점은 모두 다릅니다.

유한 집합 X와 그 부분 집합 F가 주어졌습니다. 여기서:

X =∪ S ∈ F S

우리는 집합 X, 즉 다음과 같은 가장 작은 카디널리티의 계열 C를 함께 포함하는 F의 부분 집합의 최소 수를 찾고 있습니다.

X =∪ S ∈ C S

우리는 그러한 집합 C를 집합 X의 덮개라고 부를 것입니다. 예를 들어 그림에서 검은색 원은 집합 X의 요소이고 윤곽선은 F의 부분 집합입니다. 세 개의 밝은 실선 윤곽이 최소 적용 범위를 구성합니다. 그리디 알고리즘은 하나 이상의 카디널리티를 포함하는 적용 범위를 제공합니다(점선 윤곽도 포함).

그리디 근사 알고리즘을 사용하여 문제를 해결하겠습니다. 집합 U에는 아직 포함되지 않은 요소가 포함되고, 계열 C에는 이미 포함된 하위 집합이 포함됩니다. 각 단계에서 탐욕스러운 선택이 이루어집니다. S는 세트 커버링으로 간주됩니다. 가장 큰 수아직 다루지 않은 요소.

이는 U가 비어 있을 때까지 발생합니다. 알고리즘의 복잡도는 O(| X |·| F |·min(| X |,| F |))입니다.

이 알고리즘에 의해 제공되는 적용 범위의 크기는 가능한 최소값을 H(max(| S |: S ∈ F ))배만큼 초과합니다(여기서 H(d)는 첫 번째 d 항의 합입니다. 고조파 계열) 또는 (ln| X | + 1)배로 동일합니다.

의사다항식 알고리즘

이러한 알고리즘은 동적 프로그래밍을 적용하여 얻는 경우가 많습니다. NP-완전 문제. 이러한 알고리즘은 입력 길이에 따라 작동 시간(및 컴퓨터 메모리)이 기하급수적으로 의존하지만 문제 입력 시 특정 숫자(숫자)에 대해서는 다항식 의존성이 있습니다. 이러한 알고리즘은 작은 숫자의 문제를 정확하고 대략적으로 해결할 수 있기 때문에 매우 유용합니다. 큰 숫자, 어떻게 든 작은 것으로 변했습니다.

예 1. 부분 집합 합계 문제("표 형식" 알고리즘)

쌍 (S, t)이 주어지며, 여기서 S = ( x 1 , x 2 , …, x n )은 양의 정수 집합이고 t는 양의 정수입니다. 집합 S의 부분 집합 중에서 그 합이 t를 초과하지 않는 것 중에서 그 합이 t에 가장 가까운 것을 찾는 것이 필요합니다.

하자 | S | = 엔. (k, w)를 표시해 보겠습니다. S에서 처음 k개의 숫자가 있고 합계 w를 입력해야 하는 문제입니다. 따라서 원래 문제는 문제 (n, t)입니다.

문제를 해결하기 위해 테이블 ​​T [n, t + 1]을 작성하고 셀 T [i, j]에 문제 (i, j)에 대한 최적의 솔루션을 작성합니다.

첫 번째 열은 0으로 채워집니다. 첫 번째 줄을 먼저 0으로 채우고 셀 (1, x 1)부터 숫자 x 1로 시작하겠습니다. 다음 규칙에 따라 셀 T [i, j] (i, j > 1)를 채웁니다.

1. j − x i > 0이면 y:= T [ i − 1, j − x i ]이고, 그렇지 않으면 y:= 0;
2. T [ i , j ] := max(T [ i − 1, j ], y + x i)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
3	0	0	0	3	3	3	3	3	3	3	3	3	3	3
5	0	0	0	3	3	5	5	5	8	8	8	8	8	8
7	0	0	0	3	3	5	5	7	8	8	10	10	12	12
9	0	0	0	3	3	5	5	7	8	9	10	10	12	12
11	0	0	0	3	3	5	5	7	8	9	10	11	12	12

S = (3, 5, 7, 9, 11) t = 13;

테이블은 다음과 같습니다. 답변: 가중치가 13인 하위 집합은 없으며 아래에서 가장 가까운 하위 집합은 12입니다.

조건 (2)는 x i (T [ i − 1, j ])를 사용하지 않거나 x i 가 합 (y + x i)에 포함되어 있으면 최적의 합을 얻을 수 있음을 나타냅니다. 이 경우 조건(1)의 변수 y에 저장되는 문제(i − 1, j − x i)의 해에 추가해야 합니다. 결과 표에서 최적의 양의 구성을 확인할 수 있습니다.

이 알고리즘의 복잡성은 O(n t) 연산입니다. 따라서 t가 크면 모든 숫자를 예를 들어 10으로 나누어 반올림하여 대략적인 알고리즘을 얻을 수 있습니다.

예제 2. 부분 집합 합 문제("목록" 알고리즘)

L을 숫자 집합으로 설정하고 x를 특정 숫자로 설정한 다음 L + x로 x가 L의 모든 요소에 추가되면 얻을 수 있는 숫자 집합을 나타냅니다. 이 알고리즘은 또한 x i가 합계에 포함될 수도 있고 포함되지 않을 수도 있다는 사실을 사용합니다. 즉:

L i = L i −1 ∪ (L i −1 + x i)

목록에서 t보다 큰 요소를 제거하면 Ln을 얻습니다. 이는 우리를 만족시키는 하위 집합 S의 가능한 모든 합을 나열한 순서 목록입니다. 문제에 대한 해결책을 얻으려면 최대(마지막) 요소를 취하는 것이 남아 있습니다. 리스트 Ln은 최대 2n개의 요소를 포함할 수 있습니다(즉, 알고리즘은 지수적입니다). 모든 요소는 서로 다르므로 t개 이상이 존재할 수 없습니다. 의사다항성이 있습니다.

근접 방식

근사 알고리즘과 관련하여 다음과 같은 질문이 생깁니다. 근사 알고리즘을 점차 복잡하게 만들고 점점 더 정확한 솔루션을 얻는 것이 가능합니까? 그러한 알고리즘이 있으며 우리가 이미 말했듯이 이를 근사 방식이라고 합니다. 이는 매우 드물다는 점에 유의해야 합니다. 일반적으로 어려운 문제의 경우 정확도가 낮고 반대쪽 끝에 무차별 대입이 있고 중간에는 아무 것도 없는 알려진 간단한 알고리즘이 있습니다.

부분집합 합 문제에 대한 두 가지 근사 방식을 고려해 보겠습니다. 그 중 하나는 "목록" 알고리즘에서 나온 것이고, 다른 하나는 존슨 알고리즘이라고 합니다.

예제 1. 부분 집합 합 문제(완전 다항식 근사 방식)

이러한 방식은 목록 L이 축소된 형식으로 저장되는 경우 "목록" 알고리즘에서 얻습니다. L'이 L의 일부이고 L'의 일부인 경우 리스트 L'을 리스트 L의 δ-환원이라고 합니다.

∀ y ∈ L ∃ ​​​​z ∈ L ′: z ≤ y , (y − z) ⁄ y ≤ δ

예를 들어 δ = 0.1 및 L =<10, 11, 12, 15, 20, 21, 22, 23, 24, 29>목록 L' =<10, 12, 15, 20, 23, 29>δ-수축입니다. m개 요소의 순서 목록을 줄이려면 Θ(m) 연산이 필요합니다. 따라서 완전한 목록이 아닌 단축된 목록을 저장하는 "목록" 알고리즘은 완전한 다항식 근사 방식임을 입증할 수 있습니다.

예제 2. 부분 집합 합 문제(Johnson 알고리즘)

알고리즘은 집합 S와 숫자 t 외에도 정수 매개변수 m > 2를 입력으로 사용합니다. x i > t ⁄(m +1)인 경우 i번째 숫자를 큰 것으로 부르겠습니다. 알고리즘 설명:

1. 큰 숫자의 모든 하위 집합을 열거하고 합계가 t ′: t ′인 큰 숫자 집합을 찾습니다.< t , Δ = t − t ′ min
2. Δ = 0이면 알고리즘이 종료됩니다.
3. 모든 작은 숫자를 내림차순으로 정렬합니다. 다음 x i ≤ Δ이면 t ′:= t ′ + x i, Δ := Δ − x i;
4. 작은 숫자에 대한 검색이 완료되면 t'를 답으로 반환합니다.

k를 큰 수의 수로 둡니다. 그러면 우리에게 적합한 큰 수의 부분 집합의 개수는 O(km) ≤ O(n·m)임을 증명할 수 있습니다. 따라서 검색은 m에 따라 증가하는 다항식 복잡성을 갖습니다. 또한 다음과 같은 사실을 보여줄 수 있습니다.

T ′⁄ t ≥ 1 − 1 ⁄ (m + 1) 1 − 1 ⁄ (m + 1) ≤ t ′⁄ t* ≤ 1

즉, 상대 오차 ε = 1⁄ (m +1)입니다. 따라서 이 근사 방식은 다항식이지만 완전히 다항식은 아닙니다.

무작위 검색 방법

일반적으로 솔루션 선택은 일련의 선택으로 표현될 수 있습니다. 임의의 메커니즘을 사용하여 이러한 선택을 하면 솔루션이 매우 빨리 발견되므로 솔루션을 여러 번 찾을 수 있고 "기록", 즉 만난 최고의 솔루션을 기억할 수 있습니다. 이러한 순진한 접근 방식은 무작위 메커니즘에서 특정 선택의 전망을 고려하는 것이 가능할 때, 즉 무작위 검색을 휴리스틱 방법 및 로컬 검색 방법과 결합하는 것이 가능할 때 크게 개선됩니다. 이러한 방법은 예를 들어 Aeroflot 일정을 생성할 때 사용됩니다.

나는 정말로 그러고 싶다 추가 정보무작위 검색 방법에 대해 알아보고 구체적인 예이 방법을 사용하여 문제를 해결하려면...........

제발. 검색어 "무작위 검색 방법"의 경우 구글 검색 엔진 300,000개 이상의 링크를 발표합니다. 이 정보면 충분할텐데........

기사 감사합니다. Little의 알고리즘을 알아냈습니다. 그 사이트를 기억하고 싶었는데 모교의 도메인을 보고 깜짝 놀랐습니다 :)

전환 금지에 대해 위에서 정확하게 언급했습니다. 여기서 설명을 보고 싶습니다.

Little의 알고리즘에 대한 명확한 설명에 감사드립니다. 그러나 고려되지 않음 중요한 세부 사항: 다음 가장자리를 선택할 때 가장자리 집합의 경로가 모든 지점을 순차적으로 포함한다는 점을 고려해야 합니다. 무작위 순서로 가장자리를 추가하기 때문에 마이크로사이클의 존재를 추적해야 합니다(예를 들어 가장자리 1,0을 선택한 경우 - 이는 0, 1을 더 이상 선택할 수 없음을 의미하거나 0,1과 1을 선택한 경우, 2 - 그러면 2,0과 2,1 등을 선택할 수 없습니다. 이는 추적하기가 쉽지 않습니다. C#으로 알고리즘을 구현하고 다음을 사용하여 주기를 추적했습니다. 특별 수업에는 마이크로사이클 세트가 포함되어 있으며 새로운 것이 추가되면 금지된 가장자리가 삭제되고 가장자리가 제거되면 가장자리가 복원됩니다.

알고리즘의 구현은 실제로 매우 어려웠으며 디버깅은 그야말로 지옥이었습니다. 코드는 512줄을 사용했습니다. 0.1~10초 내에 20포인트를 처리합니다. 지속 시간은 입력 세트에 따라 크게 달라집니다. 많은 분량충분한 시간 안에 해결되지는 않습니다. 제가 가지고 있는 가장 간단한 검색 엔진은 1초 안에 13개의 꼭지점에 대한 답을 찾습니다.

C#으로 알고리즘을 구현해야 하는 경우 이메일로 문의해 주세요. [이메일 보호됨].

분기 및 경계 방법(Little의 알고리즘)을 사용하여 여행하는 외판원 문제 해결

http://igorvn.ucoz.ru/load/kursovye/kommivojazher/2-1-0-15

Little의 방법은 소수의 포인트에서만 작동하므로 모든 예에서 포인트가 10개를 넘지 않습니다. 15포인트부터 시작하면 최소값보다 1~2% 더 많은 대략적인 결과가 제공됩니다. 각 이동(축소)을 결정하는 순서는 이것이 어떤 기준으로 수행되는지 명확하지 않습니다. 결국 공식적으로 우리는 또 다른 매트릭스를 얻습니다.

내 의견을 확인하기 위해 "Russian Method"를 보내드립니다.

감사합니다. 우리는 귀하의 정직성과 역량에 대해 의심의 여지가 없습니다. 하지만 *.doc 파일은 호스팅하지 않습니다. 영구 저장 상태로 공개된 장소에 콘텐츠를 게시하고 새 댓글 텍스트에 링크를 포함하면 모든 사람이 볼 수 있도록 게시됩니다.

Little의 방법의 모든 이론적 오류에 대해 배우고 싶은 사람에게는 먼저 축소가 무엇인지, 어떤 수학적 근거로 수행되는지 설명하시기 바랍니다. 게다가 제가 개발한 러시아 방식을 완전 무료로 보내드릴 수 있습니다. 내 이메일: [이메일 보호됨]

많은 연구자들이 분기 및 경계 방법에 대한 아이디어를 얻었지만 Little et al. 지정된 방법문제 해결을 위한 성공적인 알고리즘을 개발하여 접근 방식의 대중화에 기여했습니다. 그 이후로 분기 및 바인딩 방법은 많은 문제에 성공적으로 적용되었으며 문제를 해결하기 위해 방법의 여러 가지 다른 수정 사항이 발명되었지만 대부분의 교과서는 Little의 선구적인 작업에 중점을 둡니다.

일반적인 아이디어는 간단합니다. 분류되는 수많은 옵션을 클래스로 나누고 이러한 클래스에 대한 추정값(아래에서 - 최소화 문제에서, 위에서 - 최대화 문제에서)을 얻어야 합니다. 한 번에 하나씩이 아니라 전체 수업에서 옵션을 선택할 수 있습니다. 어려운 점은 절차가 효과적인 클래스(분기)와 추정(경계)으로의 구분을 찾는 것입니다.

표 2

표 3

표 4

이전 섹션의 예제 1을 사용하여 Little의 알고리즘을 제시하겠습니다. 행렬을 다시 작성해 보겠습니다.

Cij를 도시 i에서 도시 j까지의 여행 비용으로 해석하는 것이 더 편리할 것입니다. j 도시의 시장이 도시에 들어오는 외판원에게 5달러를 지불하라는 법령을 내렸다고 가정해 보겠습니다. 이는 모든 투어가 도시 j에 들어가야 하기 때문에 모든 투어가 5달러만큼 저렴해진다는 것을 의미합니다. 하지만 모든 투어의 가격이 균일하게 하락했기 때문에 이전 최소 투어의 비용이 이제 가장 저렴해집니다. 시장의 선행은 행렬 C의 j번째 열의 모든 숫자가 5만큼 감소한 것으로 나타낼 수 있습니다. 시장이 여행하는 판매원을 j번째 도시에서 멀리 보내고 보상을 설정하기를 원했다면 10달러의 금액은 모든 요소에서 10을 빼서 표현할 수 있습니다. jth 그윤곽. 이렇게 하면 각 투어의 비용이 다시 변경되지만 최소 투어는 최소로 유지됩니다. 따라서 다음 정리가 증명되었습니다.

행렬 C의 모든 행이나 열의 모든 요소에서 상수를 빼서 최소 투어를 최소값으로 남겨둡니다.

알고리즘의 경우 다음을 얻는 것이 편리할 것입니다. 더 많은 0그러나 행렬 C에서는 수신하지 않고 음수. 이를 위해 각 행에서 최소 요소를 뺍니다(행 감소라고 함, 표 3 참조). 그런 다음 행 방향 행렬의 각 열에서 최소 요소를 빼서 열 방향 감소 행렬을 얻습니다. 표 참조 . 4).

대각선 대시는 도시 i에서 도시 i까지 걸어갈 수 없음을 의미합니다. 행의 감소 상수의 합은 27, 열의 합은 7, 합의 합은 34입니다.

예를 들어 표에 표시된 것처럼 투어는 행렬 C의 밑줄이 그어진(다른 색상으로 강조 표시된) 6개 요소의 시스템으로 정의될 수 있습니다. 2. 요소에 밑줄을 긋는 것은 라운드에서 해당 요소가 i번째 요소에서 j번째 요소로 이동한다는 것을 의미합니다. 6개 도시 투어에는 6개의 밑줄이 그어진 요소가 있어야 합니다. 6개 도시 투어에는 6개의 모서리가 있기 때문입니다. 각 열에는 정확히 하나의 밑줄이 그어진 요소(여행하는 판매원이 각 도시에 한 번 들어옴)가 포함되어야 하며, 각 행에는 정확히 하나의 밑줄이 그어진 요소가 포함되어야 합니다(여행하는 판매원은 각 도시를 한 번 떠났습니다). 또한 밑줄 친 요소는 여러 개의 작은 주기가 아닌 단일 라운드를 설명해야 합니다. 밑줄 친 항목의 개수의 합이 투어 비용입니다. 책상 위에 2 비용은 36이며, 이는 사전식 검색으로 얻은 최소 라운드입니다.

이제 우리는 표에 주어진 행렬을 토대로 추론해 보겠습니다. 2. 구축이 가능한 경우 올바른 시스템밑줄 친 요소, 즉 위에서 설명한 세 가지 요구 사항을 충족하는 시스템이고 밑줄 친 요소는 0일 뿐이므로 이 매트릭스에 대해 최소 투어를 얻을 수 있다는 것이 분명합니다. 그러나 원래 행렬 C의 경우에도 최소값이 됩니다. 정확한 투어 비용을 얻으려면 모든 감소 상수를 다시 추가해야 하며 투어 비용은 0에서 34로 변경됩니다. 따라서 최소 투어는 34보다 작을 수 없습니다. 모든 라운드에서 낮은 평가를 받았습니다.

이제 분기를 시작하겠습니다. 이를 위해 0을 추정하는 단계를 수행합니다. 축소 행렬의 셀 (1,2)에 있는 0을 고려합니다. 즉, 도시 1에서 도시 2로 이동하는 데 드는 비용이 0이라는 뜻입니다. 도시 1에서 도시 2로 가지 않으면 어떻게 될까요? 그런 다음 두 번째 열에 표시된 가격에 대해 도시 2를 입력해야 합니다. 단 1명에 대해 더 저렴합니다(6번 도시에서 출발). 다음으로, 첫 번째 줄에 표시된 가격으로 도시 1을 떠나야 합니다. 가장 저렴한 옵션은 0을 위해 도시 3으로 가는 것입니다. 이 두 가지 최소값을 합산하면 1+0=1이 됩니다. 도시 1에서 도시 2로 "0"으로 가지 않으면 최소한 1을 지불해야 합니다. . 이것은 0의 추정치입니다. 모든 0의 추정치는 표에 나와 있습니다. 5 오른쪽 및 0 위(0과 동일한 0점은 제공되지 않음).

이러한 추정치 중 최대값을 선택해 보겠습니다(예제에는 여러 추정치가 있습니다. 1과 같다, 셀 (1,2)에서 첫 번째 항목을 선택합니다.

따라서 제로 에지(1,2)가 선택됩니다. 모든 둘러보기를 가장자리(1,2)를 포함하는 클래스와 가장자리(1,2)를 포함하지 않는 클래스의 두 가지 클래스로 나누어 보겠습니다. 두 번째 클래스의 경우 1을 더 지불해야 한다고 말할 수 있으므로 이 클래스의 투어 비용은 35 이상입니다.

첫 번째 클래스에 대해서는 표의 행렬을 고려해야 합니다. 6 첫 번째 줄과 두 번째 열은 지워졌습니다.

표 5

표 7

또한 축소된 행렬에서는 셀 (2,1)에 금지 사항이 있습니다. 가장자리(1,2)가 선택되었으며 가장자리(2,1)를 사용하여 둘러보기를 조기에 종료하는 것은 불가능합니다. 축소된 행렬은 첫 번째 열에서 1씩 줄어들 수 있으므로 해당 행렬에 해당하는 각 라운드의 비용은 최소 35입니다. 분기 및 추정값 획득 결과는 그림 1에 나와 있습니다. 6.

원은 클래스를 나타냅니다. 위쪽 원은 모든 라운드의 클래스입니다. 왼쪽 아래 - 가장자리(1,2)를 포함한 모든 투어의 클래스; 오른쪽 아래 - 가장자리(1,2)를 포함하지 않는 모든 투어의 클래스입니다. 원 위의 숫자는 아래에서 추정한 수치입니다.

계속해서 분기해 나가자 긍정적인 측면: 왼쪽 - 아래. 이를 위해 표의 축소 행렬 C에서 0을 추정합니다. 7. 셀 (3,1)의 최대 점수는 3입니다. 따라서 그림의 오른쪽 아래 정점에 대한 점수는 다음과 같습니다. 7은 35+3=38입니다. 그림의 왼쪽 하단 꼭지점을 평가하려면 7에서는 행렬 C에서 또 다른 행 3과 열 1을 삭제하여 테이블에서 행렬 C[(1,2), (3,1)]를 얻어야 합니다. 8. 이 매트릭스에서는 투어의 조각이 이미 가장자리 (1,2)와 (3,1)에서 구성되었으므로 셀 (2,3)에 금지를 설정해야 합니다. , 조기 폐쇄는 금지되어야 합니다(2.3). 이 행렬은 1열씩 주어지므로(표 9), 해당 클래스의 각 투어(즉, 가장자리 (1,2)와 (3,1)을 포함하는 투어)의 비용은 36 이상입니다.

표 9

표 11

이제 주어진 행렬 C[(1,2), (3,1)]에서 0을 평가합니다. 최대 점수가 3인 0은 셀 (6,5)에 있습니다. 부정적인 옵션의 점수는 38+3=41입니다. 긍정적인 옵션에 대한 평가를 얻으려면 6행과 5열을 제거하고 셀 (5,6)에 금지를 입력하십시오. 표를 참조하십시오. 10. 이 행렬은 환원불가능하다. 결과적으로 포지티브 옵션의 점수는 증가하지 않습니다(그림 8).

표의 행렬에서 0을 평가합니다. 10, 우리는 가장자리 선택(2,6)에 따라 분기를 얻고, 부정적인 옵션은 36+3=39의 점수를 얻고, 긍정적인 옵션에 대한 점수를 얻기 위해 두 번째 행과 여섯 번째 열을 지웁니다. 테이블에서 행렬을 가져옵니다. 열하나.

투어의 일부가 이미 구성되었으며 조기 복귀가 금지되어야 하기 때문에(5.3) 셀(5.3)의 매트릭스에 금지를 추가해야 합니다. 이제 대각선 제한이 있는 2x2 행렬이 남았으므로 가장자리 (4,3) 및 (5,4)로 둘러보기를 완료합니다. 우리가 긍정적인 옵션으로 확장한 것은 헛되지 않았습니다. 이제 우리는 비용이 36인 1>2>6>5>4>3>1 투어를 받았습니다. 검색 트리의 맨 아래에 도달하면 투어 클래스가 하나의 투어로 좁혀졌고 추정치는 다음과 같습니다. 아래는 정확한 비용으로 변환되었습니다.

따라서 36점 이상의 모든 수업은 최고의 여행포함하지 마십시오. 따라서 해당 꼭지점은 지워집니다. 두 자손이 모두 삭제된 정점도 삭제됩니다. 우리는 전체 검색을 엄청나게 줄였습니다. 행렬 C에 해당하는 클래스에 더 나은 둘러보기가 포함되어 있지 않은지 확인하는 것이 남아 있습니다. 셀 1,2에 금지가 있는 행렬 C가 주어지면 열에서 1만큼 감소합니다(점수 34+1=35 제공). 0의 평가는 셀(1,3)의 0에 대해 3을 제공하므로 음수 옵션 35+3의 평가는 이미 수신된 라운드 36의 값을 초과하고 음수 옵션은 차단됩니다.

포지티브 옵션의 추정치를 얻기 위해 행렬에서 첫 번째 행과 세 번째 열을 제외하고 금지(3.1)를 설정하고 행렬을 얻습니다. 이 행렬은 네 번째 행에 1로 주어지며, 클래스 점수는 36에 도달하고 원은 지워집니다. 정점 "모두"의 두 자식이 모두 죽기 때문에 그 정점도 죽습니다. 정점이 남아 있지 않아 검색이 끝났습니다. 우리는 표에 밑줄이 그어진 것과 동일한 최소 투어를 받았습니다. 2.

Little 알고리즘의 성능에 대한 만족스러운 이론적 추정과 관련 알고리즘아니요, 하지만 연습에 따르면 현대 컴퓨터 n = 100인 문제를 해결할 수 있는 경우가 많습니다. 이는 이전에 비해 엄청난 개선입니다. 전체 검색. 또한 분기 및 경계와 같은 알고리즘은 완료할 수 없는 경우 효과적인 휴리스틱 절차입니다.