از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
نمودارها در پایتون – تئوری و پیاده سازی
سرفصلهای مطلب
در این درس به تئوری پشت الگوریتم و پیاده سازی پایتون می پردازیم جستجو و پیمایش عرض اول. اول، ما تمرکز می کنیم روی node جستجو کردن، قبل از پرداختن به پیمایش نمودار با استفاده از الگوریتم BFS، به عنوان دو وظیفه اصلی که می توانید آن را برای آن به کار ببرید.
توجه داشته باشید: ما یک نمودار مجاورت-لیست پیاده سازی شده در درس را فرض می کنیم.
جستجوی وسعت-اول – نظریه
جستجوی اول عرض (BFS) نمودار را به طور سیستماتیک طی می کند، سطح به سطح، تشکیل یک درخت BFS در طول مسیر.
اگر جستجوی خود را از node v
( root node از نمودار یا ساختار داده درختی ما)، الگوریتم BFS ابتدا از همه موارد بازدید می کند همسایه ها از node v
(این گره های کودک هستند، روی مرحله اول) به ترتیبی که در لیست مجاورت آمده است. بعد، گره های فرزند آن همسایگان را می گیرد (سطح دو) در نظر گرفته شود و غیره روی.
این الگوریتم برای هر دو گراف قابل استفاده است پیمایش و جستجو کردن. هنگام جستجو برای a node که شرایط خاصی را برآورده می کند (هدف node)، مسیر با کوتاه ترین فاصله از ابتدا node به هدف node. فاصله به عنوان تعداد شاخه های پیموده شده تعریف می شود.
جستجوی عرض-اول می توان برای حل بسیاری از مسائل از جمله یافتن کوتاه ترین مسیر بین دو گره، تعیین سطوح هر یک استفاده کرد. nodeو حتی حل بازی های پازل و پیچ و خم ها.
در حالی که این الگوریتم کارآمدترین الگوریتم برای حل پیچ و خم ها و معماهای بزرگ نیست – و الگوریتم هایی مانند الگوریتم Dijkstra و A* از آن برتری دارد – همچنان نقش مهمی در این دسته بازی می کند و بسته به آن روی مشکل در دست – DFS و BFS می توانند از پسرعموهای اکتشافی خود بهتر عمل کنند.
جستجوی عرض-اول – الگوریتم
هنگام پیاده سازی BFS، ما معمولا از a استفاده می کنیم FIFO ساختاری مانند a Queue
برای ذخیره گره هایی که در مرحله بعدی بازدید خواهند شد.
توجه داشته باشید: برای استفاده از a Queue
در پایتون، ما نیاز داریم import مربوطه Queue
کلاس از queue
مدول.
ما باید توجه داشته باشیم که درگیر نشویم حلقه های بی نهایت با بازبینی مجدد و مکرر همان گرهها، که میتواند به راحتی با نمودارهایی اتفاق بیفتد چرخه ها. با در نظر گرفتن این موضوع، گره هایی که بوده اند را پیگیری می کنیم ملاقات کرد. این اطلاعات لازم نیست به طور صریح ذخیره شوند، ما به سادگی می توانیم آن را پیگیری کنیم والدین گره ها، بنابراین به طور تصادفی پس از بازدید از یکی به آن باز نمی گردیم.
برای جمع بندی منطق، مراحل الگوریتم BFS به شکل زیر است:
- اضافه کردن root/شروع node به
Queue
. - برای هر node، تنظیم کنید که آنها یک والد تعریف شده نداشته باشند node.
- تا
Queue
خالی است:- را استخراج کنید node از ابتدای
Queue
. - پردازش خروجی را انجام دهید.
- برای هر همسایه جریان node که نمی کند یک والد تعریف شده داشته باشید (بازدید نشده است)، آن را به آن اضافه کنید
Queue
و جریان را تنظیم کنید node به عنوان والدین آنها
- را استخراج کنید node از ابتدای
پردازش خروجی بسته به انجام می شود روی هدف پشت جستجوی نمودار هنگام جستجوی هدف node، پردازش خروجی معمولاً در حال آزمایش است node برابر با هدف است node. این مرحله است روی که می توانید خلاق شوید!
اجرای جستجوی Breadth-First – جستجوی گره هدف
بیایید ابتدا شروع کنیم جستجو کردن – و برای یک هدف جستجو کنید node. علاوه بر هدف node، ما به یک شروع نیاز خواهیم داشت node همچنین. خروجی مورد انتظار a است مسیر که از همان ابتدا ما را هدایت می کند node به هدف node.
با در نظر گرفتن آنها و در نظر گرفتن مراحل الگوریتم، می توانیم آن را پیاده سازی کنیم. ما a را تعریف می کنیم Graph
کلاس برای “پوشش” اجرای جستجوی BFS.
Graph
شامل یک نمایش گراف – در این مورد یک ماتریس مجاورت، و همه روش هایی است که ممکن است هنگام کار با نمودارها به آن نیاز داشته باشید. هم جستجوی BFS و هم پیمایش BFS را به عنوان متدهای آن کلاس پیاده سازی می کنیم:
from queue import Queue
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
self.m_directed = directed
self.m_adj_list = {node: set() for node in self.m_nodes}
def add_edge(self, node1, node2, weight=1):
self.m_adj_list(node1).add((node2, weight))
if not self.m_directed:
self.m_adj_list(node2).add((node1, weight))
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list(key))
پس از اجرای الف لفاف کلاس، می توانیم جستجوی BFS را به عنوان یکی از روش های آن پیاده سازی کنیم:
def bfs(self, start_node, target_node):
visited = set()
queue = Queue()
queue.put(start_node)
visited.add(start_node)
parent = dict()
parent(start_node) = None
path_found = False
while not queue.empty():
current_node = queue.get()
if current_node == target_node:
path_found = True
break
for (next_node, weight) in self.m_adj_list(current_node):
if next_node not in visited:
queue.put(next_node)
parent(next_node) = current_node
visited.add(next_node)
path = ()
if path_found:
path.append(target_node)
while parent(target_node) is not None:
path.append(parent(target_node))
target_node = parent(target_node)
path.reverse()
return path
وقتی مسیر را بازسازی می کنیم (اگر پیدا شد)، از هدف به عقب بر می گردیم node، از طریق پدر و مادر خود، ردیابی مجدد تمام راه به شروع node. علاوه بر این، ما معکوس مسیری برای شهود خودمان برای رفتن از start_node
به سمت target_node
با این حال، این مرحله اختیاری است.
از طرف دیگر، اگر مسیری وجود نداشته باشد، الگوریتم یک لیست خالی برمی گرداند.
با در نظر گرفتن پیاده سازی توضیح داده شده قبلی، می توانیم آن را با اجرای جستجوی BFS آزمایش کنیم روی نمودار مثال:
بیایید این نمودار را با استفاده از ما بازسازی کنیم Graph
کلاس این یک گراف بدون جهت با 6 گره است، بنابراین ما آن را به صورت نمونهسازی میکنیم:
graph = Graph(6, directed=False)
در مرحله بعد، باید تمام لبه های نمودار را به نمونه اضافه کنیم Graph
کلاسی که ما ایجاد کردیم:
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 5)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)
حال، بیایید ببینیم چگونه Graph
کلاس به صورت داخلی نمودار نمونه ما را نشان می دهد.
graph.print_adj_list()
این اراده print لیست مجاورتی که برای نشان دادن نموداری که ایجاد کرده ایم استفاده می شود:
node 0 : {(3, 1), (1, 1), (4, 1), (2, 1)}
node 1 : {(0, 1), (2, 1)}
node 2 : {(0, 1), (1, 1), (5, 1), (3, 1)}
node 3 : {(0, 1), (5, 1), (4, 1), (2, 1)}
node 4 : {(0, 1), (5, 1), (3, 1)}
node 5 : {(3, 1), (4, 1), (2, 1)}
در این لحظه، ما یک نمودار ایجاد کردهایم و درک میکنیم که چگونه به عنوان یک ماتریس مجاورت ذخیره میشود. با در نظر گرفتن تمام این موارد، می توانیم خود جستجو انجام دهیم. بگویید می خواهیم جستجو کنیم node 5
شروع از node 0
:
path = ()
path = graph.bfs(0, 5)
print(path)
اجرای این کد نتیجه می دهد:
(0, 3, 5)
پس از نگاهی گذرا به نمودار مثال، میتوانیم ببینیم که کوتاهترین مسیر بین 0
و 5
است در واقع (0, 3, 5)
. اگرچه، شما همچنین می توانید پیمایش کنید (0, 2, 5)
و (0, 4, 5)
. این مسیرهای جایگزین اساساً همان فاصله هستند (0, 3, 5)
– با این حال، روش مقایسه گره ها توسط BFS را در نظر بگیرید. از آن “اسکن” می کند چپ به راست و 3
اولین است node روی سمت چپ لیست مجاورت که به 5
، بنابراین این مسیر به جای بقیه طی می شود.
این یکی از ویژگی های BFS است که می خواهید پیش بینی کنید. از چپ به راست جستجو می کند – و نمی خواهد یک مسیر به همان اندازه معتبر را پیدا کنید اگر “بعد از” مسیر اول پیدا شود.
توجه داشته باشید: مواردی وجود دارد که در آن مسیری بین دو گره پیدا نمی شود. این سناریو برای قطع شده نمودارها، که در آن حداقل دو گره وجود دارد که توسط یک مسیر به هم متصل نیستند.
در اینجا یک نمودار قطع شده به نظر می رسد:
اگر بخواهیم یک مسیر بین گره ها را جستجو کنیم 0
و 3
در این نمودار، آن جستجو ناموفق خواهد بود و یک مسیر خالی برگردانده می شود.
عرض-اول پیاده سازی – پیمایش نمودار
عرض-اولین پیمایش یک مورد خاص از Breadth-First Search است که مسیر را طی می کند کل نمودار، به جای جستجو برای یک هدف node. الگوریتم همانطور که قبلاً تعریف کرده بودیم باقی می ماند، تفاوت در این است که هدف را بررسی نمی کنیم. node و ما نیازی به یافتن مسیری نداریم که به آن منتهی شود.
این پیاده سازی را به طور قابل توجهی ساده می کند – اجازه دهید فقط print از هر کدام node برای به دست آوردن شهودی از روش عبور آن از گره ها عبور می شود:
def bfs_traversal(self, start_node):
visited = set()
queue = Queue()
queue.put(start_node)
visited.add(start_node)
while not queue.empty():
current_node = queue.get()
print(current_node, end = " ")
for (next_node, weight) in self.m_adj_list(current_node):
if next_node not in visited:
queue.put(next_node)
visited.add(next_node)
توجه داشته باشید: این روش باید به عنوان بخشی از Graph
کلاس اجرا شده قبلا
حالا بیایید نمودار مثال زیر را به شکلی که قبلا نشان داده شده است تعریف کنیم:
graph = Graph(5, directed=False)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
در نهایت، اجازه دهید کد را اجرا کنیم:
graph.bfs_traversal(0)
اجرای این کد انجام خواهد شد print گره ها به ترتیبی که BFS آنها را اسکن کرد:
0 1 2 4 3
گام به گام
بیایید کمی عمیق تر به این مثال بپردازیم و ببینیم که چگونه الگوریتم گام به گام کار می کند. همانطور که پیمایش را از ابتدا شروع می کنیم node 0
، آن را در قرار داده است visited
تنظیم و به queue
همچنین. در حالی که ما هنوز گره هایی در آن داریم queue
، اولی را استخراج می کنیم، print و همه همسایگانش را بررسی کنید.
هنگام عبور از همسایگان، بررسی می کنیم که آیا هر یک از آنها بازدید شده است یا خیر، و در غیر این صورت آنها را به آنها اضافه می کنیم queue
و آنها را به عنوان بازدید شده علامت گذاری کنید:
مراحل | صف | ملاقات کرد |
---|---|---|
شروع را اضافه کنید node 0 | (0) | {0} |
از 0 بازدید کنید، 1 و 2 را به صف اضافه کنید | (1، 2) | {0} |
از 1 بازدید کنید، 4 را به صف اضافه کنید | (2، 4) | {0، 2} |
از 2 بازدید کنید، 3 را به صف اضافه کنید | (4، 3) | {0، 1، 2} |
بازدید از 4، بدون همسایه بازدید نشده | (3) | {0، 1، 1، 4} |
بازدید از 3، بدون همسایه بازدید نشده | ( ) | {0، 1، 2، 4، 3} |
پیچیدگی زمانی
در حین عرض-اولین پیمایش، هر node دقیقا بازدید می شود یک بار، و هر شاخه نیز مشاهده می شود یک بار در صورت الف جهت دار نمودار، یعنی دو برابر اگر نمودار باشد بدون جهت. بنابراین، پیچیدگی زمانی الگوریتم BFS است O(|V| + |E|)، جایی که V مجموعه ای از گره های گراف است و E مجموعه ای است که از تمام شاخه های آن (لبه ها) تشکیل شده است.
نتیجه
در این درس، تئوری پشت الگوریتم جستجوی پهنا-اول را توضیح داده و مراحل آن را تعریف کردهایم.
ما پیادهسازی Python را برای جستجوی Breadth-First و Breadth-First Traversal به تصویر کشیدهایم و آنها را آزمایش کردهایم. روی نمودارها را مثال بزنید تا ببینید چگونه گام به گام کار می کنند. در نهایت پیچیدگی زمانی این الگوریتم را توضیح داده ایم.
منتشر شده در 1403-01-06 16:25:03