Cvičení 13: Grafy

Úloha 1: Nejkratší cesta v grafu

Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány ve speciálním souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:

první číslo je číslo uzlu ze kterého vede hrana
druhé číslo je číslo uzlu do kterého vede tato hrana

Napište program path.py, který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.

Program otestujte na tomto souboru:

Výsledek pro cestu z uzlu 2 do uzlu 5 je:

2 6 9 5

Řešení problémů

nadoby = list(map(int, input().split()))
x = int(input())

o=[[0,0,0,'']]
c=[]
end = False

def konec(s):
    end = False
    for i in range(3):
        if s[i]==x:
            end = True
    return end

def stejny(a,b):
    return a[:3]==b[:3] 

def novy(s):
    ret = True
    for x in o:
        if stejny(s,x):
            ret = False
            break
    if ret:
      for x in c:
        if stejny(s,x):
            ret = False
            break
    return ret

while len(o)>0 and not end:
    s = o.pop(0)
    c.append(s)
    print('Stav',s)
    for i in range(3):
        if s[i]<nadoby[i]:   
            s_n = s[:]
            s_n[i]=nadoby[i]
            s_n[3]+='N'+str(i)+'\n'
            if konec(s_n):
                print(s_n[3])
                end=True
                break
            if novy(s_n):
                o.append(s_n)
            
    for i in range(3):
        if (not end)and s[i]>0:   
            s_n = s[:]
            s_n[i]=0
            s_n[3]+='V'+str(i)+'\n'
            if konec(s_n):
                print(s_n[3])
                end=True
                break
            if novy(s_n):
                o.append(s_n)

    for i in range(3):
        if not end:
          for j in range(3):
            if (j!=i) and s[i]>0 and s[j]<nadoby[j]:
                s_n = s[:]
                if (s[i]<=(nadoby[j]-s[j])):
                   s_n[i]=0
                   s_n[j]+=s[i]
                else:
                   s_n[i]-=(nadoby[j]-s[j])
                   s_n[j]=nadoby[j]
                s_n[3]+=str(i)+'P'+str(j)+'\n'
                if konec(s_n):
                    print(s_n[3])
                    end=True
                    break
                if novy(s_n):
                    o.append(s_n)
if not end:
    print("Nelze vyresit")

def spravne(a):
    ret = True
    for i in range(len(a)-1):
        roz = len(a)-1-i
        if (a[i]-a[-1])==roz or (a[-1]-a[i])==roz:
            ret = False
            break
    return ret

def kralovny(hotovo, neumistene):
    print('s:',hotovo, neumistene)
    if len(neumistene)==0:
        return(hotovo)
    else:
        vysl = []
        for i in range(len(neumistene)):
            hotovo2 = [x for x in hotovo]
            neumistene2 = [x for x in neumistene]
            hotovo2.append(neumistene[i])
            if spravne(hotovo2):
                neumistene2.pop(i)
                vysl = kralovny(hotovo2,neumistene2)
                if (len(vysl)>0):
                    break
        return vysl

print(kralovny([], [0,1,2,3,4,5,6,7]))

def spravne(a):
    ret = True
    for i in range(len(a)-1):
        roz = len(a)-1-i
        if (a[i]-a[-1])==roz or (a[-1]-a[i])==roz:
            ret = False
            break
    return ret

def kralovny(hotovo, neumistene, res):
    print('s:',hotovo, neumistene)
    if len(neumistene)==0:
        res.append(hotovo)
        return []
    else:
        vysl = []
        for i in range(len(neumistene)):
            hotovo2 = [x for x in hotovo]
            neumistene2 = [x for x in neumistene]
            hotovo2.append(neumistene[i])
            if spravne(hotovo2):
                neumistene2.pop(i)
                vysl = kralovny(hotovo2,neumistene2, res)
                if (len(vysl)>0):
                    break
        return vysl
a=[]
kralovny([], [0,1,2,3,4,5,6,7], a)
print(a)

maxVolumes = [5,3,5]
 
class State:
    def __init__(self,v):
        self.v = v[:]
        self.act = ""
        self.prev = None
    def __repr__(self):
        return str(self.v) + self.act
 
    def expand(self):
        newStates=[]
        #Ni nalit
        for i in range(len(self.v)):
            if self.v[i] == maxVolumes[i]:
                continue
            tmp = State(self.v)
            tmp.v[i] = maxVolumes[i]
            tmp.act = "N{}".format(i)
            newStates.append(tmp)
 
 
        #Vi vylit
        for i in range(len(self.v)):
            if self.v[i] > 0:
                tmp = State(self.v)
                tmp.v[i] = 0
                tmp.act = "V{}".format(i)
                newStates.append(tmp)
 
        #iPj prelit z i do j
        for i in range(len(self.v)):
            for j in range(len(self.v)):
                if i != j and self.v[i] >0 and self.v[j] != maxVolumes[j]:
                    tmp = State(self.v)
                    rest = maxVolumes[j] - self.v[j]
                    if self.v[i] > rest:
                        tmp.v[i] -= rest
                        tmp.v[j] += rest
                    else:
                        tmp.v[j] += self.v[i]
                        tmp.v[i] = 0
                    tmp.act = "{}P{}".format(i,j)
                    newStates.append(tmp)
        return newStates
 
start = State([5,0,0])
states = start.expand()
print(states)
 
goal = [2,0,8]
 
openList = []
openList.append( start )
isInOpen = {}
 
while openList:
    actual = openList.pop(0)
    print(actual)
    if actual.v[2] % 3 == 0 and actual.v[2] > 0:
        print("Huarra")
        while actual != None:
            print(actual)
            actual = actual.prev
 
        break
 
    states = actual.expand()
 
    for state in states:
        if not str(state.v) in isInOpen:
            state.prev = actual
            openList.append(state)
            isInOpen[ str(state.v) ] = 1

class Person:
    def __init__(self, name, sex):
        self.name = name
        self.sex = sex   
        self.children = []  
        self.parents = []   # parents of this node
        self.partner = None   # partner (=husband/wife of this node)
 
    def add_child(self, node):
        self.children.append(node)
 
    def add_parent(self, node):
        self.parents.append(node)
 
    def set_partner(self, node):
        self.partner = node
 
    def __str__(self):
        s = "Female" if self.sex == 'F' else "Male" 
        return self.name + " " + s
 
 
def findPerson(name, family):
    for person in family:
        if person.name == name:
            return person
    return None
 
 
def load(filename):
    f = open(filename,"r")
    family = []  #array of ref of Person
    for line in f:
        typ, name1, name2, sex1, sex2 = line.strip().split()
 
        p1 = findPerson(name1, family)
        if p1 == None:
            p1 = Person(name1, sex1)
            family.append(p1)
 
        p2 = findPerson(name2, family)
        if p2 == None:
            p2 = Person(name2, sex2)
            family.append(p2)  
 
        if typ == 'M':
            p1.set_partner(p2)
            p2.set_partner(p1)
        elif typ == 'P':  #name1 is parent of name2
            p1.add_child(p2)
            p2.add_parent(p1)
    f.close()
    return family
 
family = load('family.txt')
for person in family:
    print("Person is", person, "partner is", person.partner)

Table of Contents

Cvičení 13: Grafy

Úloha 1: Nejkratší cesta v grafu

Řešení problémů