====== 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:
1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1
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]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]
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)