الگوریتم کراسکال - ساخت و ساز از یک چارچوب مطلوب

در اوایل قرن 19 هندسه دان یاکوب اشتاینر از برلین مجموعه ای وظیفه نحوه اتصال سه روستا به طوری که آنها طول بود کوتاه ترین. بعدها، او خلاصه مشکل: آن است که لازم برای پیدا کردن یک نقطه در یک هواپیما، فاصله از آن به n دیگر نقاط شده است. حداقل. در قرن 20، آن را همچنان به کار بر روی این موضوع. آن را به چند نکته و اتصال آنها به گونه ای است که فاصله بین آنها کوتاه ترین بود تصمیم گرفته شد. این همه یک مورد خاص از مشکل مورد مطالعه است.

"حریص" الگوریتم

الگوریتم کراسکال به الگوریتم "حریص" (همچنین به نام شیب) اشاره دارد. جوهر از آن ها - بالاترین پیروزی در هر مرحله. نه همیشه، الگوریتم "حریص" بهترین راه حل برای این مشکل فراهم می کند. یک تئوری وجود دارد، نشان می دهد که نسبت به خود وظایف خاص آنها را به راه حل مطلوب. این نظریه matroids است. الگوریتم کراسکال به این گونه مسائل اشاره دارد.

پیدا کردن اسکلت حداقل وزن

الگوریتم بازدید سازه شمارش قاب مطلوب. مشکل از آن به شرح زیر است. دن گراف بدون جهت و بدون لبه های موازی و حلقه ها، و مجموعه ای از لبه تابع وزن w، که اختصاص شماره به هر یال e داده شده است - دنده وزن - W (ه). وزن هر زیر مجموعه ای از کثرت از دنده مجموع وزنهای یالهای آن است. نیاز به پیدا کردن اسکلت یک وزن کوچک است.

توصیف

الگوریتم کراسکال کار می کند. اول، تمام یالهای گراف اولیه در چیدمان صعودی چیدمان از وزن مرتب شده اند. در ابتدا، قاب هیچ گونه دنده نیست، بلکه شامل تمام رئوس. پس از مرحله بعدی از الگوریتم به بخش در حال حاضر ساخته از لاشه است، که یک جنگل پوشا، یک لبه اضافه شده است. این است که به دلخواه انتخاب نشده است. همه یالهای گراف، متعلق به قاب نیست، می تواند قرمز و سبز نامیده می شود. بالای هر یک از لبه های قرمز در جزء همان زیر اتصال جنگل ساخت و ساز، و تاپس سبز - متفاوت است. بنابراین، اگر شما را به لبه قرمز را اضافه کنید، یک چرخه وجود دارد، و اگر سبز - به عنوان پس از این مرحله دریافت قطعات چوب متصل کمتر از یک خواهد بود. بنابراین، ساخت و ساز و در نتیجه می تواند بدون لبه قرمز را اضافه نمی کند، اما هر یال سبز می توانند اضافه به جنگل. و می افزاید: یک یال سبز با حداقل وزن. در نتیجه یک چارچوب حداقل وزن.

اجرا

معنی جنگل فعلی اف این تقسیم مجموعه ای از رئوس در زمینه اتصال (اشکال اتحادیه خود را F، و آنها متلاشی شدن). در هر دو لبه از رئوس قرمز آنها در یک قطعه قرار دارند. قسمت (X) - تابع است که برای هر رأس x یک بخشی از آن نام گرداند، آن را متعلق به x. متحد (X، Y) - یک روش است که ایجاد یک پارتیشن جدید، متشکل از ترکیب بخش هایی از x و y و تمامی قطعات دیگر. بگذارید n - تعداد یال. همه این مفاهیم در الگوریتم کروسکال گنجانده شده است. پیاده سازی:

1. ترتیب تمام یالهای گراف از 1 به وزن صعودی n ام. (هوش مصنوعی، بی - بالای لبه با تعداد من).

