Payamvdn/NorthPersian_fa_wiki huggingface dataset:
تعداد کمی به عنوان یک درصد کمی از کالری مصرفی کل است. این که آیا این اثر با توجه به ماهیت آروسیک به طور خود به خودی باعث می شود از میزان چسبندگی پلاکت خون کاسته شود ویا به علت درصد بالایی از آلفا لینولنیک اسید ویا به ترکیبی از خواص روغن تازه آفتابگردان تصفیه شده است. این واقعیت که بیماری عروق کردند بدون علامت اولیه در گروه های مختلف و گونه های مختلف روغن خردل وجود ندارند؛ و این فرضیه که روغن خردل موجب اضافه وزن می شود است. استفاده از روغن خردل در جوامع سنتی برای ماساژ نوزاد استفاده می شود اما در مطالعه ایی به عنوان اثرات آسیب پذیری و نفوذپذیری پوست شناخته شده است. مطالعات دیگر بر روی نمونه های بزرگترشان داده اند که ماساژ با روغن خردل موجب بهبود وزن و میانگین قد نوزاد در مقایسه با نوزادان بدون ماساژ می شود. البته روغن کنجد گزینهٔ بهتری برای این استفاده است. اطلاعات غذایی. با توجه به USDA ۱قاشق غذاخوری روغن خردل شامل: ۱)۱۲۹٪ کالری ۲)۱۴٪ چربی ۳)۰٪کربوهیدرات ۴)۰٪لیپید ۵)۰٪پروتین راهکار. نمک خردل را می توان از طریق زیر تهیه کرد خردل و نمک و فلفل و دانه های خردل با آب مخلوط می کنیم و سپس با سرکه یا مایع دیگر مخلوط
کرده. تحت این شرایط یک واکنش شیمیایی بین آنزیم myrosinasc و گلوکزینولات شناخته شده به عنوان sinigrin از دانه های خردل سیاه و سفید (برسیکا نیگرا) یا خردل قهوه ای (جوسیا کلزا) که موجب تولید آسیل ایزو تیو سینات می شود. توسط تقطیر می توان اسانس بسیار تیز مزه تولید کرد. گاهی روغن فرار خردل هم نامیده می شود که حاوی ۹۲٪ تیوسیانات است که منشأ مزهٔ تند است که با توجه به فعال شدن قسمت TRPV۱ در نورون های حسی حس می شود. ایزوتیوسیانات در گیاه به عنوان یک دفاع در برابر گیاهخواران عمل می کند. از آنجایی که isthiocyarate ahyl موجود این نوع روغن خردل سمی است و موجب تحریک پوست و غشاهای مخاطی می شود. در مقادیر بسیار ناچیز که اغلب توسط صنایع غذایی برای بهبود طعم استفاده می شود. در شمال ایتالیا به عنوان مثال آن را در نمک و فلفل و میوه ای به نام mostarda استفاده می شود. این نیز برای دفع سگ ها و گربه ها استفاده می شود. آن را نیز به الکل طبیعی می زنند برای تغییر در ماهیت چیزی این برای مصرف انسانی نامناسب و مضر است. شماره CAS: ۷–۴۰–۸۰۰۷ است و شماره CAS برای آلیل ایزو تیوسینات ۵۷–۵۶–۷ است. روغن آووکادو. روغن آووکادو نوعی روغن خوراکی فش
رده از میوه ای آمریکایی به نام آووکادو است. به عنوان یک ماده اولیه در پخت وپز در غذاها استفاده می شود و همچنین برای روغن کاری در محصولات آرایشی برای ایجاد خاصیت مرطوب کنندگی مورد استفاده قرار می گیرد. این روغن چه در حالت تصفیه نشده و به خصوص در حالت تصفیه شده معمولاً دارای نقطه دود بالایی است. نقطه دود در حالت تصفیه نشده برابرست با ۴۸۲ درجه فارنهایت یا ۲۵۰ درجه سانتیگراد و دود روغن تصفیه شده می تواند از این مقدار یعنی ۴۸۲ درجه فارنهایت یا ۲۵۰ درجه سانتیگراد پایین تر هم بیاید. موارد استفاده. برداشت می شود در فصل هایی که آووکادو موجود نیست بر روی روغن زیتون و فراورده های آن کار می شود تا فصل برداشن آووکادو از راه برسد. ۵)روغن آووکادو یک روغن بکر بوده و هست این روغن همچنین به منظور استفاده در لوازم آرایشی نیز استخراج می شود زیرا جذب پوستی بالایی دارد و سریعاً جذب پوست می شود. ۶)خشک کردن بخش گوشتی آووکادو تا آنجایی که امکان داشته باشد ادامه می یابد لازم است ذکر شود که میزان آب در قسمت گوشتی این میوه ۶۵٪ است. روغن آووکادو به صورت سنتی و با استفاده از حلال در دماهای بالا استخراج می شود. خواص. روغن خام از نوع هاس آو
وکادو دارای میزان عطر و طعم خاص و شخصی است ونیز دارای میزان اسید چرب اشباع شده و نقطه دود بالایی است(۲۸۲F یا ۲۵۰&lt;) که این روغن را دارای خاصیت خوبی برای سرخ کردن می کند. روغن سرد فشرده شده هاس رنگ زمرد سبز درخشانی دارد زمانی که استخراج می شود که این رنگ به علت سطوح بالایی کلروفیل و کاروتنوئید موجود در روغن استخراج شده است. روغن سرد فشرده شده آووکادو به علت داشتن طعم و عطر شبیه طعم کره /قارچ توصیف شده است. در واریته های دیگر ممکن است عطر و طعم های متفاوتی با میزان طعم قارچ بیشتر و عطر کمتر باشد. همچنین در مقایسه با روغن زیتون برای پخت پز دارای خواص مهمتری است. دارای یک مقطع چربی اشباع نشده مشابه است که کمک می کند تا روغن حفاظت شود در برابر اکسیداسیون در حین پختن. روغن آووکادو به طور طبیعی دارای خاصیت کمی اسیدی است که این خاصیت به افزایش نقطه دودش کمک می کند. روغن آووکادوی خام که با رنگ زمرد سبز (از آووکادوی دارای کلروفیل) با خیال راحت می تواند حرارت داده شود تا درجه حرارت ۳۷۵ درجه فارنهایت یا ۱۲۱ درجه سانتیگراد و شبیه روغن زیتون با کیفیت بالا است. روغن تصفیه شدهٔ آووکادو با نقطه دود بالاتر از ۵۰۰ درجه فارنها
یت می تواند تا با اطمینان بیشتری تا هر درجه حرارتی در پخت پزها/ سرخ کردن زیاد / کباب کردن/خشک کردن و در روغن سرخ کردنی استفاده می شود. روغن آووکادو نسبتاً روغن جدیدی در دنیای آشپزی است و اغلب در رابطه با نقطه دودش تصورات غلطی موجود است. نکته قابل توجه این است که این روغن مانند سایر روغن ها این خاصیت را دارد که هرچه میزان تصفیه شدن اش بیشتر باشد نقطه دودش بیشتر است. روغن خام آووکادو به میزان قابل توجهی نقطه دود بالایی نسبت به روغن زیتون دارد. روغن آووکادو از معدود روغن های گاهی است که از دانه استخراج نمی شود و از قسمت گوشتی اطراف هستهٔ آووکادو حاصل می آید. روغن های گیاهی. روغن های نباتی (گیاهی) را از گیاهان یا دانهٔ آن ها استخراج می کنند. برخی روغن های گیاهی از جمله روغن دانه شلغم روغنی یا روغن پنبه دانه، بدون انجام عملیات مخصوص بر روی آنها، برای مصرف انسان مناسب نیستند. روغن های نباتی همچون دیگر انواع چربی، از استرهای گلیسرین و همچنین از مخلوط انواع مختلف اسید چرب تشکیل یافته اند. این روغن ها در آب حل نمی شوند، اما در برخی حلال های آلی، محلول هستند. منبع روغن گیاهی معمولاً روغن های نباتی رایج را از دانه گیاها
ن زیر به دست می آورند: دیگر انواع روغن های گیاهی. از میان این روغن ها، اغلب افراد از روغن زیتون، روغن دانه آفتاب گردان و روغن نخل (که در دمای اتاق جامد است) برای تهیه غذاهای خود استفاده می نمایند. نقطه دود. روغن با نقطه دود بالا، یعنی روغنی که قبل از اینکه سطح آن تولید دود کند بتوان تا درجه بالایی حرارت داد. وقتی روغن به نقطه دود می رسد، شروع به تولید کف می کند و ماده ای سمی به نام آکرولئین تولید می شود که چشم را می سوزاند. نقطه دود روغن های مختلف. نقطه دود روغن مخصوص سرخ کردنی بالاست و به راحتی دود نمی کند. همچنین جذب کمتری به مواد غذایی داشته و موجب کاهش دریافت چربی می شود. معایب مصرف روغن های گیاهی. در گذشته از روغن های حیوانی برای تغذیه استفاده می شد؛ این روغن ها دارای مقدار زیادی اسیدهای چرب اشباع و کلسترول بودند و سبب ایجاد بیماری های مختلف قلبی و عروقی می شدند، به همین دلیل روغن های گیاهی جایگزین این روغن ها شدند اما زیاده روی در مصرف روغن های گیاهی نیز که امروزه مشکل تمامی جوامع است دارای مضرات قابل توجهی است. نسبت مناسب اسید چرب ۶امگا/۳امگا در بدن انسان ۳/۱ است در حالی که این نسبت در روغن های گیاهی ب
ه طور متوسط حدود ۱۵/۱ است و این یکی از مهم ترین عوامل ایجاد بیماری هایی است که امروزه در بین جوامع انسانی شیوع دارند، زیرا نسبت اسید چرب امگا- ۶ به امگا- ۳ امروزه در اثر مصرف زیاد روغن های گیاهی حاوی امگا-۶ چون روغن آفتابگردان و ذرت در رژیم غذایی انسان ها به حدود ۱۶/۱ رسیده است که سبب ایجاد بیماری های قلبی عروقی، سرطان ها به خصوص سرطان روده بزرگ و سینه و بیماری های مربوط به ضعف سیستم ایمنی بدن می-شود. در آزمایش های انجام گرفته نشان داده شده است، نسبت های بالای امگا-۳ به امگا -۶ (در اثر مصرف روغن بزرک و ماهی) سبب کاهش تکثیر سلول های سرطانی در بیماران مبتلا به سرطان روده بزرگ، سرطان سینه و کاهش بیماری [آسم و آرتریت] روماتوئید می شود (و از طرف دیگر افزایش میزان امگا-۳ رژیم غذایی، به وسیله دانه های روغنی کتان سبب کاهش قابل ملاحظه مرگ های ناگهانی حاصل از بیماری های قلبی و کاهش سکته های قلبی غیر کشنده می شود. همین طور در یک مطالعه انجام گرفته در زندان های بریتانیا با افزایش نسبت امگا-۳ به امگا-۶ در رژیم غذایی زندانیان، میزان خشونت این زندانیان ۳۷ درصد کاهش یافت نسبت اسید چرب امگا-۳ به امگا-۶ در روغن های خوراکی مختل
ف عبارتند از درحقیقت راه منطقی مبارزه با این مشکلات رفتن به سمت جایگزینی مصرف غذاهای آب پز به جای سرخ کردنی ها و مصرف زیاد غذاهای سرشار از امگا-۳ مانند انواع ماهی ها و غذاهای دریایی و روغن گیاه بزرک (کتان روغنی) یا حتی الامکان مصرف روغن کلزا که بدین لحاظ از سایر روغن ها متعادل تر است. شیوه استخراج. روش جدید استخراج روغن از دانهٔ گیاهان، به طریق شیمیایی و با استفاده از حلال های خاصی می باشد. این روش، محصول بیشتری تولید می کند، با صرفه تر است و سریع تر هم انجام می پذیرد. روشی دیگر برای استخراج روغن از دانه گیاهان، بدون استفاده از حلال صورت می گیرد و به استخراج فیزیکی معروف است. در این روش روغن را با روش های مکانیکی فشردن، استخراج می نمایند. از این روش معمولاً برای تهیه روغن های خوراکی استفاده می شود. تمامی روغن ها به روش مکانیکی یا فشردن روغن گیری می شوند به جز روغن خراطین که شیوه ای متناسب با خودش را دارد. تهیهٔ روغن خراطین به دو صورت (سنتی و صنعتی) انجام می شود. بدین صورت که برای تهیه به روش سنتی باید ابتدا کرم خاکی خشک شده یا پودر این کرم را تهیه کرد و سپس با استفاده از روغن زیتون یا کنجد اقدام به روغن گیری
کرد. در روش صنعتی نیز روغن به صورت مستقیم از طریق دستگاه های روغن گیری از کرم خراطین (ایزینیا فتیدا) تهیه می شود. منابع. "Why Is Avocado Oil Good For The Skin?". Livestrong Foundation. 2011-03-31. Retrieved 2013-07-13. "What is unrefined, extra virgin, cold pressed avocado oil?". Unlu, Nuray Z. ; Bohn, Torsten; Clinton, Steven K. ; Schwartz, Steven J. (۱ مارس ۲۰۰۵). "Carotenoid Absorption from Salad and Salsa by Humans Is Enhanced by the Addition of Avocado or Avocado Oil". Journal of Nutrition (The American Society for Nutritional Sciences) 135 (3): 431–436. "Easy Avocado Oil Uses for Natural Skincare and Healthy Cooking". OilyOily. Retrieved 7 September 2013. "What is unrefined, extra virgin cold-pressed avocado oil?". American Oil Chemists' Society. April 2010. Retrieved 2013-07-13. "Avocado oil". Perdue University Center for New Crops and Plants Products. 1999-02-18. Retrieved 2013-07-13.
لان کلمبیا شرکت هواپیمایی کلمبیایی است، که در سال ۱۹۸۱ تأسیس شد و در حال حاضر به عنوان زیرمجموعه ای از خطوط هوایی لان ایرلاینز، روزانه به ۳۱ مقصد، در آمریکای شمالی و جنوبی، پروازهای مستقیم دارد. دفتر مرکزی شرکت لان کلمبیا در شهر بوگوتا، کلمبیا قرار دارد و فرودگاه بین المللی ال دورادو و فرودگاه انریکه اولایا هررا، قطب های این شرکت هواپیمایی به شمار می آیند. شرکت لان کلمبیا در حال حاضر در ناوگان هوایی خود، دارای ۲۲ فروند هواپیمای جت مسافربری می باشد.
فرض می کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان گذاری استاندارد را استفاده می کنیم. برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را ببینید. در اینجا فقط مهمترین ها را ذکر می کنیم. مسئله روند کمترین هزینه به این صورت تعریف می شود: گراف جهت دار formula_1 با گنجایش formula_2 داده شده است: formula_3 ، سنگینی formula_4 و ارزش تعادل formula_5، formula_6 را به عنوان یک روند کمترین روند هزینه بیابید، به طوری که تابع formula_7 با formula_8 برای همهٔ formula_9 های عضو formula_10 و formula_11برای همهٔ formula_12 های عضو formula_13 از قبیل formula_14 که کمترین مقدار یا همان مینیموم می باشد formula_15مجموعه ای از ورودی های را تشکیل می دهد. راس formula_12 باقی می ماند. واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند formula_6 می تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین هزینه حل می شوند. نمونه داده شده formula_18 از مسئله روند کمترین هزینه و روند formula_7 با formula_20 برای همهٔ formula_21، ظر
فیت باقی ماندهٔ یال formula_21 به وسیله formula_23 تعریف می شود. علاوه بر این، ما یک یال جدید formula_9 از formula_25 به formula_12 برای هر یال formula_27 در نظر گرفته ایم و formula_28 و formula_29 تعریف کرده ایم. باقی مانده گراف formula_30 شامل همه بال ها ( قدیمی و جدید) با ظرفیت باقی مانده مثبت می باشد. معروف است که روند formula_6 از formula_32 بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در formula_30 وزن منفی نداشته باشد. دیاگراف formula_1 داده شده با وزن formula_4، یک ذخیره امکانپذیر در formula_36 است، تابع formula_37 به این صورت که هزینه کاهش یافته formula_38 است که برای هر formula_9 نامنفی عبارت formula_40 برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. این توسط کوتاه ترین راه محاسبه منبع واحد قطعی و تصمیم گرفته می شود. روند داده شدهformula_41 با formula_20 و ذخیره formula_43، یک گراف مجاز تعریف می کنیم که تمام یال های formula_30 که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با formula_45 معنی می کنیم. اگر formula_3
2 یک روند formula_6 بهینه باشد( برای بعضی از formula_6ها) و formula_49 یک ذخیره امکانپذیر در formula_30 باشد، پس مارپیچ است. 1- مسئله گردش با کمترین هزینه. ورودی های مسئله عبارتند از: هدف: یافته جریان formula_55 است کهformula_56 را مینیمم می کند به طوری که: formula_57 formula_58 تعریف 1: یک گردش formula_32 شرایط زیر را ارضا می کند. در این تعریف جدید، جریان در قوس اولیه formula_63 شرط formula_64 را ارضا می کند و هر واحد جریان هزینه formula_65 را تحمیل می کند. جریان در قوس معکوس formula_66 شرط formula_67 را ارضا کرده و هزینه formula_68 را برای هر واحد جریان تحمیل می کند. هزینه کل برای دو یال با جریان formula_32 برابر formula_70 است. بنابراین بهینه سازی هزینه کل برای این گراف جدید معادل بهینه سازی هزینه کل برای گراف اولیه است. برای یک جریان formula_32 در گراف formula_1 گراف باقی مانده formula_73 را گرافی تعریف می کنیم که مجموعه یال های آن عبارتند از: formula_74 کران بالای formula_75 را برای یال formula_76 تعریف می کنیم. واضح است که formula_77 تعریف 2: یک پتانسیل تابعی است به صورت formula_78 تعریف 3: فرض کنید تاب
ع پتانسیل formula_79 داده شده است. هزینه کاهش یافته را به صورت زیر تعریف می کنیم: formula_80 آنگاه داریم:&lt;br&gt; formula_81 تعریف 4: هزینه یک دور formula_82 برابر است با: formula_83 تئوری 1: موارد زیر با هم معادلند. 2- الگوریتم حذف یک دور. تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می شود. این الگوریتم به صورت زیر است. فرض کنید که formula_32 یک گردش شدنی باشد.تا وقتی که formula_89 شامل دور منفی formula_82 است. formula_82 را حذف کرده و formula_32 را به روز رسانی کن.صحت الگوریتم فوق از تئوری بالا نتیجه می شود. اگر هزینه ها و ظرفیت ها، هر دو صحیح باشند، جریان بهینه formula_32 موجود است به نحوی که formula_63 برای هر formula_95 صحیح است. فرض کنید: formula_96 formula_97 بنابراین هر گردش شدنی دارای هزینه حداکثری formula_98 و هزینه حداقلی formula_99 است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می دهد، برای یافتن یک گردش بهینه به حداکثر formula_100 حذف نیاز است. برای رسیدن به این نتیجه گیری که الگوریتم فوق شبه چندجمله ای است، به دو مورد زیر نیاز داریم. 3- حذف دور با کمترین هزینه
متوسط. با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می توان یک الگوریتم با زمان چندجمله ای به دست آورد. تعریف 5: فرض کنید که هزینه متوسط دور formula_82 برابر با formula_104 باشد که formula_105 هزینه دور و formula_106 تعداد یال های موجود در formula_82 است. تعریف 6: فرض کنید گردش formula_32 داده شده باشد و formula_109 هزینه دور با کمترین هزینه متوسط باشد. formula_110 می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله ای به دست آورد. اکنون می توانیم الگوریتم زیر را بیان کنیم. فرض کنید formula_32 یک گردش باشد تا زمانی که formula_112 دور formula_82 با کمترین هزینه متوسط را حذف کن. formula_32 را به روز رسانی کنشرط formula_112 معادل داشتن یک دور با هزینه منفی در formula_89 است. برای داشتن یک الگوریتم با زمان چندجمله ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله ای پیدا کنیم. برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می کنیم. تعریف7: یک گردش formula_32، formula_118-بهینه است اگر تابع پتانسیل formula_79 موجود باشد که برای هر formula_76 داشته باشیم formula_121 واضح
است که formula_32، 0-بهینه است؛ اگر و تنها اگر formula_32 یک گردش با کمترین هزینه باشد. برای هر گردش، formula_32، formula_125-بهینه است. زیرا اگر برای هر formula_126 قرار دهیم formula_127؛ برای هر formula_76 داریم formula_129. تعریف 8: formula_130 کمترین formula_118 است که formula_32، formula_118- بهینه باشد. دو مقدار formula_130 و formula_109 به شکل جالبی به هم مرتبطند. تئوری 2: برای یک گردش formula_32 داریم: formula_137 &lt;br&gt;اثبات: ابتدا نشان می دهیم formula_138. چون formula_139 با جمع کردن روی تمام یال های هر دور formula_82 می بینیم که formula_141. بنابراین برای دور با هزینه متوسط کمینه formula_82 داریم: formula_143 حال نشان می دهیم که formula_144. قرار می دهیم formula_145. آنگاه برای هر دورformula_82 در formula_89 داریم: formula_148 راس formula_149 را به گراف اضافه کرده و و آن را به همه رئوس formula_150، با یال هایی به وزن formula_151 وصل می کنیم. پتانسیل formula_152 را برای گره formula_150 به صورت طول کوتاه ترین مسیر از formula_149 به formula_150 با استفاده از هزینه های formula_156 تعریف می کنیم. با
استفاده از تعریف کوتاهترین مسیر داریم: formula_157 که نتیجه می دهد: formula_158 این بدان معنی است که formula_32، formula_160- بهینه است. بنابراین formula_161 فرض کنید گردش formula_32 داده شده باشد و formula_163 گردش به دست آمده بعد از formula_164 بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی formula_32 باشد. تئوری زیر ثابت می کند که الگوریتم Goldberg-Tarjan در زمان چندجمله ای اجرا می شود. تئوری3: formula_166 تئوری4: formula_167 که formula_168 و formula_169 تعداد یال ها و گره ها در گراف هستند. تئوری5: اگر formula_170 گردش formula_32 بهینه است. اثبات: این حقیقت که formula_172 نشان می دهد که پتانسیل formula_79 موجود است که formula_174. بنابراین برای هر دور formula_175. با توجه به صحیح بودن هزینه ها داریم؛ formula_176 حال با توجه به سه نتیجه قبل ثابت می کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله ای بر حسب اندازه ورودی، خاتمه می یابد. تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر formula_177 تکرار نیاز دارد. اثبات: هر گردش اولیه C- بهینه است. بعد از formula_178 تکرار، با ت
وجه به اینکه formula_179، داریم: formula_180 اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر formula_101 داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر formula_182 خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله ای نیست. اثبات تئوری 3: می دانیم پتانسیل formula_79 موجود است که: formula_184 به علاوه، formula_137. برای دور formula_82 با کمترین هزینه متوسط، چون formula_187، نتیجه می گیریم که formula_188. حال ادعا می کنیم که formula_189. داریم formula_190، اگر formula_191 یا formula_192. در حالت اول، formula_193. در حالت دوم، formula_194. در هر دو حالت، formula_195، formula_130 -بهینه است و تئوری ثابت می شود. اثبات تئوری4: می دانیم پتانسیل formula_79 موجود است که formula_184. فرض کنید در تکرار formula_164، دور formula_82 را حذف می کنیم که در آن، formula_201. آنگاه formula_202 بنابراین formula_203 حذف دور، یک یال با formula_204 را از گراف باقی مانده حذف و تنها یال هایی با formula_205 را ایجاد می کند. بنابراین برای حذف چنین یالی به بیش از formula_168 تکرار نیاز نیست. انتزاعی الگوریتم هزینه پ
یمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی از کارآمدترین الگوریتم ها، برای روند کمترین هزینهٔ مسائل، شناخته شده است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می کند. الگوریتم گولبرگ و تارجان. یک روند formula_6، formula_118 -بهینه نامیده می شود اگر یک ذخیره formula_37 مانند formula_210 برای همهٔ formula_211. پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان یک روند formula_6 را محاسبه می کند که بهینه formula_118 برای بعضی از formula_118 های بزرگ است. پس مقدار formula_118 را در هر تکرار، نگهداری کردن و بهینگی formula_118، کاهش می دهد. ساده است که هر روند formula_6، بهینه formula_118 است اگر formula_219 . علاوه بر این، از دید هزینه های انتگرال، هر روند formula_118-بهینه با formula_221، بهینه است. پس ساختار جهانی این الگوریتم، به صورت زیر است.&lt;br&gt; formula_223 form
ula_224 formula_225 formula_226 formula_227 formula_228 formula_229 formula_230 formula_231 formula_230 این روال دستوری( مجموعه کد) به صورت زیر اجرا می شود: ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال ها با هزینه کاهش یافته منفی هل داده می شود. این نتیجه یک روند formula_233 بهینه برای بعضی formula_233 ها است. یک راس فعال نامیده می شود اگر اضافی باشد. formula_235 تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می شود. formula_236 formula_224 formula_238 formula_239 formula_224 formula_241 formula_242 formula_243 formula_244 formula_245 formula_230 formula_230 formula_248 formula_224 formula_250 formula_251 formula_244 formula_253 formula_230 formula_255 formula_224 formula_257 formula_230 هر اجرای refine، formula_259 عمل relabel و formula_260. عمل push استفاده می کند که formula_261 و formula_262. اثبات این موارد قبلاً ذکر شده است. ملاحظه می کنیم که به طور تئوری زمان refine را می توان با استفاده از درخت های پویا به formula_263 بهبود داد. برای محاسبه روند formula_6 ا
ولیه، الگوریتم روند ماکسیموم گولدبرگ و تارجان استفاده می شود. در آزمایش های ما فقط بخش کوچکی از زمان اجرا برای این قدم اولیه مصرف شد. جنبه های پیاده سازی. تصمیم اولیه در هنگام پیاده سازی الگوریتم فوق مربوط به گراف باقی مانده ای است: لازم نیست که گراف باقی مانده ای را به طور صریح ذخیره کنیم. اما اگر بدون ذخیره سازی عمل شود، لازم است تمام یال های همسایهٔ یک راس فعال چک شود قبل از این که بتوان آن را relabel کرد. این کار بسیار پر هزینه است. لذا تصمیم گرفتیم که گراف باقی مانده ای را به طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم. ظرفیت باقی مانده ای ذخیره و در هر یال به روز می شود. در نتیجه نیازی به ذخیره روند نیست. در حقیقت روند به طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. برای هر راس formula_12،افزونگی formula_266 و formula_267 احتمالی ذخیره می شود. هزینه های کاهش یافته به طور صریح ذخیره نمی شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. برای هر راس لیستی از یال های خارج شونده با ظرفیت باقی مانده ای مثبت
موجود است. اشاره گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه گذاری می کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می کند. این امر متضمن آن است که یک relabel می تواند زمانی که اشاره گر به انتهای لیست می رسد انجام پذیرد. یک امر مهم در پیاده سازی انتخاب راس فعال است. با توجه به این که تعداد رأس های فعال معمولاً کم است لازم است که ساختمان داده ای استفاده شود که مجموعه گره های فعال را در بر دارد. ساختمان داده های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده سازی ساده صف استفاده می شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس های فعال را در یک صف ساده ذخیره کنیم. توجه شود
که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به formula_268 کاهش می دهد. مکاشفه ای. پالایش قیمت. رویه refine یک روند formula_6 ،formula_118-بهینه محاسبه می کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از formula_271 بهینه برای بعضی از formula_272. در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می شود اولین مسئله را می توان توسط یک محاسبه کوتاه ترین مسیر مبدأ واحد در formula_285 حل کرد که formula_286 از روی formula_286 با اضافه کردن formula_118 به هر وزن یال به دست می آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند formula_6 جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود. مکاشفهٔ دیگر توسط راه حل مسئله دوم به دست می آید. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده است. ملاحظه کنید که formula_32 ،formula_118 بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در formula_285 وجود نداشته باشد که
در آن formula_293 برای همه ی formula_278 . لذا کوچکترین formula_118 که به ازای آن formula_118 بهینه می شود عبارت است ازformula_297 که در آن formula_298 عبارت است از کمترین وزن میانگین مدار جهت دار در formula_299. لذا مسئله دوم چیری به جز یک مسئله کمترین چرخهٔ میانگین نیست. این مسئله را می توان توسط یک الگوریتم پارامتری کوتاه ترین مسیر به طور بسیار کارآند حل کرد. یک نسخهٔ پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخهٔ بهبود یافتهٔ آن توسط تارجان و ارلین بیان شده است. یک پیاده سازی کارآمد این الگوریتم توسط بوناگل توصیف شده است. زمان اجرا در بدترین حالت عبارت است از formula_300. برای پیاده سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه ترین مسیر در هر تکرار حل کردیم. کوچکترین formula_118 که سبب شود روند formula_6 جاری formula_118 بهینه شود را پیدا می کنیم و همچنین یک formula_49 بالقوه مناسب را میابیم. سپس refine را به formula_32، formula_49 و formula_307 اعمال می کنیم. این مکاشفه منجر به بهبود قابل ملاحظه ای در زمان اجرا شد. در مقایسه با این که توسط یک محاسبه ساده کوتاه