Dva problema: lepo risanje grafov in pokrivanje točk s premicami

author: Janez Brank, Condensed Matter Physics, Jožef Stefan Institute
published: Feb. 25, 2007,   recorded: April 2004,   views: 106

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Bibliography

Description

Risanje grafov kot optimizacijski problem Recimo, da bi radi graf narisali tako, da bi posameznim vozliščem grafa priredili neke točke v ravnini, povezave pa bi potem predstavili z daljicami med temi točkami. Kako izbrati koordinate točk? Eden od načinov je, da definiramo neko funkcijo, ki poskusa na podlagi koordinat oceniti videz narisanega grafa, in potem izberemo koordinate tako, da je vrednost te funkcije čim manjsa. Predstavil bom funkcijo, ki sta jo predlagala Davidson in Harel leta 1996 in se se kar dobro obnese na majhnih grafih. Onadva sta jo minimizirala s simuliranim ohlajanjem, jaz pa sem jo poskusil malo predelati, da je postala odvedljiva, in sem jo minimiziral z gradientnim spuscanjem. Pokrivanje točk s premicami Mislimo si optimizacijski problem, pri katerem je dana množica točk v ravnini, mi pa bi radi izbrali neko množico premic, tako da bo vsaka točka ležala na vsaj eni od teh premic in da bo število premic čim manjše. Izkaže se, da je ta problem NP-težak, lahko pa poskusimo s požresnim algoritmom priti do približnih (čeprav ne optimalnih) rešitev. Predstavil bom nekaj razpostavitev točk, pri katerih se požresni algoritem odreže še posebej slabo.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: