오브젝트의 최적의 배치는 pairwise 유사 가중치를 사용합니다.

Question

Ok 이것은 추상적 인 알고리즘 적 과제이며, 그것을 사용하려고하는 일급 비밀이기 때문에 추상적으로 남아 있습니다.

O = {o_1, ..., o_N}의 객체 집합과 S_ij가 객체 o_i와 o_j의 쌍으로의 상관 관계 인 대칭성 유사도 행렬 S가 있다고 가정합니다.

개체가 놓일 수있는 개별 위치가있는 1 차원 공간이 있다고 가정합니다 (행에 N 개의 상자가 있거나 사용자를 위해 의자가있는 것처럼).

특정 배치를 가지고 우리는 한 목표물의 위치에서 다른 대상체의 위치로 이동하는 비용을 우리가 목표물에 도달 할 때까지 통과해야하는 상자의 수로 측정하여 쌍의 개체 유사성을 곱할 수 있습니다. 그 위치 직전 또는 직전에 위치에서 상자로 이동하는 것은 비용이 들지 않습니다.

세 개체에 대해 우리는 다음과 같은 유사성 행렬 어디로 예를 상상해 : 나무 상자에서 객체의 가장 좋은 순서 분명히 그런

 1.0 0.5 0.8 

S = 0.5 1.0 0.1 

    0.8 0.1 1.0 

입니다 :

[o_3] [o_1] [o_2] 

비용 이 순서는 한 객체에서 다른 객체로 이동하는 데 필요한 비용의 합계입니다. 한편

[o_3] [o_1] [o_2] 

:

[o_1] [o_2] [o_3] 

비용을 것 = 비용 그래서 여기에 우리는 o_2 및 1BOX * 0.1sim = 0.1, 같은 동일한 o_3 사이의 거리에 대한 비용이있다 (o_1 -> o_3) = 1box * 0.8sim = 0.8.

---

대상 우리가 객체의 모든 가능한 쌍에 대한 위에서 언급 한 전체 비용을 최소화하는 방법으로 사용할 수있는 위치에있는 N 객체의 위치를 ​​결정하는 것입니다!

analogue은 테이블과 의자가 하나의 행 (상자와 같은)에 나란히 서 있고 N 명의 의자에 앉아 있어야한다고 상상하는 것입니다. 이제 그 사람들은 몇 가지 관계를 가지고 있습니다. 즉, 그들 중 한 사람이 다른 사람과 이야기하기를 원할 가능성이 얼마나 높습니다. 이것은 여러 개의 의자에 의해 일어 서서 그 사람에게 이야기하는 것입니다. 사람들이 두 개의 연속적인 의자에 앉으면 서로 이야기하기 위해 움직일 필요가 없습니다.

그래서 어떻게하면 두 개 ppl 사이의 모든 거리 - 비용이 최소화되도록 이들 ppl을 줄일 수 있습니까? 즉, 밤에는 손님이 걸어 다니는 총 거리가 최소 가까이에 있음을 의미합니다.

탐욕스러운 검색은 ... 좋습니다. 잊어 버리십시오! 나는 몇몇 문학을 찾을 수있는 그런 문제의 표준 공식이 있고, 다른 검색 접근법 (예 : 동적 프로그래밍, 금기 검색, 조합 최적화 분야의 시뮬레이션 어닐링 등)이 있다면 듣고 싶다.

앞으로 귀하의 아이디어를 듣고 싶습니다.

추신.제 질문은이 스레드와 공통점이 있습니다 Algorithm for ordering a list of Objects,하지만 여기서는 문제가 더 좋고 아마 약간 다를 것이라고 생각합니다.

Answer 1

(내 자신의) 스레드에 단순한 정렬 방식을 도우겠습니다.

1. 유사성 매트릭스의 위쪽 절반을 주문하십시오.
2. 유사 가중치가 가장 높은 오브젝트 쌍으로 시작하여 가운데 위치에 놓습니다.

3. 다음 객체는 왼쪽이나 오른쪽에 놓을 수 있습니다. 그래서 왼쪽 또는 오른쪽에 놓을 때 객체를 선택할 때마다 은 미리 배치 된 객체에 대해 가장 많은 비용을 부담합니다. 고토 2 단계

이 객체를 떠나 나중에 배치하면이 비용이되기 때문에 3 단계의 선택은 남아있는, 그리고 (더 사전 배치 개체)보다의 다시 큰 . 비용이 많이 드는 게재 위치는 될 수있는 한 빨리 완료해야합니다.

이것은 너무 간단하며 좋은 해결책을 발견하지 못합니다.

완전한 순서는 "스왑"의를 사용하여 개선

2. 시도 (임의 또는 다른 알고리즘에서) 어떻게 든 생성과이

1. 시작하는 또 다른 방법 개체 쌍.

저는 로컬 미니 마가 큰 제지가 될 것이라고 생각합니다.

Answer 2

다음은 이미 게시 된 방법의 변형입니다. 나는 이것이 최적이라고 생각하지 않지만 시작일 수 있습니다.

Create a list of all the pairs in descending cost order. 
While list not empty: 
    Pop the head item from the list. 
    If neither element is in an existing group, create a new group containing 
    the pair. 
    If one element is in an existing group, add the other element to whichever 
    end puts it closer to the group member. 
    If both elements are in existing groups, combine them so as to minimize 
    the distance between the pair. 

그룹은 그룹의 순서 역전이 필요할 수 조합, 데이터 구조 것을 지원하도록 설계되어야한다.

Answer 3

두 번째 할당 문제의 인스턴스처럼 들립니다. 이 전문 분야는 위치가 한 줄로 만 배치되어 있기 때문에 가능하지만 해결하기가 쉽지 않을 것입니다. 일반적으로 QAP는 NP 하드입니다. 내가 문제를 잘못 해석하지 않으면 P = NP를 동시에 입증하지 않고 다항식 시간에 문제를 해결하는 최적의 알고리즘을 찾을 수 없습니다.

인스턴스가 작 으면 분기 및 바인딩과 같은 정확한 방법을 사용할 수 있습니다. 문제가 더 어려울 경우 금기 검색이나 다른 메타 이론을 사용할 수도 있습니다. HeuristicLab에는 QAP 및 일부 메타에 대한 구현이 있습니다. GUI에서 문제를 구성하고 유사성과 거리 행렬을 적절한 매개 변수에 붙여 넣기 만하면됩니다. 강력한 금기 검색으로 시작하십시오. 그것은 오래된 알고리즘이지만 여전히 잘 작동하는 알고리즘입니다. Taillard는 자신을 위해 구현하려는 경우 자신의 웹 사이트에 C 코드도 있습니다. 구현은 해당 코드를 기반으로합니다.

QAP에서 많은 출판이 이루어졌습니다.보다 현대적인 알고리즘은 유전 검색 능력을 지역 검색 휴리스틱 스 (예 : Stützle IIRC의 Genetic Local Search)와 결합시킨다.