close

Вход

Забыли?

вход по аккаунту

?

kursovaya(59)

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????? ??????????????? ?????????? ??????????????? ??????????
??????? ????????????????? ???????????
"????? ??????????? ???????????"
????????? ?????????????? ????????????
????????????? ??????? ? ???????? ?????? ?? ?????????? "?????? ???????????":
"????????? ?????????? ???????????? ????? ? ?????, ????????? ???????? ? ?????????"
????????: ______________?.?. ??????
(???????)??. ?????? ?-11
????????:______________?.?. ???????
(???????) ????. ???. ???
??????????
???????? ........................................................................... 3
1. ????????????? ?????.................................................................... 4
2. ???????? ????????? ??????. ????-?????......................................... 8
3. ??????? ??????? ?????................................................................ 10
?????? ???????????? ??????????.................................................. 14
????????
? ???????? ?????? ???????????? ??????????? ????????? ?????????? ???????????? ????? ? ?????, ????????? ???????? ? ?????????.
???????? "??????????? ????" ????????? ?? ?????? "???????????? ???????????" ???????????? ?????????? ??????????? ???????? ??????????? ? 1859 ????. ????? ????, ????? ?? ???????? ??????? ?????, ?????? ??? ??? ??????? ? ????????? ? ???????? ?????. ???? ??????????? ????? ??????? ??????????, ?????? ?? 20 ?????? ????? ???? ????????? ???????? ???????? ?????? ????.
1.????????????? ?????
???? ???? ????? ??????? ????, ?????????? ??? ??????? ????? ?? ?????? ????, ?? ????? ???? ?????????? ????????????? ??????, ? ???? ?????????? ????????????? ??????. ????, ??????? ???????? ??????? ????, ?????????? ????? ?????? ??? ???????, ?????????? ?????????????????. ??? ??????????? ????? ?????????????? ?? ??????????????? ?????, ???? ???? ??????? ???????????????. ??????????? ???? ?? ??????????? ???????? ??? ????? ?????. ????, ??? ????????????? ????? ???? ?????? ??????? ???? ?, ??? ?????? ??????????? ???? ???????? ?????????????????. ???????, ??? ??????????? ???? ?????????? ?????? ?? ? ?????? ?????.
????? ???? G ????? ?????????? ? ??????????? ????, ??????? ??????????? ?????????? ??????. ??? ?????, ????????, ?????????? ? ???????? v1,...,vp ????? G ???????? ??????? u1,...,up ? ????????? ????? {(vi,ui)} {(ui,vi+1)}. ???????? ??????? v ?????????? ????? ????? d(v), ??????????? ??, ??? ???? ????? ??????????? ??????. ? ?????? ???????????????? ????? ????????? ??????? do(v) ?? ????????? ????? ? di(v)- ?? ????????.
?????????? ????????? ??????????? ??????? ????????????? ????????????? ?????? ? ?????. ??-??????, ?????? ?????? ???? ???????? ?????????????. ?????????????, ?? ???????? ????? ??????? ????, ???????? ??????????? ??? ??????? ??????? ?????. ??-??????, ???? ????, ?????? ???????? ?????, ??????????? ????? ??? ??? ???????, ???????? ? ?????? ?????, ?? ?? ????? ???????? ?????????????.
??????? (???????????) ???? ??????? ???????? ?????? (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). ???????, ??? ???? ???? ????? ???? ??????????? ????, ?? ?? ????? ????? ? ?????? ???????????? ?????.
???? ??????????? ???? ?????????? ? ??? ????? ???????? ?????? ???, ??? ?????????? ??????? ???????, ?? ????? ???? ????????????? ?? ????????, ????????? ?? ???????? ???????? ?????, ??????????? ????? ??? ??????? ?????.
?? ???????? ????????????? ? ????, ?????????????? ????? ??????? ???? ? "????????????", ?? ??????? ??????????? ???? ??? ????????? ??????.
??????? (?????, 1952) 1. ???? ? ??????? ????? ? n > 3 ????????? p(v) > n/2 ??? ????? ??????? v, ?? ???? G ???????? ?????????????. ?????????. ?????????? ????????? ????????????? ???? ?????? ????????? ???????, ????? ?? ???????? ?????????????? ?. ??. ???????.
??????????????. ??????? ? ?????? ????? k ????? ??????, ???????? ?????? ?? ??? ? ?????? ???????? ?? G. ????? ????????????, ??? k -- ?????????? ????? ??????, ??????????? ??? ????, ????? ?????????? ???? G ???? ?????????????. ?????, ??????, ??? k > 0, ?????? ? ????????????.
????? v>p>w>...>v ??????????? ???? ? ????? G, ??? v, w-- ??????? ?? G, ? p-- ???? ?? ????? ??????. ????? w ?? ???????? ??????? ? v, ??? ??? ? ????????? ?????? ?? ????? ?? ?? ???????????? ??????? p, ??? ???????????? ????????????? k. ????? ????, ???????, ??????, w, ??????? ??????? w, ?? ????? ??????????????? ????????? ?? ???????? v, ??????? ??????? v, ?????? ??? ????? ?? ????? ?? ???????? v>p>w>...>v> w>v ?? v>v>...>w>w>...>v, ?????????? ????? ?????, ??????????? ????? w ? v. ?????? ???????, ??? ????? ?????? ????? G, ?? ?????????? ???????? ? w, ?? ?????? ????? ??????, ??????? ? v (?? ???? ?????, ?? ??????? ????, n/2 + k); ? ?????? ???????, ????????, ??? ????? ?????? ????? G, ??????? ? w, ???? ?????, ?? ??????? ????, n/2 + k. ? ??? ??? ?? ???? ??????? ????? G ?? ????? ???? ???????????? ??????? ? ?? ??????? ??????? w, ?? ????? ????? ?????? ????? G, ?????? n + k, ?? ??????, ??? n + 2k. ??? ? ???? ??????? ????????????.
??????? (???) 2. ???? ????? ?????? ????? G(V, E) n > 3 ? ??? ????? ???? ????????? ?????? u ? v ??????????? ???????????: d(u)+d(v)>n ? (u,v)E, ?? ???? G - ???????????. ???? G ????? ??????????? ???? ???? ??????????? ???? ?? ????????? ???????:
1. ??????? ?????: ?? d(vi)>i ? d(vk)>k=>d(vi)+d(vk)>n(ki)
2. ??????? ???????: ?? d(vk)>k>n/2=>d(vn-k)>nk.
?????, ????????, ??? ????? ??? ????? ????????????, ?? ???? ??? H(p) - ????????? ????????????? ?????? ? p ?????????, ? G(p) -- ????????? ???? ?????? ? p ?????????. ?????? ????????? ???????????? ????? ??? ????????????? ?????? ???????????? ???????? ??????????? ???????????????, ?? ??? ??? ?????????? (?, ?????? ????? ?? ??????????) ??????????? ???????? ???????.
???? ????? ??????, ??? ??????? ??????? ?????????? ?????????????? ?????? ??????? ????????? ?????????. ??????? ? ????????? (backtracking) -??? ????? ????? ?????????????? ????????. ??????? ? ????????? ???????? ?????? ??? ??????? ?????, ????????? ???????? ???????????? ????????, ?? ????????? ????? ???????. ? ????? ????? ?????? ?? ????????, ??? ??????? ????? ???????? ??? ?????? (?????? ?????????? ?????) B = (b1,b2,...,bn), ??????????????? ???????? ???????? ? ????????????, ??? ??? ????????? ????? ????????. ??? ???? ? ????? ??????? ??????????? ??????? (????? n) ????? ???? ???????? ???????, ? ? ?????? ??????? ?? ??????????.
????? ???????? ? ????????? ??????? ?? ???, ??? ??? ?????? ??????? ??????????? ???????? ??????? ????????? ??????? ????????? ???????, ?? ???? ??? ??????????. ???? ?????????? ??????????, ?? ?????????? ??????? ? ??????????? ????? ????????? ?????????? ???????, ? ???????? ??????? ??? ????????? ?????? ????????? ????????.
????? ???????? ? ????????? ????? ????????????? ??? ????????????? ????????? ????????????????? ??????? ?????????. ? ???? ????????? ????????? ?????? ?????????????, ? ????? ?????????? ? ???????. ??? ???????? ???? ???????????? ????? ??????????? ?????????, ??? ??? ?????? ?? ?????? ???????????? ????????? ????????:
* ????????? ???????????? ???????? ?????????? ? ???????????, ?? ????? ?? ????????? ??????????? ???????????????. ???? ????? ??????????? ????, ?? ??????? ????????? ??????? ?? ?????
* ?????????? ????????????????? ?????????? (??????????, ??????? ?? ?????? ?????? ????? ????????? ????? ?????? ????????). ???? ????? ?????????? ???, ?? ??????? ?????????? ??????? ? ???????????? ????? ?? ?????????; ??? ??????????????? ????? ??? ??????????? ????????. ???? ????????????????? ?????????? ??????????, ?? ??????????? ????????? ?????.
* ??????????? ????, ? ???????
1) ???????????? ?????????? ???????? ??????? ??????????
2) ??? ??????? ???????? ?????????? ???????????? ????? ????????? ??????? ??????
???????? ????????? ????????????? ??? ???????????? ??????, ?????????? ??????????? ? ?????????????. ??? ????? ????????? ??????????? ????? ???? ??????? ??? ???????, ? ??? ??????????????? ????? - ??????? ??????????? ???????.
2. ???????? ????????? ??????. ????-?????
1) ?????? 3 ???????: ??? ????? ?????????? ??????, ??? ?????????? ???????? ????, ? ??? ??????????? ??????? ???????, ?? ??????? ????????? ??????? ?? ????????? ????? ????????.
2) ????? ????????? ????????????? ? false. ??????? ? ??????? ????????? ????????????? ? -1. ????????? ??????? ???????? ???????.
3) ??? ?????? ??????? ? ??????? ??????? (?? ???????? ?????????? ????), ???? ?? ?? ?? ????????, ????????? ?? ?????? ? ??????? ????????? ("?? ??? ????????????"), ??????? ?????? ????????? ??????? ? ?????????? ?? ? ??????? ????.
4) ???? ??????, ??????? ? ??????? ????????, ?? ??????? ?? ??? ?? ????, ???, ?? ? ??????? "?? ??? ????????????" ??? ??????? ??????? ?????????? -1, ???????? ?????? ??????? ??? ????????????, ?????? "?????" ?? 1 ??????? ? ???? ?????, ?????????????? ??????? ?????????? ?????????? ???????.
5) ?????? ??????? ???????????? ? ??????????? true, ???? ???????? ?????? ???? ? ???? ?????????? ???? ????? ????????? ????????? ???????? ? ??????. ???? ???? ?? ?????? ? "?????" ??????????, ?? ?????????? false.
6) ????????? ? ???? 2.
1. 3. ?????? ??????? ??????
?????? 1
?????? ????
???.1 ???? ?????????
???.2
?????? 2
?????? ????
???.3
???????????? ?????: 1,2,3,4,0,1; 1,3,2,0,4,1; 1,2,0,4,3,1; 1,0,2,3,4,1; 1,4,3,2,0,1; 1,4,0,2,3,1; 1,3,4,0,2,1;
???? ?????????
???.4
?????? 3
???.5
???????????? ?????: 1,2,3,4,0,1; 1,0,4,3,2,1; ???? ?????????
???.6
??????????
? ???? ???????? ?????? ???? ??????????? ????????? ?????????? ???????????? ????? ? ?????, ????????? ???????? ? ?????????.
???????? ????????, ???????? ? ??????????? ???????, ???? ??????? ????????????? ????????? ???? ????????? ????, ????? ???? ???? ????????? ????????????? ? ???? ???????? ?????????? ????.
? ?????? ?????????????? ?????????? ??????????? ???? n-p-n ??122?, ????????? ???? E24. ????????? ???? ????????? ???? ??????? ? ???? ?????????? ????????, ? ????? ????, ? ??????? "??????????".
?????? ???????????? ??????????
1. ??. ??????????. ?????? ??????????? ??????????. 2-? ?????????????? ???????.
2. ?. ???????, ?. ???????? - ???????? ? ????????? ??????. 1982?.
3. ?.?. ??????????, ?.?. ???????? - ????? ? ????????????????: ?????????, ???????????? ? ??????????.
4. ?.?. ??????????, ?.?. ?????????, ?.?. ???????, ?.?. ?????? - ?????? ????????????? ? ??????? ?????????????? ??????. ??????? ???????. 1996?.
5. ?. ??????? - ????????????? ??? ?????????????. 1988?.
6. ?. ?????? - ?????? ??????. 1973?.
??????????
?????????? 1.
??? ?????????:
#include "stdafx.h"
#include <stdio.h>
#define n 10
bool boo[n];
int way[n], r[n];
int a[n][n]=
{
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0
};
bool gamilton(int start)
{
int cur = start; int next = 0; way[next++] = cur; bool found;
while (true)
{
found = false;
boo[cur] = true;
for (int i = r[cur] + 1; i < n; i++)
if (i != cur && (a[i][cur] || a[cur][i]) && !boo[i])
{
found = true;
r[cur] = i;
way[next++] = cur = i;
break;
}
if (!found)
{
if (next == 1) return false;
r[cur] = -1;
boo[cur] = false;
cur = way[--next - 1];
}
else
if (next == n && (a[cur][start] || a[start][cur])) return true;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int i;
printf("Solution:\n");
for (i = 0; i < n; i++) { boo[i] = false; r[i] = -1; }
if (gamilton(1))
{
for (i = 0; i < n; i++) printf("%d ", way[i]);
printf("%d\n", way[0]);
}
else
printf("Solution Not Found!\n");
getchar();
}
2
2
????????, 2013 ?.
Документ
Категория
Без категории
Просмотров
4
Размер файла
274 Кб
Теги
kursovaya
1/--страниц
Пожаловаться на содержимое документа