{"id":6146,"date":"2009-04-08T10:09:51","date_gmt":"2009-04-08T07:09:51","guid":{"rendered":"http:\/\/studentpmr.ru\/?p=6146"},"modified":"2009-04-08T10:09:51","modified_gmt":"2009-04-08T07:09:51","slug":"%d0%bc%d0%b5%d1%82%d0%be%d0%b4-%d1%84%d0%be%d1%80%d0%b4%d0%b0","status":"publish","type":"post","link":"http:\/\/studentpmr.ru\/?p=6146","title":{"rendered":"\u041c\u0435\u0442\u043e\u0434 \u0424\u043e\u0440\u0434\u0430"},"content":{"rendered":"<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0441\u0435\u0442\u044c G=(I,U) \u0431\u0435\u0437 \u043a\u043e\u043d\u0442\u0443\u0440\u043e\u0432, \u0441 \u043e\u0434\u043d\u0438\u043c \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c s \u0438 \u0441\u0442\u043e\u043a\u043e\u043c t. \u0427\u0438\u0441\u043b\u0430 \u043d\u0430 \u0434\u0443\u0433\u0430\u0445 l<sub>ij<\/sub> \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0442 \u0438\u0445 \u0434\u043b\u0438\u043d\u0443. \u043d\u0430\u0439\u0434\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0443 \u0442.\u0435. \u0432\u0435\u0440\u0448\u0438\u043d\u0435 1 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0435\u0442\u043a\u0443 \u0415<sub>1<\/sub>=0, \u0447\u0438\u0441\u043b\u043e 0 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u044d\u0442\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u0412\u0435\u0440\u0448\u0438\u043d\u0435 2 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0435\u0442\u043a\u0443 \u0415<sub>2<\/sub>=\u0415<sub>1<\/sub>+l<sub>12<\/sub> . \u0414\u0430\u043b\u0435\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c 3,4,\u2026,n \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0443:<\/p>\n<p>\u0415<sub>j<\/sub>=min(E<sub>i<\/sub>+l<sub>ij<\/sub>), j=3,4,\u2026,n <\/p>\n<p> <!--more-->  <\/p>\n<p>{(i,j)} <\/p>\n<p>{(i,j)}- \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0434\u0443\u0433 (i,j), \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 j. \u0427\u0438\u0441\u043b\u043e E<sub>j<\/sub> \u0440\u0430\u0432\u043d\u043e \u0434\u043b\u0438\u043d\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b s \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b j.<\/p>\n<p>\u041f\u043e\u043c\u0435\u0447\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u0434\u043e\u0439\u0434\u0435\u043c \u0434\u043e \u0441\u0442\u043e\u043a\u0430. \u041c\u0435\u0442\u043a\u0430 E<sub>t<\/sub> \u0438 \u0431\u0443\u0434\u0435\u0442 \u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c \u0434\u043b\u0438\u043d\u0443 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430 \u0434\u043e \u0441\u0442\u043e\u043a\u0430.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u0432 \u0441\u0435\u0442\u0438 \u043d\u0430\u0434\u043e \u043d\u0430\u0439\u0442\u0438 \u0434\u043b\u0438\u043d\u0443 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0443\u0442\u0438, \u0442\u043e \u043f\u043e\u043c\u0435\u0442\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d 1 \u0438 2 \u0440\u0430\u0441\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u0430 \u043c\u0435\u0442\u043a\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043d\u0430\u0445\u043e\u0434\u044f\u0442 \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>\u0415<sub>j<\/sub>=max(E<sub>i<\/sub>+l<sub>ij<\/sub>), j=3,4,\u2026,n <\/p>\n<p>{(i,j)}<\/p>\n<p>\u041d\u0430\u0439\u0434\u0435\u043c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430: <\/p>\n<p>\u0415<sub>2<\/sub>=E<sub>1<\/sub>+l<sub>12<\/sub>=0+1=1<\/p>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0432 \u043f\u043e\u043c\u0435\u0442\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441\u043e \u0432\u0442\u043e\u0440\u043e\u0439, \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u043c\u0435\u0447\u0430\u0442\u044c * \u0434\u0443\u0433\u0443, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0412 \u0441\u0430\u043c\u043e\u043c \u043d\u0430\u0447\u0430\u043b\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u043e\u043c\u0435\u0447\u0430\u0435\u043c * \u0434\u0443\u0433\u0443(1,2).<\/p>\n<p>\u0415<sub>3<\/sub>=min(0+2;1+3)=2 \u041c\u0435\u0442\u0438\u043c * \u0434\u0443\u0433\u0443 (1,3) \u0442\u0430\u043a \u043a\u0430\u043a \u044d\u0442\u043e\u0439 \u0434\u0443\u0433\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 min.<\/p>\n<p>\u0415<sub>4<\/sub>=min(1+5;2+5)=6 \u041c\u0435\u0442\u0438\u043c * \u0434\u0443\u0433\u0443 (2,4) \u0442\u0430\u043a \u043a\u0430\u043a \u044d\u0442\u043e\u0439 \u0434\u0443\u0433\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 min.<\/p>\n<p>\u0415<sub>5<\/sub>=min(2+12;6+7)=6 \u041c\u0435\u0442\u0438\u043c * \u0434\u0443\u0433\u0443 (4,5) \u0442\u0430\u043a \u043a\u0430\u043a \u044d\u0442\u043e\u0439 \u0434\u0443\u0433\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 min.<\/p>\n<p>\u0415<sub>6<\/sub>=min(1+6;13+3)=7 \u041c\u0435\u0442\u0438\u043c * \u0434\u0443\u0433\u0443 (4,6) \u0442\u0430\u043a \u043a\u0430\u043a \u044d\u0442\u043e\u0439 \u0434\u0443\u0433\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 min.<\/p>\n<p>\u0414\u043b\u0438\u043d\u0430 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438 \u043e\u0442 1 \u0434\u043e 6 \u0440\u0430\u0432\u043d\u0430:<\/p>\n<p>l<sub>min<\/sub>=E<sub>6<\/sub>=7<\/p>\n<p>\u0421\u0430\u043c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043d\u0430\u0439\u0434\u0435\u043c \u0434\u0432\u0438\u0433\u0430\u044f\u0441\u044c \u0441 \u043a\u043e\u043d\u0446\u0430 \u0433\u0440\u0430\u0444\u0438\u043a\u0430: \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b 6 \u043a \u043d\u0430\u0447\u0430\u043b\u0443 \u0433\u0440\u0430\u0444\u0438\u043a\u0430 \u2013 \u043a \u0432\u0435\u0440\u0448\u0438\u043d\u0435 1 \u0432\u0434\u043e\u043b\u044c \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u043d\u044b\u0445 * \u0434\u0443\u0433 \u0432 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438, \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u043e\u043c \u0438\u0445 \u043e\u0440\u0438\u0435\u043d\u0442\u0430\u0446\u0438\u0438.<\/p>\n<p>l<sub>min<\/sub>=(1,2,4,6)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0441\u0435\u0442\u044c G=(I,U) \u0431\u0435\u0437 \u043a\u043e\u043d\u0442\u0443\u0440\u043e\u0432, \u0441 \u043e\u0434\u043d\u0438\u043c \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c s \u0438 \u0441\u0442\u043e\u043a\u043e\u043c t. \u0427\u0438\u0441\u043b\u0430 \u043d\u0430 \u0434\u0443\u0433\u0430\u0445 lij \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0442 \u0438\u0445 \u0434\u043b\u0438\u043d\u0443. \u043d\u0430\u0439\u0434\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0443 \u0442.\u0435. \u0432\u0435\u0440\u0448\u0438\u043d\u0435 1 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0435\u0442\u043a\u0443 \u04151=0, \u0447\u0438\u0441\u043b\u043e 0 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u044d\u0442\u043e \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0434\u043e \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430. \u0412\u0435\u0440\u0448\u0438\u043d\u0435 2 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u043c \u043c\u0435\u0442\u043a\u0443 \u04152=\u04151+l12 . \u0414\u0430\u043b\u0435\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043a\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c 3,4,\u2026,n \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0443: \u0415j=min(Ei+lij), <a class=\"readmore\" href=\"http:\/\/studentpmr.ru\/?p=6146\">\u0427\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043b\u0435\u0435<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41],"tags":[],"_links":{"self":[{"href":"http:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts\/6146"}],"collection":[{"href":"http:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6146"}],"version-history":[{"count":0,"href":"http:\/\/studentpmr.ru\/index.php?rest_route=\/wp\/v2\/posts\/6146\/revisions"}],"wp:attachment":[{"href":"http:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6146"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/studentpmr.ru\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}