{"id":336193,"date":"2022-07-26T09:00:12","date_gmt":"2022-07-26T09:00:12","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=336193"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=336193","title":{"rendered":"<span>\u0412\u044b\u0431\u0438\u0440\u0430\u0435\u043c\u0441\u044f \u0438\u0437 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u00ab\u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443\u00bb (BFS) \u043d\u0430 Python<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/730\/776\/55c\/73077655c12cfaaf455bf4f04792a977.png\" width=\"1094\" height=\"822\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/730\/776\/55c\/73077655c12cfaaf455bf4f04792a977.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0423\u0447\u0438\u043c\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043d\u0430 Python \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 (BFS) \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447.<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443\u00bb (BFS). \u0417\u0430\u0442\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438: \u043a\u0430\u043a \u0432\u044b\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0438\u0437 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430.<\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u0433\u0440\u0430\u0444\u044b. \u041a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0433\u0440\u0430\u0444\u0430 \u2013 \u044d\u0442\u043e \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u0437\u0430\u0434\u0430\u0447\u0438. \u041a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u0443\u0437\u043b\u0430 (\u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u2013 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0438 \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0435\u0442 \u0432\u0441\u043b\u0435\u0434 \u0437\u0430 \u044d\u0442\u0438\u043c \u0443\u0437\u043b\u043e\u043c \u043d\u043e\u0432\u044b\u0435 (\u0442\u043e \u0435\u0441\u0442\u044c, \u043d\u043e\u0432\u044b\u0435 \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438), \u0440\u0435\u0448\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0443 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438. \u042d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043e\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f, \u043a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0443\u0441\u043f\u0435\u0445 \u2013 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0438\u043b\u0438 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u043f\u0440\u043e\u0432\u0430\u043b). \u0421\u0440\u0435\u0434\u0438 \u0441\u0430\u043c\u044b\u0445 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u2013 \u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443 (DFS), \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 (BFS), \u0436\u0430\u0434\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u043e\u0438\u0441\u043a \u043f\u043e \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u044e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 (UCS), A*-\u043f\u043e\u0438\u0441\u043a, \u0442.\u0434. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0435\u0447\u044c \u043f\u043e\u0439\u0434\u0435\u0442 \u043e \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u2013 \u044d\u0442\u043e \u00ab\u0441\u043b\u0435\u043f\u043e\u0439\u00bb \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041e\u043d \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u0441\u043b\u0435\u043f\u044b\u043c\u00bb, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0443 \u0441 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0433\u043e \u0441\u043e\u0431\u043e\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438) \u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435, \u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442 \u043a \u0443\u0437\u043b\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f. \u0415\u0441\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0442\u043e \u043e\u043d \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0438 \u043f\u0440\u0435\u043a\u0440\u0430\u0449\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a, \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0435\u0442 \u043e\u0442 \u0443\u0437\u043b\u0430 \u043d\u043e\u0432\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u00ab\u043f\u043e\u043b\u043d\u044b\u043c\u00bb &#8212; \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043e\u043d \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u00a0\u0422\u043e\u0447\u043d\u0435\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0431\u043b\u0438\u0436\u0435 \u0432\u0441\u0435\u0433\u043e \u043a \u043a\u043e\u0440\u043d\u044e. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445, \u0433\u0434\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 \u0443\u0437\u043b\u0430 \u043a \u043b\u044e\u0431\u043e\u043c\u0443 \u0435\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u043c\u0443 \u0443\u0437\u043b\u0443 \u0441\u0442\u043e\u0438\u0442 \u0435\u0434\u0438\u043d\u0438\u0446\u0443, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c BFS \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0437\u0430 \u0443\u0440\u043e\u0432\u043d\u0435\u043c, \u043e\u043d \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <a href=\"https:\/\/python.plainenglish.io\/queue-data-strucure-theory-and-python-implementation-e58f3582c390\"><u>\u043e\u0447\u0435\u0440\u0435\u0434\u044c<\/u><\/a>, \u0442\u0430\u043a \u0447\u0442\u043e \u043d\u043e\u0432\u044b\u0435 \u0443\u0437\u043b\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432 \u0445\u0432\u043e\u0441\u0442 \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0430 \u0441\u0442\u0430\u0440\u044b\u0435 \u0443\u0437\u043b\u044b \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u0437 \u0433\u043e\u043b\u043e\u0432\u044b \u043e\u0447\u0435\u0440\u0435\u0434\u0438. \u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 \u0434\u043b\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 BFS \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code>procedure BFS_Algorithm(graph, initial_vertex):   create a queue called frontier   create a list called visited_vertex   add the initial vertex in the frontier   while True:     if frontier is empty then       print(\"No Solution Found\")       break        selected_node = remove the first node of the frontier     add the selected_node to the visited_vertex list        \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438      if selected_node is the solution then        print(selected_node)       break        \/\/ \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u043e\u0442 \u0443\u0437\u043b\u0430     new_nodes = extend the selected_node       \/\/ \u0414\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0443\u0437\u043b\u044b, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u0434\u043d\u0435\u043c \u043a\u0440\u0430\u0435     for all nodes from new_nodes do       if node not in visited_vertex and node not in frontier then       add node at the end of the queue<\/code><\/pre>\n<p>\u0418\u0437 \u0432\u044b\u0448\u0435\u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, BFS, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0432 \u0444\u043e\u0440\u043c\u0435 \u0433\u0440\u0430\u0444\u0430 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0435\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 (\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b). \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0438\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b (\u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438). \u042d\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0430\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435, \u0447\u0442\u043e \u043d\u0430\u043c \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2013 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c, \u0442\u0430\u043a\u043e\u0439, \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0433 \u0431\u044b \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b.<\/p>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u0432 \u043e\u0431\u0449\u0438\u0445 \u0447\u0435\u0440\u0442\u0430\u0445 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443, \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0441\u0442\u0430\u043d\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442, \u0442\u0430\u043a\u043e\u0439, \u043a\u0430\u043a \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435, \u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043e\u0442 \u0432\u0445\u043e\u0434\u0430 \u043a \u0432\u044b\u0445\u043e\u0434\u0443 \u0437\u0430 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0448\u0430\u0433\u043e\u0432. \u0417\u0430 \u043e\u0434\u0438\u043d \u0448\u0430\u0433 \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u043a\u043e\u043c\u043d\u0430\u0442\u044b \u0432 \u0434\u0440\u0443\u0433\u0443\u044e. \u0412 \u043d\u0430\u0448\u0435\u043c \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435 11 \u043a\u043e\u043c\u043d\u0430\u0442, \u0438 \u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043d\u0438\u0445 \u2013 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0435 \u0438\u043c\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u201cA\u201d, \u201cB\u201d, \u0442.\u0434. \u0418\u0442\u0430\u043a, \u043d\u0430\u0448\u0430 \u0446\u0435\u043b\u044c \u2013 \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u0438\u0437 \u043a\u043e\u043c\u043d\u0430\u0442\u044b \u201cS\u201d \u0432 \u043a\u043e\u043c\u043d\u0430\u0442\u0443 \u201cI\u201d.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d1c\/b6f\/523\/d1cb6f5239be1ce7ac7baf6c7026684c.png\" alt=\"\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\" title=\"\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\" width=\"1006\" height=\"1001\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d1c\/b6f\/523\/d1cb6f5239be1ce7ac7baf6c7026684c.png\"\/><figcaption>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442<\/figcaption><\/figure>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443, \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0443\u0436\u043d\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0435\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430. \u0427\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f <em>\u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u043a\u043e\u043c\u043d\u0430\u0442\u0443<\/em> \u0438 <em>\u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0434\u0432\u0435\u0440\u044c<\/em> \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435. \u041f\u043e\u0441\u043b\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0439 \u043d\u0438\u0436\u0435 \u0433\u0440\u0430\u0444 \u2013 \u0432 \u043d\u0435\u043c 11 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 15 \u0440\u0435\u0431\u0435\u0440.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0d9\/7f2\/f2f\/0d97f2f2f9754f7948d478b91350a947.png\" alt=\"\u0413\u0440\u0430\u0444, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0443 \" title=\"\u0413\u0440\u0430\u0444, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0443 \" width=\"1094\" height=\"766\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0d9\/7f2\/f2f\/0d97f2f2f9754f7948d478b91350a947.png\"\/><figcaption>\u0413\u0440\u0430\u0444, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0443 <\/figcaption><\/figure>\n<p>\u0418\u0442\u0430\u043a, \u043e\u0442 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u201cS\u201d (\u044d\u0442\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u201cI\u201d (\u044d\u0442\u043e \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b, \u043f\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0435\u043d\u0430). \u041a\u0430\u043a \u044f \u0443\u0436\u0435 \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u043b \u0432\u044b\u0448\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u043e\u0431\u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u0442 \u043a \u0443\u0437\u043b\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u2013 \u043a\u0430\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435. <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/b36\/ee9\/db7\/b36ee9db77d4f2a4ea9d5dc366856fde.png\" alt=\"\u0418\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u0449\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \" title=\"\u0418\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u0449\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \" width=\"1094\" height=\"622\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b36\/ee9\/db7\/b36ee9db77d4f2a4ea9d5dc366856fde.png\"\/><figcaption>\u0418\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u0449\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 <\/figcaption><\/figure>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0432 \u0440\u0430\u043d\u0435\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0432 \u043d\u0430\u0448\u0435\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435. \u041a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0438\u043b\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438. \u041d\u043e \u0432 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043c\u044b \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u043d\u0430 \u0441\u043b\u043e\u0432\u0430\u0440\u0435, \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u043e\u0432\u0430\u0440\u0435 \u0431\u044b\u043b\u0438 \u0438\u043c\u0435\u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0431\u044b\u043b \u0441\u043f\u0438\u0441\u043e\u043a \u0432\u0441\u0435\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u0441\u043c\u0435\u0436\u043d\u044b\u0445 \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439, \u043a\u0430\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0438\u0436\u0435.<\/p>\n<pre><code class=\"python\">graph = {     \"A\": ['S'],     \"B\": ['C', 'D','S'],     \"C\": ['B', 'J'],     \"D\": ['B', 'G', 'S'],     \"E\": ['G', 'S'],     \"F\": ['G', 'H'],     \"G\": ['D', 'E', 'F', 'H', 'J'],     \"H\": ['F', 'G', 'I'],     \"I\": ['H', 'J'],     \"J\": ['C', 'G', 'I'],     \"S\": ['A', 'B', 'D', 'E']   }<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043a\u043b\u0430\u0441\u0441 Node. \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d \u043a\u0430\u043a \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441, \u0447\u0442\u043e\u0431\u044b \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439. \u0418\u0442\u0430\u043a, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. <\/p>\n<pre><code class=\"python\">from abc import ABC, abstractmethod class Node(ABC):   \"\"\"     \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435      \u042d\u0442\u043e\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0432\u0430\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043a\u043b\u0430\u0441\u0441 \u0434\u043b\u044f BFS \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u0449\u0438\u043c,     \u0438 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447      ...       Methods     -------     __eq__(self, other)         Determines if two nodes are equal or not          is_the_solution(self)         Determines if the current node is the solution of the problem      def is_the_solution(self)         Extends the current node according to the rules of the problem          __str__(self)         Prints the node data   \"\"\"    @abstractmethod   def __eq__(self, other):     pass    @abstractmethod   def is_the_solution(self, state):     pass    @abstractmethod   def extend_node(self):     pass    @abstractmethod   def __str__(self):     pass<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u043d\u0430\u043c \u0434\u043b\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u043d\u0430 \u043f\u0435\u0440\u0435\u0434\u043d\u0438\u0439 \u043a\u0440\u0430\u0439, \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0443\u0437\u0435\u043b \u0441 \u043f\u0435\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u043a\u0440\u0430\u044f, \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043f\u0443\u0441\u0442 \u043b\u0438 \u043f\u0435\u0440\u0435\u0434\u043d\u0438\u0439 \u043a\u0440\u0430\u0439 \u0438, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u0442.\u0434.<\/p>\n<pre><code class=\"python\">class BFS:   \"\"\"     This class used to represent the  Breadth First Search algorithm (BFS)      ...      Attributes     ----------     start_state : Node         represent the initial state of the problem      final_state : Node         represent the final state (target) of the problem      frontier : List         represents the stack and is initialized with the start node     checked_nodes : List         represents the list of nodes that have been visited throughout the algorithm execution     number_of_steps : Integer         Keep track of the algorithm's number of steps      path : List         represents the steps from the initial state to the final state      Methods     -------     insert_to_frontier(self, node)         Insert a new node to the frontier. In this algorithm the frontier is a queue, so each new element is inserted to end of the data structure           remove_from_frontier(self)         Remove the first element from the frontier, following the FIFO technic. The removed node is added to the checked_node list      remove_from_frontier(self)         check if the frontier is empty          search(self)         Implements the core of algorithm. This method searches, in the search space of the problem, a solution      \"\"\"    def __init__(self, start, final):     self.start_state = start     self.final_state = final     self.frontier = [self.start_state]     self.checked_nodes = []     self.number_of_steps = 0     self.path = []    def insert_to_frontier(self, node):     \"\"\"       Insert a node at the end of the frontier        Parameters       ----------       node : Node           The node of the problem that will be added to the frontier     \"\"\"     self.frontier.append(node)       def remove_from_frontier(self):     \"\"\"       Remove a node from the beginning of the frontier       Then add the removed node to the checked_nodes list        Returns       -------       Node         the first node of the frontier     \"\"\"     first_node = self.frontier.pop(0)     self.checked_nodes.append(first_node)     return first_node     def frontier_is_empty(self):     \"\"\"       Check if the frontier id empty, so no solution found        Returns       -------       Boolean         True if the frontier is empty         False if the frontier is not empty     \"\"\"     if len(self.frontier) == 0:       return True     return False       def search(self):     \"\"\"       Is the main algorithm. Search for a solution in the solution space of the problem       Stops if the frontier is empty, so no solution found or if find a solution.      \"\"\"     while True:        self.number_of_steps += 1              # print(f\"Step: {self.number_of_steps}, Frontier Size: {len(self.frontier)} \")       if self.frontier_is_empty():         print(f\"No Solution Found after {self.number_of_steps} steps!!!\")         break                selected_node = self.remove_from_frontier()        # \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438       if selected_node.is_the_solution(self.final_state):         print(f\"Solution Found in {self.number_of_steps} steps\")         print(selected_node)         break        # \u043d\u0430\u0440\u0430\u0441\u0442\u0438\u0442\u044c \u0443\u0437\u0435\u043b       new_nodes = selected_node.extend_node()        # \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043d\u0430\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u043f\u0435\u0440\u0435\u0434\u043d\u0438\u0439 \u043a\u0440\u0430\u0439       if len(new_nodes) > 0:         for new_node in new_nodes:           if new_node not in self.frontier and new_node not in self.checked_nodes:             self.insert_to_frontier(new_node)<\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043a\u043b\u0430\u0441\u0441, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u0443\u0437\u0435\u043b \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435. \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 Node, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043b\u043e\u0436\u0435\u043d\u044b \u0432\u0441\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b.<\/p>\n<pre><code class=\"python\">from BFS_Algorithm import Node  class MazeNode(Node):   \"\"\"     This class used to represent the node of a maze     ...     Attributes     ----------     graph : Dictionary         represent the graph       value : String         represents the id of the vertex     parent : MazeNode         represents the parent of the current node        Methods     -------     __eq__(self, other)         Determines if the current node is the same with the other      is_the_solution(self, final_state)         Checks if the current node is the solution     extend_node(self)         Extends the current node, creating a new instance of MazeNode for each edge starts from current node      _find_path(self)         Find the path (all verticies and edges from the intitial state to the final state)     __str__(self)         Returns the solution of the maze, the whole path vertex by vertex in order to be printed properly.   \"\"\"    def __init__(self, graph, value):     self.graph = graph     self.value = value     self.parent = None       def __eq__(self, other):     \"\"\"       Check if the current node is equal with the other node.       Parameters       ----------       Other : MazeNode           The other vertex of the graph       Returns       -------       Boolean         True: if both verticies are the same         False: If verticies are different     \"\"\"      if isinstance(other, MazeNode):       return self.value == other.value     return self.value == other       def is_the_solution(self, final_state):     \"\"\"       Checks if the current node is the solution       Parameters       ----------       final_state : MazeNode           The target vertex (final state) of the graph       Returns       -------       Boolean         True: if both verticies are the same, so solution has been found         False: If verticies are different, so solution has not been found     \"\"\"     return self.value == final_state       def extend_node(self):     \"\"\"       Extends the current node, creating a new instance of MazeNode for each edge starts from the current node       Returns       -------       List         List with all valid new nodes     \"\"\"     children = [MazeNode(self.graph, child) for child in self.graph[self.value]]     for child in children:       child.parent = self     return children    def _find_path(self):     \"\"\"       Find the path, all verticies and edges from the intitial state to the final state       Returns       -------       List         List with all nodes fron start to end in a row     \"\"\"     path = []     current_node = self     while current_node.parent is not None:       path.insert(0, current_node.value)       current_node = current_node.parent     path.insert(0, current_node.value)     return path    def __str__(self):     \"\"\"       Returns the solution of the maze, the whole path vertex by vertex as well as the path lenght, in order to be printed properly.       Returns       -------       str         the solution of the problem     \"\"\"     total_path = self._find_path()     path = \"\"     for index in range(len(total_path)):       if index == len(total_path) - 1:         path += f\"{total_path[index]} \"       else:         path += f\"{total_path[index]} -> \"       return path + f\"\\nPath lenght: {len(total_path)-1}\"<\/code><\/pre>\n<p>\u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0448\u0430\u0433 \u2013 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0432\u0441\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442 \u0438 \u0432\u044b\u0432\u0435\u0434\u0435\u0442 \u043d\u0430 \u044d\u043a\u0440\u0430\u043d \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u0432\u0445\u043e\u0434\u0430 \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0434\u043e \u0432\u044b\u0445\u043e\u0434\u0430 \u0438\u0437 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430. \u042d\u0442\u043e\u0442 \u043f\u0443\u0442\u044c \u0438\u043c\u0435\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 4 \u0438 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a: \u201cS\u201d -> \u201cB\u201d -> \u201cC\u201d -> \u201cJ\u201d -> \u201cI\u201d.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/892\/19b\/b18\/89219bb18adfdbdbc9e0b99084c409ea.png\" alt=\"\u041f\u0443\u0442\u044c \u043e\u0442 \u0443\u0437\u043b\u0430 S \u043a \u0443\u0437\u043b\u0443 I\" title=\"\u041f\u0443\u0442\u044c \u043e\u0442 \u0443\u0437\u043b\u0430 S \u043a \u0443\u0437\u043b\u0443 I\" width=\"1083\" height=\"833\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/892\/19b\/b18\/89219bb18adfdbdbc9e0b99084c409ea.png\"\/><figcaption>\u041f\u0443\u0442\u044c \u043e\u0442 \u0443\u0437\u043b\u0430 S \u043a \u0443\u0437\u043b\u0443 I<\/figcaption><\/figure>\n<h2>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u044b\u043b\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e, \u043a\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0432\u044b\u0445\u043e\u0434 \u0438\u0437 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c BFS \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0431\u043b\u0438\u0436\u0435 \u0432\u0441\u0435\u0433\u043e \u043a \u043a\u043e\u0440\u043d\u044e. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0435\u0441\u043b\u0438 \u0443 \u0432\u0441\u0435\u0445 \u0440\u0435\u0431\u0435\u0440 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u0430\u044f \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c, \u0442\u043e BFS \u0432\u0435\u0440\u043d\u0435\u0442 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>\u0412\u0435\u0441\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043f\u0440\u043e\u0435\u043a\u0442\u0430 \u0432\u044b\u043b\u043e\u0436\u0435\u043d \u043d\u0430 GitHub <a href=\"https:\/\/github.com\/AndreasSoularidis\/AISearchAlgorithms\/tree\/main\/Maze\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/piter\/blog\/679020\/\"> https:\/\/habr.com\/ru\/company\/piter\/blog\/679020\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0423\u0447\u0438\u043c\u0441\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c \u043d\u0430 Python \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 (BFS) \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447.<\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443\u00bb (BFS). \u0417\u0430\u0442\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438: \u043a\u0430\u043a \u0432\u044b\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0438\u0437 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0430.<\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u0433\u0440\u0430\u0444\u044b. \u041a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0433\u0440\u0430\u0444\u0430 \u2013 \u044d\u0442\u043e \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u0437\u0430\u0434\u0430\u0447\u0438. \u041a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u0443\u0437\u043b\u0430 (\u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440 \u2013 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0438 \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0435\u0442 \u0432\u0441\u043b\u0435\u0434 \u0437\u0430 \u044d\u0442\u0438\u043c \u0443\u0437\u043b\u043e\u043c \u043d\u043e\u0432\u044b\u0435 (\u0442\u043e \u0435\u0441\u0442\u044c, \u043d\u043e\u0432\u044b\u0435 \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438), \u0440\u0435\u0448\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0443 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438. \u042d\u0442\u043e\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043e\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f, \u043a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0443\u0441\u043f\u0435\u0445 \u2013 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0438\u043b\u0438 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u043d\u043e\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u043f\u0440\u043e\u0432\u0430\u043b). \u0421\u0440\u0435\u0434\u0438 \u0441\u0430\u043c\u044b\u0445 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u2013 \u043f\u043e\u0438\u0441\u043a \u0432 \u0433\u043b\u0443\u0431\u0438\u043d\u0443 (DFS), \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 (BFS), \u0436\u0430\u0434\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043f\u043e\u0438\u0441\u043a \u043f\u043e \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u044e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 (UCS), A*-\u043f\u043e\u0438\u0441\u043a, \u0442.\u0434. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0435\u0447\u044c \u043f\u043e\u0439\u0434\u0435\u0442 \u043e \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u2013 \u044d\u0442\u043e \u00ab\u0441\u043b\u0435\u043f\u043e\u0439\u00bb \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041e\u043d \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u0441\u043b\u0435\u043f\u044b\u043c\u00bb, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0433\u0440\u0430\u0444\u0430. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0443 \u0441 \u043a\u043e\u0440\u043d\u0435\u0432\u043e\u0433\u043e \u0443\u0437\u043b\u0430 (\u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0433\u043e \u0441\u043e\u0431\u043e\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438) \u0438 \u0438\u0441\u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435, \u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442 \u043a \u0443\u0437\u043b\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f. \u0415\u0441\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0442\u043e \u043e\u043d \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0438 \u043f\u0440\u0435\u043a\u0440\u0430\u0449\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a, \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0435\u0442 \u043e\u0442 \u0443\u0437\u043b\u0430 \u043d\u043e\u0432\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u00ab\u043f\u043e\u043b\u043d\u044b\u043c\u00bb &#8212; \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043e\u043d \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u00a0\u0422\u043e\u0447\u043d\u0435\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0431\u043b\u0438\u0436\u0435 \u0432\u0441\u0435\u0433\u043e \u043a \u043a\u043e\u0440\u043d\u044e. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445, \u0433\u0434\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 \u0443\u0437\u043b\u0430 \u043a \u043b\u044e\u0431\u043e\u043c\u0443 \u0435\u0433\u043e \u0434\u043e\u0447\u0435\u0440\u043d\u0435\u043c\u0443 \u0443\u0437\u043b\u0443 \u0441\u0442\u043e\u0438\u0442 \u0435\u0434\u0438\u043d\u0438\u0446\u0443, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c BFS \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0437\u0430 \u0443\u0440\u043e\u0432\u043d\u0435\u043c, \u043e\u043d \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <a href=\"https:\/\/python.plainenglish.io\/queue-data-strucure-theory-and-python-implementation-e58f3582c390\"><u>\u043e\u0447\u0435\u0440\u0435\u0434\u044c<\/u><\/a>, \u0442\u0430\u043a \u0447\u0442\u043e \u043d\u043e\u0432\u044b\u0435 \u0443\u0437\u043b\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432 \u0445\u0432\u043e\u0441\u0442 \u043e\u0447\u0435\u0440\u0435\u0434\u0438, \u0430 \u0441\u0442\u0430\u0440\u044b\u0435 \u0443\u0437\u043b\u044b \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u0437 \u0433\u043e\u043b\u043e\u0432\u044b \u043e\u0447\u0435\u0440\u0435\u0434\u0438. \u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 \u0434\u043b\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 BFS \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code>procedure BFS_Algorithm(graph, initial_vertex):   create a queue called frontier   create a list called visited_vertex   add the initial vertex in the frontier   while True:     if frontier is empty then       print(\"No Solution Found\")       break        selected_node = remove the first node of the frontier     add the selected_node to the visited_vertex list        \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438      if selected_node is the solution then        print(selected_node)       break        \/\/ \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u043e\u0442 \u0443\u0437\u043b\u0430     new_nodes = extend the selected_node       \/\/ \u0414\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0443\u0437\u043b\u044b, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0435\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u0434\u043d\u0435\u043c \u043a\u0440\u0430\u0435     for all nodes from new_nodes do       if node not in visited_vertex and node not in frontier then       add node at the end of the queue<\/code><\/pre>\n<p>\u0418\u0437 \u0432\u044b\u0448\u0435\u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, BFS, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0432 \u0444\u043e\u0440\u043c\u0435 \u0433\u0440\u0430\u0444\u0430 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0435\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 (\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b). \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0438\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0430\u0440\u0430\u0449\u0438\u0432\u0430\u0442\u044c \u0443\u0437\u043b\u044b (\u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u044b \u0437\u0430\u0434\u0430\u0447\u0438). \u042d\u0442\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0430\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435, \u0447\u0442\u043e \u043d\u0430\u043c \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2013 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c, \u0442\u0430\u043a\u043e\u0439, \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0433 \u0431\u044b \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b.<\/p>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u0432 \u043e\u0431\u0449\u0438\u0445 \u0447\u0435\u0440\u0442\u0430\u0445 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0432 \u0448\u0438\u0440\u0438\u043d\u0443, \u043e\u0431\u0441\u0443\u0434\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0441\u0442\u0430\u043d\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442, \u0442\u0430\u043a\u043e\u0439, \u043a\u0430\u043a \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435, \u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043e\u0442 \u0432\u0445\u043e\u0434\u0430 \u043a \u0432\u044b\u0445\u043e\u0434\u0443 \u0437\u0430 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0448\u0430\u0433\u043e\u0432. \u0417\u0430 \u043e\u0434\u0438\u043d \u0448\u0430\u0433 \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u043a\u043e\u043c\u043d\u0430\u0442\u044b \u0432 \u0434\u0440\u0443\u0433\u0443\u044e. \u0412 \u043d\u0430\u0448\u0435\u043c \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435 11 \u043a\u043e\u043c\u043d\u0430\u0442, \u0438 \u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043d\u0438\u0445 \u2013 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0435 \u0438\u043c\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u201cA\u201d, \u201cB\u201d, \u0442.\u0434. \u0418\u0442\u0430\u043a, \u043d\u0430\u0448\u0430 \u0446\u0435\u043b\u044c \u2013 \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u0438\u0437 \u043a\u043e\u043c\u043d\u0430\u0442\u044b \u201cS\u201d \u0432 \u043a\u043e\u043c\u043d\u0430\u0442\u0443 \u201cI\u201d.<\/p>\n<figure class=\"full-width\"><figcaption>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442<\/figcaption><\/figure>\n<p>\u0418\u0442\u0430\u043a, \u043c\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443, \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0443\u0436\u043d\u043e \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0435\u0435 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430. \u0427\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f <em>\u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u043a\u043e\u043c\u043d\u0430\u0442\u0443<\/em> \u0438 <em>\u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0434\u0432\u0435\u0440\u044c<\/em> \u0432 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435. \u041f\u043e\u0441\u043b\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0439 \u043d\u0438\u0436\u0435 \u0433\u0440\u0430\u0444 \u2013 \u0432 \u043d\u0435\u043c 11 \u0432\u0435\u0440\u0448\u0438\u043d \u0438 15 \u0440\u0435\u0431\u0435\u0440.<\/p>\n<figure class=\"full-width\"><figcaption>\u0413\u0440\u0430\u0444, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443 \u0432\u044b\u0448\u0435 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0443 <\/figcaption><\/figure>\n<p>\u0418\u0442\u0430\u043a, \u043e\u0442 \u043a\u0430\u0436\u0434\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043a \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u201cS\u201d (\u044d\u0442\u043e \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435) \u0434\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u201cI\u201d (\u044d\u0442\u043e \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0443\u0437\u0435\u043b, \u043f\u043e \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0435\u043d\u0430). \u041a\u0430\u043a \u044f \u0443\u0436\u0435 \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u043b \u0432\u044b\u0448\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u043e\u0431\u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u0441\u0435 \u0443\u0437\u043b\u044b \u043d\u0430 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u043e\u043c \u0443\u0440\u043e\u0432\u043d\u0435, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u0442 \u043a \u0443\u0437\u043b\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0443\u0440\u043e\u0432\u043d\u044f \u2013 \u043a\u0430\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435. <\/p>\n<figure class=\"full-width\"><figcaption>\u0418\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443 \u0438\u0449\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 <\/figcaption><\/figure>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u0441\u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u0432 \u0440\u0430\u043d\u0435\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043a \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442 \u0432 \u043d\u0430\u0448\u0435\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435. \u041a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0433\u0440\u0430\u0444\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0438\u043b\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438. \u041d\u043e \u0432 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043c\u044b \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c\u0441\u044f \u043d\u0430 \u0441\u043b\u043e\u0432\u0430\u0440\u0435, \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043a\u043b\u044e\u0447\u0430\u043c\u0438 \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u043e\u0432\u0430\u0440\u0435 \u0431\u044b\u043b\u0438 \u0438\u043c\u0435\u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d, \u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0431\u044b\u043b \u0441\u043f\u0438\u0441\u043e\u043a \u0432\u0441\u0435\u0445 \u0432\u0435\u0440\u0448\u0438\u043d, \u0441\u043c\u0435\u0436\u043d\u044b\u0445 \u0441 \u0434\u0430\u043d\u043d\u043e\u0439 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u0432\u0435\u0440\u0448\u0438\u043d\u043e\u0439, \u043a\u0430\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0438\u0436\u0435.<\/p>\n<pre><code class=\"python\">graph = {     \"A\": ['S'],     \"B\": ['C', 'D','S'],     \"C\": ['B', 'J'],     \"D\": ['B', 'G', 'S'],     \"E\": ['G', 'S'],     \"F\": ['G', 'H'],     \"G\": ['D', 'E', 'F', 'H', 'J'],     \"H\": ['F', 'G', 'I'],     \"I\": ['H', 'J'],     \"J\": ['C', 'G', 'I'],     \"S\": ['A', 'B', 'D', 'E']   }<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043a\u043b\u0430\u0441\u0441 Node. \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d \u043a\u0430\u043a \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441, \u0447\u0442\u043e\u0431\u044b \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439. \u0418\u0442\u0430\u043a, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438. <\/p>\n<pre><code class=\"python\">from abc import ABC, abstractmethod class Node(ABC):   \"\"\"     \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435      \u042d\u0442\u043e\u0442 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u0432\u0430\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043a\u043b\u0430\u0441\u0441 \u0434\u043b\u044f BFS \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u0449\u0438\u043c,     \u0438 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447      ...       Methods     -------     __eq__(self, other)         Determines if two nodes are equal or not          is_the_solution(self)         Determines if the current node is the solution of the problem      def is_the_solution(self)         Extends the current node according to the rules of the problem          __str__(self)         Prints the node data   \"\"\"    @abstractmethod   def __eq__(self, other):     pass    @abstractmethod   def is_the_solution(self, state):     pass    @abstractmethod   def extend_node(self):     pass    @abstractmethod   def __str__(self):     pass<\/code><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043b\u0430\u0441\u0441, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0448\u0438\u0440\u0438\u043d\u0443. \u042d\u0442\u043e\u0442 \u043a\u043b\u0430\u0441\u0441 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u043d\u0430\u043c \u0434\u043b\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439: \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u043d\u0430 \u043f\u0435\u0440\u0435\u0434\u043d\u0438\u0439 \u043a\u0440\u0430\u0439, \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0443\u0437\u0435\u043b \u0441 \u043f\u0435\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u043a\u0440\u0430\u044f, \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043f\u0443\u0441\u0442 \u043b\u0438 \u043f\u0435\u0440\u0435\u0434\u043d\u0438\u0439 \u043a\u0440\u0430\u0439 \u0438, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0439, \u0442.\u0434.<\/p>\n<pre><code class=\"python\">class BFS:   \"\"\"     This class used to represent the  Breadth First Search algorithm (BFS)      ...      Attributes     ----------     start_state : Node         represent the initial state of the problem      final_state : Node         represent the final state (target) of the problem      frontier : List         represents the stack and is initialized with the start node     checked_nodes : List         represents the list of nodes that have been visited throughout the algorithm execution     number_of_steps : Integer         Keep track of the algorithm's number of steps      path : List         represents the steps from the initial state to the final state      Methods     -------     insert_to_frontier(self, node)         Insert a new node to the frontier. In this algorithm the frontier is a queue, so each new element is inserted to end of the data structure           remove_from_frontier(self)         Remove the first element from the frontier, following the FIFO technic. The removed node is added to the checked_node list      remove_from_frontier(self)         check if the frontier is empty          search(self)         Implements the core of algorithm. This method searches, in the search space of the problem, a solution      \"\"\"    def __init__(self, start, final):     self.start_state = start     self.final_state = final     self.frontier = [self.start_state]     self.checked_nodes = []     self.number_of_steps = 0     self.path = []    def insert_to_frontier(self, node):     \"\"\"       Insert a node at the end of the frontier        Parameters       ----------       node : Node           The node of the problem that will be added to the frontier     \"\"\"     self.frontier.append(node)       def remove_from_frontier(self):     \"\"\"       Remove a node from the beginning of the frontier       Then add the removed node to the checked_nodes list        Returns       -------       Node         the first node of the frontier     \"\"\"     first_node = self.frontier.pop(0)     self.checked_nodes.append(first_node)     return first_node     def frontier_is_empty(self):     \"\"\"       Check if the frontier id empty, so no solution found        Returns       -------       Boolean         True if the frontier is empty         False if the frontier is not empty     \"\"\"     if len(self.frontier) == 0:       return True     return False       def search(self):     \"\"\"       Is the main algorithm. Search for a solution in the solution space of the problem       Stops if the frontier is empty, so no solution found or if find a solution.      \"\"\"     while True:        self.number_of_steps += 1              # print(f\"Step: {self.number_of_steps}, Frontier Size: {len(self.frontier)} \")       if self.frontier_is_empty():         print(f\"No Solution Found after {self.number_of_steps} steps!!!\")         break                selected_node = self.remove_from_frontier()        # \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438       if selected_node.is_the_solution(self.final_state):         print(f\"Solution Found in {self.number_of_steps} steps\")         print(selected_node)         break        # \u043d\u0430\u0440\u0430\u0441\u0442\u0438\u0442\u044c \u0443\u0437\u0435\u043b       new_nodes = selected_node.extend_node()        # \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043d\u0430\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0430<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-336193","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/336193","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=336193"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/336193\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=336193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=336193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=336193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}