2. برای i = 1 تا n را انجام دهد.

3. X: = قسمت (AI).

4. Y: = قسمت (دو).

5. اگر X آیا نمی برابر y سپس متحد (X، Y)، شامل با لبه F من تعداد.

صحت

اجازه دهید T - فریم از نمودار اصلی ساخته با استفاده از الگوریتم کروسکال و S - قاب دلخواه آن است. ما باید ثابت کند که W (T) است بزرگتر از عرض (S).

اجازه بدهید M - تکثر باله S، P - تکثر باله T. اگر S است به T برابر نیست، پس از آن است و همکاران قاب دنده T، متعلق به اس اس و همکاران نمی متصل چرخه، آن را به نام C. C حذف از هر ES لبه، متعلق وجود دارد S. ما به دست آوردن یک قاب جدید، به دلیل لبه ها و رئوس همان است. وزن آن است بزرگتر از عرض (S)، از W (ET) دیگر W (ES) در یک الگوریتم کروسکال قدرت. این عملیات (جایگزین دنده T S در دنده) تکرار خواهد شد تا زمانی که دریافت T. وزن هر قاب دریافت پس از آن است که بیشتر از وزن قبلی، که نشان میدهد که W (T) است بزرگتر از عرض (S).

استحکام الگوریتم کروسکال زیر از قضیه از رادو-ادموندز در matroids.

نمونه های نرم افزار الگوریتم کروسکال

نمودار دن با گره A، B، C، D، E و دنده (A، B)، (A، E)، (B، C)، (B، E)، (C، D)، (C، E) ، (D، E). وزنهای یالهای در جدول و در شکل نشان داده شده. در ابتدا، جنگل ساخت و ساز F شامل تمام رئوس گراف و بدون هیچ گونه دنده است. الگوریتم کروسکال اول اضافه دنده (A، E)، از وزن پایین ترین بود، و رئوس A و E در اجزای مختلف هستند اتصال چوب F (دنده (A، E) به رنگ سبز است)، سپس دنده (C، D)، به دلیل که این لبه پایین ترین وزن یالهای گراف، به F متعلق است، و آن را به رنگ سبز است، پس از آن به همان دلایلی است که به لبه اضافه (A، B). اما لبه (ب، ه) به تصویب می رسد، حتی اگر او و حداقل وزن از لبه باقی مانده، به دلیل آن قرمز رنگ است: راس B و E متعلق به همان قطعه را از اتصال به جنگل F، است که، اگر ما به F اضافه کردن لبه (ب، ه)، تشکیل می شود چرخه. سپس افزود لبه سبز (ب، ج) لبه قرمز، به تصویب می رسد (C، E)، و سپس D، E. بنابراین، لبه ها اضافه پی در پی (A، E)، (C، D)، (A، B)، (B، C). از nihera قاب مطلوب و متشکل از نمودار اصلی است. بنابراین در این مورد این عمل یک الگوریتم کروسکال. به عنوان مثال نشان داده شده است.

شکل نشان می دهد یک نمودار، که متشکل از دو جزء متصل. خطوط جسورانه نشان دنده قاب بهینه (سبز) با استفاده از الگوریتم کروسکال ساخته شده است.

تصویر بالا نشان می دهد نمودار اصلی، و پایین - اسکلت حداقل وزن، ساخته شده برای او با استفاده از الگوریتم.

دنباله ای از اضافه دنده (1.6)؛ (0،3)، (2،6) و یا (2،6)، (0،3) - مهم نیست؛ (3،4)؛ (0،1)، (1،6) و یا (1،6)، (0،1)، همچنین مراقبت (5،6).

الگوریتم کراسکال کاربرد عملی پیدا می کند، برای مثال، برای بهینه سازی ارتباطات واشر، جاده ها در محلات جدید مسکن و املاک در هر کشور، و همچنین در موارد دیگر.