jaanos
commented
5 years ago Osnovni pristop je seveda ta, da se domneva preizkusi na vseh majhnih grafih, kot sta @jonagricar in @tjasamehle naredili v funkciji testiranje_hipoteze. Seveda pa ni verjetno, da bi se tam našel kak protiprimer, sicer domneva ne bi bila niti postavljena. Vseeno pa seveda to velja preveriti.
Single trajectory (ali single-solution) in population-based sta dve vrsti metahevristik, ki jih lahko uporabite. Morda lahko za začetek generirate nekaj naključnih grafov na izbranem številu vozlišč (v Sage imate razne funkcije, ki začnejo z graphs.Random - morda najbolj splošna je graphs.RandomGNP, ki ji podaste želeno število vozlišč in verjetnost, da bosta dve vozlišči povezani) in preverite, kateri izmed njih se najbolj približajo enakosti v neenačbi (če niso slučajno že sami protiprimeri). Ti grafi vam lahko služijo kot začetna populacija, potem pa z izbrano metahevristiko iz njih generirate nove grafe.
Pri genetskih algoritmih lahko tako grafe križate (npr. dva grafa razdelite na dva dela, potem pa povežete en del enega grafa z drugim delom drugega grafa) ali mutirate (naredite manjšo spremembo, npr. dodaste ali odstranite eno povezavo). Tako dobite nove grafe, ki bodo skupaj s starimi sestavljali novo populacijo - iz nje pa potem odstranite "najslabše" primerke (torej tiste, ki bodo imeli veliko odstopanje v neenakosti - npr. tako, da bo velikost populacije vsakič enaka kot velikost začetne populacije). Postopek ustavite, ko bodisi najdete protiprimer, ali pa se populacija neha izboljševati.
Svetujem sicer, da se skupaj s @katjamarina in @sdekanovic glede metahevristik zglasite pri prof. Škrekovskem, pa se boste pomenili, katere metahevristike bi bile najbolj primerne.
Mimogrede, če slučajno naletite na kak protiprimer G, potem v Sage-u napišite
G.sparse6_string()Izpisal se bo niz znakov, ki predstavlja graf (če ga daste kot parameter v Graph, bo to konstruiralo tak graf). Ta niz nam pošljite, da bomo imeli dokumentiran protiprimer.
Pozdravljeni, lažje in hitreje bo, če vam pišem kar tukaj. S @tjasamehle nimava nobene ideje glede tega, kako se lotiti problema iskanja protiprimera - podobno težavo imata tudi @katjamarina in @sdekanovic. Ali za to iskanje obstaja kakšna posebna metoda ali funkcija? Na uvodni uri ste omenili metaheuristic in single trajectory, vendar nam ni jasno, kako naj bi to izgledalo oziroma kaj to sploh pomeni, zato bi potrebovali vašo pomoč. Hvala že vnaprej in lep pozdrav!