지수 시간 코드를 빠르게하는 방법

Question

나는 시뮬레이션을 작성 중이다. 해결해야 할 문제는 다음과 같습니다.

길이가 l 인 임의의 이진 벡터 t (파이썬 목록)이 제공됩니다. 그런 다음 동일한 길이의 이진 벡터를 샘플링하고 샘플링 된 각 벡터와 t 사이의 해밍 거리 (정렬 된 불일치 수)를 측정하고 결과를 저장합니다. 나는 길이 l의 얼마나 많은 이진 벡터가 지금까지 발견 된 거리와 호환되는지를 알고 싶다. 분명히 t이지만 많은 다른 사람들도 그렇습니다.

내 코드는 다음과 같습니다.

import random 
import itertools 
import operator 

l=23 
t = [random.randint(0,1) for b in range(l)] 
stringsleft = set(itertools.product([0,1],repeat=l)) 

xcoords = [] 
ycoords = [] 
iters = l 
for i in xrange(iters): 
    print i, len(stringsleft) 
    xcoords.append(i) 
    ycoords.append(math.log(len(stringsleft))) 
    pattern = [random.randint(0,1) for b in range(l)] 
    distance = sum(itertools.imap(operator.ne, pattern, t)) 
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if sum(itertools.imap(operator.ne, pattern, y)) == distance])) 

는 불행하게도 매우 느리고 메모리를 많이 사용하고 나는 그것을 l=30 사건을 해결하기 위해 속도를 높일 수 있나요 (30)에 L이 증가하면 전혀 작동하지 않는 이유는 무엇입니까?

업데이트 그래서 지금은 l=26으로 실행 정수하여 목록을 대체하여 작은 최적화했다.

l=26 
t = random.randint(0,2**l) 
stringsleft = set(range(2**l)) 
xcoords = [] 
ycoords = [] 
iters = l 
for i in xrange(iters): 
    print i, len(stringsleft) 
    if (len(stringsleft) > 1): 
     xcoords.append(i) 
     ycoords.append(math.log(len(stringsleft),2)) 
    pattern = random.randint(0,2**l) 
    distance = bin(pattern^t).count('1') 
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if bin(pattern^y).count('1') == distance])) 

내가 l=30에 도착하는 것을 멈추게하는 문제는 시간보다는 RAM 사용법입니다.

Answer 1

나는 이것에 대해 계속 생각해 봤고, 결국 내가 쓴 프로그램은 기본적으로 Sneftel의 방법이다. 처음에는 선택을하지 않고 해밍 거리의 목록을 가지고 있습니다. 그런 다음 첫 번째 값으로 1을 선택한다고 가정하면 나머지 시퀀스가 ​​해밍 거리와 호환되면 0 만있는 모든 시퀀스는 호환됩니다. 1. 1과 동일합니다.

나는 처음에는 재귀 버전을 사용했지만 스택을 사용하여 루프로 변경하여 yield을 사용하여 호환 시퀀스를 생성하는 생성기로 사용할 수있었습니다.

하나의 최적화는 해밍 거리> l/2라고 추측하면 0과 1을 뒤집어 새로운 추측이 해밍 ​​거리가 < = l/2임을 보장합니다.

l = 30 인 경우 성능이 좋아 지지만, 추측 횟수와 운이 얼마나 좋은지에 따라 다릅니다.

나의 초기 기안자 생각 때문에, 나는 '추측'의 관점에서 '순서'를 알아 내려고합니다.

코드 : 당신은 N^2이 아닌 더 최적화 된 알고리즘을 찾을 필요가

import random 

LENGTH = 30 
NUMGUESSES = 20 


def guess(): 
    return [random.randint(0, 1) for i in range(LENGTH)] 

SEQUENCE = guess() 
GUESSES = [guess() for i in range(NUMGUESSES)] 


def hamming(a, b): 
    return sum(aelem != belem for aelem, belem in zip(a, b)) 


# Flip if hamming > LENGTH/2 
mid = LENGTH/2 
for i in range(NUMGUESSES): 
    if hamming(SEQUENCE, GUESSES[i]) > mid: 
     GUESSES[i] = [1 - g for g in GUESSES[i]] 

HAMMINGS = [hamming(SEQUENCE, g) for g in GUESSES] 

print "Sequence:", SEQUENCE 
print 
for h, g in zip(HAMMINGS, GUESSES): 
    print "Guess and hamming:", g, h 
print 


def compatible_sequences(guesses, hammings): 
    # Use a stack instead of recursion, so we can make this a generator. 
    stack = [] 
    # Start: we have chosen nothing yet, and the hammings have start values 
    stack.append(([], hammings)) 

    while stack: 
     so_far, hammingsleft = stack.pop() 

     if -1 in hammingsleft: 
      # Skip, choices so far are incompatible with the guesses 
      continue 

     if len(so_far) == LENGTH: 
      # Success if all the Hamming distances were exactly correct 
      if all(h == 0 for h in hammingsleft): 
       yield so_far 
      continue 

     # Not done yet, add choices 0 and 1 to the queue 
     place_in_guess = len(so_far) 
     for choice in (1, 0): 
      stack.append(
       (so_far + [choice], 
       [h - (g[place_in_guess] != choice) 
        for h, g in zip(hammingsleft, guesses)])) 

print "Compatible sequences:" 
for nr, sequence in enumerate(compatible_sequences(GUESSES, HAMMINGS), 1): 
    print nr, sequence 

Answer 2

편집 : 틀렸어. Mastermind에서는 올바른 색상의 수를 알고 있지만 올바른 색상은 아닙니다. 그로 인해 가능한 해결책의 수가 달라 지므로 두 문제 사이에 확실한 정확한 번역이 없으므로 아래에서 결론을 내릴 수 없습니다. 지금 당장 답을 남겨주세요. 어쩌면 누군가가 그 문제에 대해 생각하는 데 도움이 될 것입니다.

나는 대답했다 :

나쁜 소식은, 적어도 NP 완성이다.

문제는 나를 게임 Mastermind (Wikipedia) 나에게 상기시켰다. 이 페이지에는 "Mastermind satisfiability problem"에 대한 언급이 있습니다. 두 가지 색상의 Mastermind 추측 및 답변 세트가 주어지면 올바른 추측이 가능한가?

이 문제는 귀하보다 약간 더 많은 정보가 있습니다 : Mastermind는 정확한 위치의 색상을 정돈하고 (== 길이에서 해몬드 거리 빼기) 잘못된 위치에 정확한 색상의 개수를 더한 다음 가능성의 수가 0보다 큰지를 결정하려고합니다. this paper

Answer 3

여기에서 역 추적 알고리즘이 작동 할 수 있습니다. 상태는 (부분) 벡터 및 각 예제 벡터의 나머지 해밍 거리입니다. 상태가 주어지면 0을 추가하고 각 벡터의 해밍 거리를 줄입니다. 저것은 1을 가졌습니다. 그 자리에. 거리가 0 이하로 떨어지면 해결책은 용납되지 않습니다. 그렇지 않으면 재발합니다. 그런 다음 1을 사용하여 동일한 작업을 수행합니다. 벡터가 완성되면 모든 거리가 0이면 출력합니다.

이것은 여전히 ​​지수 적 시간이지만 상당히 빨라야합니다.