برنامه نویسی نمودار پویا


Error

در راه حل هایی که از برنامه نویسی پویا استفاده می کنند، ترتیب محاسبه دینامیک مهم است (لازم است مقادیری که مقدار فعلی به آن بستگی دارد قبلا محاسبه شود).
بنابراین، در صورت لزوم استفاده از برنامه‌نویسی پویا بر روی گراف‌های غیر چرخه‌ای جهت‌دار، لازم است در ابتدا یک مرتب‌سازی توپولوژیکی از نمودار ساخته شود. سپس دینامیک را با مرتب‌سازی راس‌ها به ترتیب مرتب‌سازی توپولوژیکی ساخته‌شده محاسبه کنید (بسته به مسئله، ترتیب پیمایش می‌تواند از منبع به سینک یا بالعکس باشد).
 
 

اگر نمودار شامل چرخه باشد (هیچ ترتیب توپولوژیکی وجود ندارد)، دو ترفند می تواند کمک کند:

1) دینامیک n بار را محاسبه کنید، که در آن n تعداد رئوس نمودار است (بر اساس قیاس با الگوریتم فورد-بلمن). اما این امر مجانبی را افزایش می دهد و به ندرت کارآمد است.

2) چگالش گراف را بسازید. برای هر جزء قویاً متصل گراف اصلی، مسئله را جداگانه حل کنید. نمودار متراکم غیر چرخه‌ای است و برای آن می‌توانید از رویکرد استاندارد با مرتب‌سازی توپولوژیکی استفاده کنید، در حالی که به عنوان مقادیر راس، مقادیر محاسبه‌شده برای مؤلفه‌های به‌شدت متصل را استفاده کنید. این روش عمدتا استفاده می شود.