p30better
پنج شنبه 29 فروردین 1392, 13:34 عصر
سلام یک کار بسیار ضروری داریم ..
یکی این الگوریتم رو برام به زبان ویژوال سی شارپ بنویسه .. در ضمن فقط چند خطه .. آقای مدیر هم این تایپک رو پاک نکنه که خیلی ضروریه با تشکر
لینک توضیحات کامل از ویکی پدیا (http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_% D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D 9%84_%D8%B3%D8%B7%D8%AD)
توضیحات کوتاه:
http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/400px-Breadth-first-tree.svg.png (http://commons.wikimedia.org/wiki/File:Breadth-first-tree.svg?uselang=fa)
الگوریتم از ریشه شروع میکند (در گرافها و یا درختهای بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب میشود) و آن را در سطح یک قرار میدهد. سپس در هر مرحله همهٔ همسایههای رئوس آخرین سطح دیده شده را که تا به حال دیده نشدهاند بازدید میکند و آنها را در سطح بعدی میگذارد. این فرایند زمانی متوقف میشود که همهٔ همسایههای رئوس آخرین سطح قبلاً دیده شده باشند. همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گرافاند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همهٔ رئوس هدف با آن خصوصیات به ریشه نزدیکترین باشد، جستجوی سطح اول به صورت غیرخلاق عمل میکند. بدین ترتیب که الگوریتم هر دفعه همهٔ همسایههای یک رأس را بازدید کرده و سپس به سراغ رأس بعدی میرود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه مییابد که رأس هدف پیدا شود و یا احتمالاً همهٔ گراف پیمایش شود. براساس آنچه گفته شد پیادهسازی هوشمندانهٔ الگوریتم آنقدر مؤثر نخواهد بود.
از نقطه نظر عملی، برای پیادهسازی این الگوریتم از صف استفاده میشود. بدین ترتیب که در ابتدا ریشه در صف قرار میگیرد. سپس هر دفعه عنصر ابتدای صف بیرون کشیده شده، همسایگانش بررسی شده و هر همسایهای که تا به حال دیده نشده باشد به انتهای صف اضافه میشود. جزئیات پیادهسازی در ادامه خواهد آمد.
یکی این الگوریتم رو برام به زبان ویژوال سی شارپ بنویسه .. در ضمن فقط چند خطه .. آقای مدیر هم این تایپک رو پاک نکنه که خیلی ضروریه با تشکر
لینک توضیحات کامل از ویکی پدیا (http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_% D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D 9%84_%D8%B3%D8%B7%D8%AD)
توضیحات کوتاه:
http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/400px-Breadth-first-tree.svg.png (http://commons.wikimedia.org/wiki/File:Breadth-first-tree.svg?uselang=fa)
الگوریتم از ریشه شروع میکند (در گرافها و یا درختهای بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب میشود) و آن را در سطح یک قرار میدهد. سپس در هر مرحله همهٔ همسایههای رئوس آخرین سطح دیده شده را که تا به حال دیده نشدهاند بازدید میکند و آنها را در سطح بعدی میگذارد. این فرایند زمانی متوقف میشود که همهٔ همسایههای رئوس آخرین سطح قبلاً دیده شده باشند. همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گرافاند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همهٔ رئوس هدف با آن خصوصیات به ریشه نزدیکترین باشد، جستجوی سطح اول به صورت غیرخلاق عمل میکند. بدین ترتیب که الگوریتم هر دفعه همهٔ همسایههای یک رأس را بازدید کرده و سپس به سراغ رأس بعدی میرود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه مییابد که رأس هدف پیدا شود و یا احتمالاً همهٔ گراف پیمایش شود. براساس آنچه گفته شد پیادهسازی هوشمندانهٔ الگوریتم آنقدر مؤثر نخواهد بود.
از نقطه نظر عملی، برای پیادهسازی این الگوریتم از صف استفاده میشود. بدین ترتیب که در ابتدا ریشه در صف قرار میگیرد. سپس هر دفعه عنصر ابتدای صف بیرون کشیده شده، همسایگانش بررسی شده و هر همسایهای که تا به حال دیده نشده باشد به انتهای صف اضافه میشود. جزئیات پیادهسازی در ادامه خواهد آمد.