Bu probleme ornek var mi?
Probleme profosyonel yaklasilmis gibi durmuyor. Problemin sunumundan ve mevcut koddan, herhangi bir bilgisayar bilimcisinin veya programcinin problemi ele almadigi gorulebiliyor.
Aldiklarinda problemin ve cozumlerin cok hizli bir sekilde form degistirdigini, basitlestigini gorebileceksiniz.
import itertools
kumeler = [
[[ 9,6,9,9,7,7,], "cift"],
[[ 9,9,6,6,9,9,7,10,], "tek"],
[[ 9,9,9,11,7,], "cift"],
[[ 7,9,9,9,7,9,9,10,10,], "cift"],
[[ 4,14,4,14,10,14,13,14,13,], "cift"],
[[ 14,13,14,13,10,14,13,13,], "cift"],
[[ 6,4,6,6,5,14,], "tek"],
[[ 8,14,8,5,4,14,13,], "tek"],
]
def simple_solve(kumeler):
variables = list(sorted(set().union(*[k[0] for k in kumeler])))
best_solution = (None, -1)
for p in itertools.product((0, 1), repeat=len(variables)):
mapping = { v: s for v, s in zip(variables, p) }
sat = lambda row: sum(mapping[n] for n in row[0]) % 2 == (0 if row[1] == 'cift' else 1)
score = sum([sat(row) for row in kumeler])
if score > best_solution[1]:
best_solution = (mapping, score)
return best_solution
sol = simple_solve(kumeler)
print({ n: "P" if s else "N" for n, s in sol[0].items() }, sol[1])
{4: ‘N’, 5: ‘P’, 6: ‘N’, 7: ‘P’, 8: ‘N’, 9: ‘N’, 10: ‘N’, 11: ‘P’, 13: ‘N’, 14: ‘N’} 8
Haklısınız konuyu ele alanlar açısından epey bir sorun var. Problem için size örnek küme verebilirim:
kume_1 = [[ 14,13,14,13,14,7,], “tek”]
kume_2 = [[ 10,13,4,10,13,12,13,7,15,], “cift”]
kume_3 = [[ 14,12,14,13,14,12,3,14,7,], “tek”]
kume_4 = [[ 13,10,13,13,14,13,14,7,], “tek”]
kume_5 = [[ 2,17,16,8,], “tek”]
kume_6 = [[ 15,8,2,15,16,8,], “tek”]
kume_7 = [[ 15,14,13,15,14,13,5,15,], “tek”]
kume_8 = [[ 13,15,13,5,], “cift”]
kume_9 = [[ 18,7,19,18,7,11,6,6,19,], “tek”]
kume_10 = [[ 17,11,17,11,6,26,18,19,19,], “tek”]
kume_11 = [[ 22,18,7,22,19,28,23,], “tek”]
kume_12 = [[ 17,11,26,27,22,26,18,], “tek”]
kume_13 = [[ 12,12,21,13,32,29,], “cift”]
kume_14 = [[ 25,12,21,25,12,21,20,12,30,31,25,30,], “tek”]
kume_15 = [[ 29,12,29,32,30,32,], “tek”]
kume_16 = [[ 30,25,12,21,30,31,30,29,30,31,25,], “tek”]
kume_17 = [[ 14,19,14,14,12,30,31,], “cift”]
kume_18 = [[ 14,13,14,21,19,14,13,14,13,32,30,29,32,], “cift”]
kume_19 = [[ 28,23,14,28,23,22,27,28,27,30,], “tek”]
kume_20 = [[ 26,27,22,14,13,14,26,27,22,26,27,32,30,29,], “cift”]
kume_21 = [[ 15,29,15,15,14,13,33,34,30,29,33,29,], “cift”]
kume_22 = [[ 28,24,13,29,], “cift”]
kume_23 = [[ 32,30,15,32,30,29,34,33,33,34,30,29,], “tek”]
kume_24 = [[ 31,30,29,31,30,29,30,33,32,29,], “cift”]
kume_25 = [[ 27,28,27,29,30,29,27,28,27,28,23,33,], “tek”]
kume_26 = [[ 26,27,33,29,26,27,26,27,22,34,32,33,34,33,], “cift”]
kume_27 = [[ 33,32,26,27,33,32,31,30,29,32,31,34,34,32,], “tek”]
kume_28 = [[ 34,33,27,28,27,34,33,32,30,35,32,], “tek”]
Mesela yukarıdaki 28’ li kümeyi koda ekleyip çalıştırın, saatler geçiyor ama bitmiyor. Deneyebilirsiniz.
Fikir olarak şu geldi aklıma. Tek olan ve eleman sayısı en düşük olandan başlamak gerekiyor gibi. Önce kume_5 elemanlarına bakılmalı. Her değişimde en az bozulum bulunmalı vs vs.
Mesela 2 yi a yaparsak kume5 ve kume6 düzeliyor. Başka da kimse etkilenmiyor gibi.
kumeler = [
[[ 14,13,14,13,14,7,], "tek"],
[[ 10,13,4,10,13,12,13,7,15,], "cift"],
[[ 14,12,14,13,14,12,3,14,7,], "tek"],
[[ 13,10,13,13,14,13,14,7,], "tek"],
[[ 2,17,16,8,], "tek"],
[[ 15,8,2,15,16,8,], "tek"],
[[ 15,14,13,15,14,13,5,15,], "tek"],
# [[ 13,15,13,5,], "cift"],
[[ 18,7,19,18,7,11,6,6,19,], "tek"],
[[ 17,11,17,11,6,26,18,19,19,], "tek"],
[[ 22,18,7,22,19,28,23,], "tek"],
[[ 17,11,26,27,22,26,18,], "tek"],
[[ 12,12,21,13,32,29,], "cift"],
[[ 25,12,21,25,12,21,20,12,30,31,25,30,], "tek"],
[[ 29,12,29,32,30,32,], "tek"],
[[ 30,25,12,21,30,31,30,29,30,31,25,], "tek"],
[[ 14,19,14,14,12,30,31,], "cift"],
[[ 14,13,14,21,19,14,13,14,13,32,30,29,32,], "cift"],
[[ 28,23,14,28,23,22,27,28,27,30,], "tek"],
[[ 26,27,22,14,13,14,26,27,22,26,27,32,30,29,], "cift"],
[[ 15,29,15,15,14,13,33,34,30,29,33,29,], "cift"],
[[ 28,24,13,29,], "cift"],
[[ 32,30,15,32,30,29,34,33,33,34,30,29,], "tek"],
[[ 31,30,29,31,30,29,30,33,32,29,], "cift"],
[[ 27,28,27,29,30,29,27,28,27,28,23,33,], "tek"],
[[ 26,27,33,29,26,27,26,27,22,34,32,33,34,33,], "cift"],
[[ 33,32,26,27,33,32,31,30,29,32,31,34,34,32,], "tek"],
[[ 34,33,27,28,27,34,33,32,30,35,32,], "tek"],
]
def backtracking_solve(kumeler):
simplify_variables = lambda vs: [v for v in set(vs) if vs.count(v) % 2 == 1]
simplify_parity = lambda p: 1 if p == 'tek' else 0
kumeler = [(simplify_variables(vs), simplify_parity(p)) for vs, p in kumeler]
def solve(kumeler, assignments):
nextvar = None
for row in kumeler:
rowsum = 0
for var in row[0]:
if var in assignments:
rowsum += assignments[var]
else:
nextvar = var
break
if nextvar is None:
if rowsum % 2 != row[1]:
return None
else:
break
if nextvar is None:
return assignments
if s1 := solve(kumeler, assignments | {nextvar: False}):
return s1
elif s2 := solve(kumeler, assignments | {nextvar: True}):
return s2
else:
return None
return solve(kumeler, {})
print(backtracking_solve(kumeler))
15 == 5 ile cozum bulamadim