translacja z pythona na c++

0

Witam,
Mam kod Pythonie. Ze względu na szybkość działania chciałbym go przepisać w C++. Niestety słabo znam ten język i ciężko zrobić mi translację. Jężeli jest ktoś w stanie i pomóc to z góry dziękuję.

poniżej fragmenty kodu:

def value(path, graph):
  #Dla danej listy wierzcholkow i grafu zwraca dlugosc cyklu opisanego przez liste
  psum = 0
  for i in range(len(path)):
    psum += graph[path[i]][path[(i+1)%len(path)]]
  return psum

def random_perm(lst):
  #Zwraca losowa permutacje ciagu
  random.shuffle(lst)
  return lst

def unify(seq):
  #Unifikuje liste
  seq.sort()
  return list(seq for seq,_ in itertools.groupby(seq))

def all_combinations(items, n):
  #Generator kombinacji n-elementowych listy items
  if n==0: yield []
  else:
    for i in xrange(len(items)):
      for cc in combinations(items[i+1:],n-1):
        yield [items[i]]+cc

def combinations(items, n):
  #Zwraca liste wszystkich n-elementowych kombinacji listy items
  sols = []
  for cc in all_combinations(items, n):
    sols.append(cc)
  return sols

def newRefSet(newSols, graph, b):
  #Metoda wywolujaca metode proprawy, zwracajaca b najlepszych rozwiazan z newSols
  newSols = improve(newSols, graph)
  newSols.sort(key=lambda s:value(s,graph))
  if len(newSols) < b:
    return newSols
  else:
    return newSols[:b]
0

Tak, ten Python to zły jest. Ale zdajesz sobie sprawę że sam twój algorytm ma w_cholerę_dużą_złożoność?

combinations (O(n)) wywołuje metodę all_combinations (O(n^2)) która wywołuje... combinations. Strzelam że złożoność wynosi (O(n!)) (czyli raczej optymalne dla algorytmu zwracającego wszystkie kombinacje), więc dla
n=25 masz 15511210043330985984000000 przejść,
n=50 - 3,0414093201713378043612608166065e+64,
n=1000 - 4,02387260077093773543702433923e+2567 przejść pętli. Powodzenia.

0

Niestety wiem, że ma dużą złozoność. Cały szkopuł polega na tym że python ze wzgledu na szybkość nie nadaje się rozwiązywania problemu komiwojażera. Zapuścilem na kompie i liczył całą noc:( Kod który chcę przetłumaczyć wykorzystuje algorytm scattersearcha do rozwiązywania problemu komiwojażera.

1 użytkowników online, w tym zalogowanych: 0, gości: 1