PEG Online Judge Coding

Question

Ich löse ein Problem mit dem PEG Online Judge, welches eine Seite ist, wo man viele Probleme für Übung und Spaß lösen kann.

Ich habe Probleme mit einem besonders. Ich habe dort Hilfe geschrieben, bekomme aber keine.

Es ist das Problem Caporegime: http://wcipeg.com/problem/capos

Sie können eine Reihe von Sprachen verwenden, um dies zu lösen. Ich habe mich für Python entschieden (obwohl ich es auch in C++ programmiert habe). Es gibt 12 Datensätze, die der Richter beim Testen des Codes verwendet. Mein Code besteht 11/12. Ich habe keine Ahnung, warum ich den letzten Test nicht bestehen kann und hoffe, dass mir jemand helfen kann.

Ich denke, es ist ein Set-Partitionierungsproblem irgendeiner Art und ich löse es mit einem breiten ersten Suchansatz. Die Problem-Datasets sind nicht groß, so dass es nicht aus dem Ruder läuft.

Hier ist meine Lösung:

import sys 
import copy 

class SearchState(): 
    def __init__(self, label, crews): 
     self.label = label 
     self.crews = crews 

    def __repr__(self): 
     return "State: %s: %s" % (self.label, str(self.crews)) 


def crewsSoldierCanBeIn(s, crews, grudges): 
    ''' 
     For a given soldier and a list of crews and grudges, 
     return the crews the soldier an go in 
    ''' 

    noGrudgeCrews = [] 
    for i, crew in enumerate(crews): 
     conflict = False 
     for c in crew: 
      if [s, c] in grudges or [c, s] in grudges: 
       conflict = True 
       break 
     if not conflict: 
      noGrudgeCrews.append(i) 

    return noGrudgeCrews  


def solve(numSoldiers, grudges): 
    ''' 
     Put each soldier in a crew, output min no. of crews and who is in them 
    ''' 

    crews = [[1]] 
    numStates = 0 
    states = [SearchState(numStates, crews)] 

    for s in range(2, numSoldiers+1): 
     newStates = [] 
     for state in states: 
      possibleCrews = crewsSoldierCanBeIn(s, state.crews, grudges) 
      if len(possibleCrews) > 0: 
       for crew in possibleCrews: 
        numStates += 1 
        newCrews = copy.deepcopy(state.crews) 
        newCrews[crew].append(s) 
        newStates.append(SearchState(numStates, newCrews)) 
      else: 
       numStates += 1 
       newCrews = copy.deepcopy(state.crews) 
       newCrews.append([s]) 
       newStates.append(SearchState(numStates, newCrews)) 

     states = copy.deepcopy(newStates) 


    minNumCrews = 1000000 
    minState = -1 
    for i, state in enumerate(states): 
     if len(state.crews) < minNumCrews: 
      minNumCrews = len(state.crews) 
      minState = i 


    print(len(states[minState].crews)) 
    for crew in states[minState].crews: 
     for s in crew: 
      print("%d " % (s), end = "") 
     print() 

def readInData(f): 

    numSoldiers, numGrudges = map(int, f.readline().strip().split()) 
    grudges = [] 
    for _ in range(numGrudges): 
     grudges.append(list(map(int, f.readline().strip().split()))) 

    return numSoldiers, grudges 


def main(): 

    # Read in the data 
    f = sys.stdin 

    numSoldiers, grudges = readInData(f) 

    solve(numSoldiers, grudges) 

if __name__ == '__main__': 
    main() 

Answer 1

Ok, also habe ich das endlich gelöst.

Grundsätzlich musste ich einen DFS-Ansatz verwenden, er kann nicht wirklich (mit dem Online-Judge-Speicher und den Zeitbeschränkungen) über BFS gelöst werden.

Der Vorteil von DFS ist zweifach: 1) Ich kann ziemlich schnell eine Lösung (nicht die beste Lösung) erreichen und benutze diese, um den Baum zu beschneiden, um Haufen von Teillösungen loszuwerden, die niemals gut sein werden und 2) Sehr wenig Speicher wird benötigt.

So DFS ist schneller und verwendet weniger Speicher für dieses Problem.