특정 항목이 포함 된 최소 체인을 찾는 알고리즘 탐색

Question

죄송합니다. 다음 알고리즘에 대한 알고리즘 또는 문제 이름을 생각해 낼 수 없습니다. 나는 문제를 진술하고 내가 시도한 것과 누군가가 올바른 방향으로 나를 가리킬 수있을 것이다.

항목이 들어 있다고 가정하십시오 (순서가 지정되지 않았거나 중복 허용됨). 실제로이 가방은 이완이 도움이 될 경우 2 ~ 20 개의 품목을 포함 할 수 있습니다.

목표는 모든 순서로 가방의 모든 항목을 포함하는 최소 길이 체인 (체인의 다른 개념이있는 경우 정렬 링크 목록)을 찾는 것입니다.

체인은 시작 토큰 (가방에 존재하지 않음)과 그 뒤에 항목 수가 많으며 끝 토큰 (가방에도 없음)으로 구성됩니다.

체인은 n-tuples (순서가 중요 함)를 연결하여 형성되며, 더 긴장을 풀기 위해 n 값이 모든 튜플에 대해 동일하다고 가정합시다. 실제로, n = 3으로 작업하고 있습니다. 겹치는 요소가있는 경우 연결되는 것과는 대조적으로 체인이 "혼합"될 수 있습니다. 예를 들어, (a, b, c)와 (c, d, e)를 고려하십시오. 는 (a, b, c, d, e)와 같이 결합 될 수 있습니다. 마찬가지로 (a, b, c)와 (b, c, d)는 (a, b, c, d)로 결합 될 수 있습니다. 일부 튜플은 첫 번째 위치에서 시작 토큰을 가질 수 있으며 일부 토큰은 마지막 위치에서 최종 토큰을 가지므로 물론 문제의 해결 방법이 될 수 있습니다.

그래서이 문제에 대한 정확한 해결책은 일반적으로 다루기가 쉽지 않은 것처럼 보입니다. 어떤 종류의 최적화 알고리즘은 문제에 "좋은"해결책을 얻기 위해 필요할 것입니다. 내가 살 수있는 "좋은"해결책.

내가 처음 시작한 것은 욕심 많은 접근법으로 첫 번째 단계에서 가방의 요소 수가 가장 많은 튜플을 임의로 끊는 방식입니다. 지금까지 구축 한 체인을 보유하는 데이터 구조를 만들고 선택한 데이터 구조를이 데이터 구조에 고정하십시오. 문제를 2 개의 하위 문제, 즉 시작 토큰 쪽과 끝 토큰 쪽으로 나눕니다. 하위 문제 1의 데이터 구조의 첫 번째 토큰이 시작 토큰이고 하위 문제 2의 마지막 토큰이 최종 토큰이 될 때까지 가능한 한 빨리 중지 조건을 찾기 위해 체인을 확장합니다 (시작 또는 종료 토큰에 따라 다름). 하위 문제에 대해) 가능한 한 빨리 가방의 내용물을 배출하려고합니다. 각 하위 문제는 가방에 몇 개의 항목이 포함되어야하는지에 대해 서로 통신해야하기 때문에 좋지 않을 수 있습니다.

누구나 어디에서이 문제가 발생 했습니까? 이 알고리즘을 개선하는 방법 (또는 올바르게 작동시키는 방법)에 대한 생각은 무엇입니까? 이것은 내가 더 큰 시스템의 현명한 부분이며 장난감 문제 또는 숙제 문제가 아닌 문제를 다루는 실제 문제입니다.

편집

죄송합니다 모두 내가 컴퓨터에서 멀리 오늘이었다. 나는보기에는 너무 복잡하지는 않지만 사소한 예제 솔루션을 게시하려고 노력할 것입니다.

/ = Start Token

\ = End Token

3 튜플

1. Bag = {A, B, C, D}
   (나는 그것을 예를 위해서 세트를 만들지 만, 각 항목은 한 번 이상 나타날 수 있습니다) :

   을 감안할 때 (트리플) : 이름을 붙일 때 간단하게하기 위해 라벨을 붙인다. 소문자는 문제의 실제 기능이 없습니다.

   (/,A, E) a 
   (/,C, D) b 
   (/,G, H) c 
   (D,B, A) d 
   (C,G, H) e 
   (B,A, \) f 
   (G,H, \) g 
   

해결책 : 우리가 함께 체인 경우 B, D 및 F 우리 (/,C,D,B,A,\)을 얻는다.
시작 및 끝 토큰을 모두 계산할 경우 길이가 6 인 bag의 모든 요소를 ​​포함하는 가능한 최단 체인입니다. 일반적으로 최단 경로 길이는 | BAG | + 2, 실제로 존재하는 경우. 내 문제 성명서가 더 이해되기를 바랍니다.

Answer 1

최대 20 개 항목 만 가지고 있으므로 합리적인 시간 (예 : 1 분 미만)에서 정확한 해결책을 계산할 수 있다고 생각합니다.

한 가지 방법 상태에 의해 주어진다 동적 프로그래밍을 사용하는 것입니다 :???? 시작처럼 보이는 체인에 해당한다

A) a 20 bit number m (which will represent which items have been visited so far) 
B) a number b in the range 1..20 
C) a number c in the range 1..20 

이 상태,,,, ..., B ,기음. , 즉 b와 c는 가장 최근의 두 요소입니다.

숫자 m은 체인에서 방문한 다른 요소를 나타내는 비트 필드입니다. 즉 체인이 i 번째 요소를 가방에 포함하는 경우에만 m의 비트 i는 1입니다.

알고리즘

가장 짧은 체인이 다음이 될 것입니다 확인하는 방법은 다음과 같습니다

1. 하자 시작 토큰이있는 모든 튜플로 구성된 상태 S = 세트. (이 모든 상태는 동일한 체인 길이 2를 가짐)
2. 체인 길이 y가 3 이상인 경우 S의 모든 상태를 거쳐 적절한 길이의 튜플을 사용하여 길이를 늘려보십시오. 이것이 가능하면 확장 상태를 추가하여 S를 설정하십시오.
3. 비트 필드 m이 모든 비트 세트로 끝날 경우에만 끝 토큰이있는 튜플을 추가 할 수 있습니다.

끝 상태를 포함하는 튜플을 추가로 관리하는 경우 모든 요소가 포함 된 최단 체인을 찾았습니다.

가방의 N 개 항목에는 약 2^N.N 개의 상태가 있습니다. 관리가 용이해야합니다.