Fórum studentů MFF UK

banejee píše:Heuristika najbližšieho bodu
Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy.

banejee píše:povedzme ze z v do u nevedie hrana a existuje cesta v -> z -> u (nech je najkratsia).. vytvorime hranu medzi v a u o velkosti (v,z) + (z,u)

banejee píše:.. dame jeden bod do cyklu.. ale dalsie body len napajame.. ako to moze byt cyklus..
..museli by sme ho napojit so zaciatocnym aj koncovym bodom.. budeme body len napajat k jednemu koncovemu bodu a na konci nam zostane posledny bod.. nemoze sa stat, ze z neho nebude viest hrana k jednemu z koncovych bodov?

Tuetschek píše:

Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.

Aha ... ja jsem to ale pochopil tak, ze p a q se lisi od sqrt(n) max. o 1 bit svou delkou ... tohle si myslim, ze neco takoveho nema moc sanci nastat .

Osiris píše:Díky. No, myslím to úplně jednoduše takhle: vezmeš si binární zápis odmocniny z n. Dále uděláš množinu A = {x | x se liší v maximálně jednom bitě}. Tu zkonstruuji tak, že si vezmu ten binární zápis odmocniny z n a postupně zneguju každý bit toho binárního zápisu a zařazuji to do A. Je jisté, že p,q leží v A. Velikost A je log_2(sqrt(n)) + 1. Udělám si kartézský součin A x A, a pro každé (a,b) v A x A otestuji, zda a*b = n. Pak p = a a q = b.

Tuetschek píše:Osiris: myslim, ze mas pravdu, s tim konceptem ... ze Hricovi fakt jde o to, kolik MUSIM vyzkouset, tj. minimalni pocet ... protoze jinak bych si mohl vymyslet libovolne hodne velke cislo a nejaky algoritmus by se uz vzdycky nasel ... ale ten tvuj algoritmus jsem z toho taky nepobral. Co je "prehazovat bit"?