موضوع مقاله: الگوریتم ارسال-برچسب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم ارسال-برچسب | مقدمه: الگوریتم ارسال-برچسب یکی از کارآمدترین الگوریتم‌ها برای محاسبهٔ یک مسئله بیشینه جریان است. | ## بخش 1: الگوریتم ارسال-برچسب | الگوریتم عمومی دارای پیچیدگی زمانی است، در حالی که پیاده‌سازی آن با قانون شیوهٔ رأس‌ها به صورت FIFO دارای زمان اجرای ، با شیوهٔ انتخاب فعال‌ترین رأس دارای پیچیدگی زمانی و با پیاده‌سازی با کمک داده‌ساختار درخت پویای ترجان و اسلیتور دارای زمان اجرای است. می‌خواهیم بیشترین میزان جریان را که می‌شود درون شبکه از s به t فرستاد را بیابیم. بعد از هر گام الگوریتم، جریان یک پیش جریان (به انگلیسی: preflow) است که شرایط زیر را دارد: . توجه داشته باشید که آخرین وضعیت یک پیش‌جریان از وضعیت متناظر برای یک جریان مجاز در یک در یک شبکه جریان منظم، مجزاست. پذیر باشد که ارتفاع (به انگلیسی: height) را به گره‌های هر جریان مجاز اختصاص دهیم، و ، و اگر یک جریان مثبت از u به v وجود داشت، . حال که ما ارتفاع گره‌ها را تعیین کردیم، جریان در شبکه به حرکت در می‌آید (مانند جریان آب بر روی پستی و بلندی). بر خلاف الگوریتم‌هایی مانند فورد-فالکرسون، جریان در طول شبکه، لزماً یک جریان مجاز در اجرای الگوریتم نیست. به‌طور خلاصه، ارتفاع‌های گره‌ها (به جز s و t) تعیین شده‌اند، و جریان بین گره‌ها فرستاده می‌شود، تا زمانی که تمام جریان‌های ممکن به t برسند. سپس می‌توانیم افزایش ارتفاع گره‌های درونی را ادامه دهیم تا تمام جریان‌هایی که درون شبکه رفته‌اند ولی به t نرسیده‌اند، به سمت s بازگردند. | ## بخش 2: الگوریتم ارسال-برچسب | یک گره قبل از پایان کار می‌تواند به ارتفاع برسد، بنا بر این، طولانی‌ترین مسیر ممکن که به s بر می‌گردد ولی شامل t نیست دارای طول است و . برای این کار لازم است که برای هر گره، بدانیم از زمان آخرین relabel کردن کدام گره‌ها بررسی نشده‌اند. الگوریتم برچسب رو به جلو : الگوریتم ارسال برچسب به ما اجازه می‌دهد که عملیات اصلی را با هر زمان اجرایی بدست آوریم. اکنون می‌خواهیم الگوریتم برچسب رو به جلو که یک الگوریتم ارسال-برچسب با زمان اجرای را بررسی کنیم که به همان خوبی زمان اجرای و بهتر برای شبکه‌های چگال است. در این الگوریتم فهرستی وجود دارد که شامل همهٔ رأس‌های شبکه به جز مبدأ و مقصد است. این الگوریتم فهرست را پیمایش می‌کند و یک راس را می‌گیرد و آن را تخلیه می‌کند و عملیات ارسال بر چسب را تا زمانی که آن راس دیگر افزایش ارتفاع ندارد روی آن انجام می‌دهد. زمانی که راسی برچسب‌گذاری شد به جلوی فهرست می‌رود و الگوریتم کار پیمایش را از اول شروع می‌کند. تخلیه راس سرشار u با push کردن همهٔ جریان‌های اضافی اش در میان یال‌های مجاز به رأس‌های همسایه تخلیه می‌شود. روند پیشروی این الگوریتم نشان می‌دهد که فهرست همسایه‌های رأس‌های درون فهرست N[u l) برای هر راسی درست شده‌است. | ## بخش 3: الگوریتم ارسال-برچسب | این الگوریتم به این صورت عمل می‌کند که: خط ۱ ارتفاع و جریان اولیه را مقدار دهی می‌کند. خط ۳ و ۴ آخرین اشاره گر از هر راس u را به اولین راس در فهرست همسایه‌های u مقدار دهی می‌کند. هر زمان در داخل حلقه راس u در خط ۸ تخلیه می‌گردد اگر که u طبق الگوریتم تخلیه برچسب‌گذاری شده بود در خط ۱۰ به ابتدای فهرست باز می‌گردد چرا که همان‌طور که قبلاً گفته شده بود زمانی که برچسب‌گذاری می‌شود ارتفاعش افزایش می‌یابد و اگر ارتفاع افزایش یافته بود آن راس به ابتدای فهرست بر می‌گردد. 600px 600px در قسمت a شبکهٔ جریان‌ها قبل از اولین تکرار در حلقه نشان داده شده‌است. ۲۶ مقدار جریان از مبدأ s خارج شده در سمت راست فهرست L که شامل همهٔ رأس‌ها غیر از مبدأ و مقصد است نشان داده شده که در حالت اول راس u را x می‌گیریم زیر هر راس در فهرست L رأس‌های همسایه قرار داده شده‌است. در قسمت b پس از x راس بعدی که تخلیه می‌شود راس y است شکل عمل تخلیهٔ y را با جرئیات نشان داده. پس راس x دوباره تخلیه می‌شود x برچسب‌گذاری نمی‌شود پس در فهرست باقی می‌ماند و به سر فهرست نمی‌آید. در قسمت d راس z راس x را دنبال می‌کند پس تخلیه می‌شود و به ارتفاع ۱ برچسب‌گذاری می‌شود و همهٔ ۸ مقدارش به راس t می‌رود سپس به ابتدا ی فهرست l می‌رود چرا که برچسب‌گذاری شده حال در قسمت e راس y راس z را دنبال می‌کند پس راس y باید تخلیه شود ولی چون هیچ جریان اضافی ندارد راس x تخلیه می‌شود و y سر جایش در فهرست باقی می‌ماند. | ## جمع‌بندی | ولی چون x هم جریانی ندارد آن هم در فهرست می‌ماند و این الگوریتم به ته فهرست L می‌رسد و تمام می‌شود.