Payamvdn/NorthPersian_fa_wiki huggingface dataset:
مق-اول ایجاد می شوند ضریب شاخه کمتری دارند (شکست های کمتری در هر شاخه به وجود می آورند) و راهروهای زیادی را دربردارند. این امر باعث می شود که الگوریتم جستجوی عمق-اول برای تولید هزارتو در بازی های ویدئویی مناسب باشد. با حذف کردن تصادفی تعدادی از دیوارها در هزارتوی تولید شده با این روش، می توان راهروهای طولانی و باریک را شاخه دارتر کرد. این روش برای تولید هزارتوهایی با درجه دشواری کمتر مناسب است. هم چنین این حالت نیز برای تولید بازی های ویدئویی مطلوب است. پس گردان بازگشتی. الگوریتم جستجوی عمق-اول در تولید هزارتو به طور معمول با استفاده از روش پس گرد Backtrack پیاده سازی می شود. الگوریتم تصادفی کروسکال. این الگوریتم نسخه تصادفی الگوریتم کروسکال است. داده ساختارهای متفاوتی وجود دارند که می توانند مجموعه هایی از خانه ها را شبیه سازی کنند. یک راه پیاده سازی کارا که توسط داده ساختار مجموعه های مجزا صورت می گیرد، می تواند هر عمل اجتماع و یافتن روی دو مجموعه را به طور سرشکن در زمان خطی انجام دهد (به طور دقیق تر زمان formula_1 ; formula_2 به ازای هر formula_3). بنابراین زمان اجرای این الگوریتم در اصل با تعداد دیوارهای
موجود در هزارتو متناسب است. این مسئله که فهرست دیوارها ابتدا به طور تصادفی مقداردهی اولیه شود یا هر دیوار به طور تصادفی از بین فهرست غیرتصادفی از دیوارها انتخاب شود، اهمیت چندانی ندارد. هر کدام از این دو روش نیز در پیاده سازی در یک سطح از سادگی قرار دارند. از آنجا که نتیجه این الگوریتم، تولید درخت پوشای کمینه یک گراف با یال های هم وزن است، الگوریتم به سمت تولید الگوهای منظمی که به نسبت ساده تر حل می شوند، متمایل است. الگوریتم تصادفی پریم. این الگوریتم نسخه تصادفی الگوریتم پریم است. مانند الگوریتم جستجوی عمق-اول، یافتن راه به سمت خانه اول معمولاً به نسبت ساده است اما به سمت دیگر خانه های هزارتو دشوار. توجه کنید که اجرای الگوریتم کلاسیک پریم بر روی یک گراف با وزن تصادفی هزارتوهایی با الگویی مشابه با هزارتوهای تولید شده در الگوریتم کروسکال ایجاد می کند. چرا که هر دو الگوریتم به یافتن درخت پوشای کمینه اختصاص دارند. در عوض، الگوریتم حاضر الگوی متفاوتی از هزارتوها را ایجاد می کند. چرا که یال های نزدیک تر به نقطه آغازین وزن مؤثر کمتری دارند. نسخه اصلاح شده. با وجود اینکه الگوریتم کلاسیک پریم فهرستی از یال ها را ذخیر
ه می کند، برای تولید هزارتو می توان لیستی از خانه های مجاور به هر خانه را ذخیره کرد. اگر یک خانه تصادفی توسط چندین یال به هزارتو موجود متصل شود یکی از این یال ها به طور تصادفی انتخاب می شود. این روش تمایل بیشتری به ایجاد شاخه نسبت به روش بالا که مبتنی بر ذخیره یال بود دارد. روش تقسیم بازگشتی. هزارتوها می توانند از طریق تقسیمات بازگشتی ساخته شوند. یک الگوریتم برای این کار در زیر شرح داده شده است: از یک فضای بدون دیوار شروع کن و آن را یک اتاق بنام. اتاق را با دیوارهایی که به طور تصادفی قرار می گیرند تقسیم کن (برای هر دیوار یک دهانه برای شروع یک راهرو، در نقطه ای تصادفی روی آن دیوار قرار دارد). حال به طور بازگشتی همین عملیات را روی اتاق های درونی انجام بده تا زمانی که همه اتاق ها به اندازه کمینه برسند. این روش منجر به تولید هزارتوهایی می شود که در آن ها دیوارهای راست و طولانی عبور می کنند. این الگو هزارتوهایی تولید می کند که در آن ها نواحی ای که بهتر است از ورود به آن ها خودداری شود، ساده تر دیده می شوند. برای مثال، در یک هزارتو مستطیلی، در یک نقطه تصادفی از فضا دو دیوار که به یکدیگر عمود هستند را بسازید. این دو
دیوار اتاق اولیه را به چهار اتاق کوچک تر تقسیم می کنند که توسط چهار دیوار از یکدیگر جدا شده اند. سه دیوار از این چهار دیوار را به طور تصادفی انتخاب کنید و یک روی هر کدام از آن ها و در نقطه ای تصادفی بر روی آن ها یک دهانه ورودی به عرض یک واحد ایجاد کنید. این روند را به طور بازگشتی ادامه دهید تا زمانی که تمامی اتاق ها عرضی برابر یک واحد در یکی از بعدهای خود داشته باشند. الگوریتم های ساده. الگوریتم های دیگری نیز وجود دارند که تنها به میزان کافی حافظه برای ذخیره یک ردیف از یک هزارتو دوبعدی یا یک صفحه از یک هزارتو سه بعدی نیازمند هستند. این الگوریتم ها با ذخیره کردن خانه هایی در ردیف کنونی که به خانه هایی از ردیف قبل مسیر دارند، از ایجاد حلقه جلوگیری می کنند. اکثر الگوریتم های تولید هزارتو برای اطمینان از قابل حل بودن هزارتو نهایی، نیازمند نگه داری ارتباط میان خانه های درونی هستند. هرچند هزارتوهای معتبر و همبند تنها با تمرکز بر روی هر خانه قابل تولید هستند. هزارتو درخت دودویی، یک هزارتو استاندارد با خطوط عمود بر هم است که در آن هر خانه یک راهرو به سمت بالا یا چپ دارد اما هر دو آن ها را نمی تواند داشته باشد. برای
ساخت یک هزارتو درخت دودویی، برای هر خانه با انداختن سکه تصمیم گرفته می شود که حرکت به سمت بالا یا چپ انجام شود. برای خانه های روی مرز همواره یک جهت اتخاذ می شود و نتیجه نهایی یک هزارتو معتبر همبند ساده خواهد بود که ظاهری مانند درخت دودوییای دارد که ریشه آن، خانه بالا سمت چپ است. جای گزین انداختن سکه برای هر خانه، ساخت یک عکس با استفاده از ترکیبی تصادفی از کاراکترهای ممیز و ممیز رو به عقب ("") است. این روش یک هزارتو همبند ساده و معتبر را ایجاد نمی کند اما گروهی از حلقه های بسته را ایجاد می کند (راهنمای استفاده از کمودور ۶۴ یک برنامه پایه را با استفاده از این الگوریتم ارائه می دهد، با این تفاوت که از کاراکترهای مورب گرافیکی PETSCII برای یک نمایش گرافیکی روان تر استفاده می کند). الگوریتم های خودکاره مشبک. انواع مشخصی از خودکاره های شبکه می توانند در تولید هزارتو مورد استفاده قرار گیرند. دو نوع مشهور از این خودکاره های شبکه، ماز و مازکتریک، دارای قوانین رشته ایB۳/S۱۲۳۴۵ و B۳/S۱۲۳۴ هستند. در حالت اول، این بدان معنی است که هر خانه به این شرط از یک مرحله به مرحله بعدی باقی می ماند که حداقل یک و حداکثر پنج همسایه داش
ته باشد. در حالت دوم، هر خانه با داشتن یک تا چهار همسایه باقی می ماند. اگر خانه ای دقیقاً سه همسایه داشته باشد متولد می شود. برای یک الگوی شروع تصادفی، این خودکاره های تولیدکننده هزارتو مشبک به تولید هزارتوهایی پیچیده منجر می شوند که دیوارهای راهروهای آن به طور غیرمبهمی ترسیم شده اند. مازکتریک که دارای قانون B۳/S۱۲۳۴ است، در مقایسه با ماز با قانون B۳/S۱۲۳۴۵ گرایشی به تولید راهروهای طولانی و باریک دارد. این یک عیب قابل توجه محسوب می شود چرا که این هزارتوها به نسبت قابل پیش بینی می شوند. مانند برخی از روش های مبتنی بر نظریه گراف که در بالا به تفصیل بیان شد، این خودکاره های مشبک عموماً هزارتوهایی از یک الگوی آغازین یکتا تولید می کنند؛ بنابراین معمولاً منجر به تولید هزارتوهایی می شوند که یافتن راه به خانه ابتدایی در آن ها به نسبت ساده است، حال آنکه راه یابی به دیگر خانه ها به نسبت دشوارتر است. شبه کد جاوا. class MazeBuilder implements Runnable { public static final int CW_TOP = 1; public static final int CW_BOT = 2; public static final int CW_LEFT = 4; public static final int CW_RIGHT = 8; static final int CW_VIR
GIN = 16; public static final int CW_ALL = CW_TOP|CW_BOT|CW_LEFT|CW_RIGHT; static final int CW_BOUND_SHIFT = 5; static final int CW_TOP_BOUND = 32; static final int CW_BOT_BOUND = 64; static final int CW_LEFT_BOUND = 128; static final int CW_RIGHT_BOUND = 256; static final int CW_ALL_BOUNDS = CW_TOP_BOUND|CW_BOT_BOUND|CW_LEFT_BOUND|CW_RIGHT_BOUND; static final int CW_IN_ROOM = 512; public static int dirsx[] = { 1, 0, -1, 0 }; public static int dirsy[] = { 0, 1, 0, -1 }; int width, height, startx, starty; int cells[][], origdirs[][], dists[][]; boolean can_go(int x, int y, int dx, int dy) { int bit = get_bit(dx, dy) « CW_BOUND_SHIFT; if ((cells[x][y] &amp; bit) != 0) return false; return (cells[x+dx][y+dy] &amp; CW_VIRGIN) != 0; int get_bit(int dx, int dy) { int bit = 0; switch (dx + dy * 2) { case 1: bit = CW_RIGHT; break; case -1: bit = CW_LEFT; break; case 2: bit = CW_BOT; break; case -2: bit = CW_TOP; break; default: dbg("get_bit problem "+dx+" "+dy); break; return bit; Random random; Maze maze; int randno
(int lo, int hi) { return (Math.abs(random.nextInt()) % (hi-lo+1)) + lo; void delwall(int x, int y, int dx, int dy) { int bit; bit = get_bit(dx, dy); cells[x][y] &amp;= ~bit; bit = get_bit(-dx, -dy); cells[x+dx][y+dy] &amp;= ~bit; void delbound(int x, int y, int dx, int dy) { int bit; bit = get_bit(dx, dy); cells[x][y] &amp;= ~(bit « CW_BOUND_SHIFT); bit = get_bit(-dx, -dy); cells[x+dx][y+dy] &amp;= ~(bit « CW_BOUND_SHIFT); void addboundwall(int x, int y, int dx, int dy) { int bit = get_bit(dx, dy); cells[x][y] |= bit | (bit«CW_BOUND_SHIFT); int bit2 = get_bit(-dx, -dy); cells[x+dx][y+dy] |= bit2 | (bit2«CW_BOUND_SHIFT); int partiters = 0; int grade_partition(Vector sl, Seg pe) { int x = pe.x; int y = pe.y; int dx = pe.dx; int dy = pe.dy; int lcount = 0, rcount = 0, splits = 0; int inc = 1; if (sl.size() &gt;= 100) inc = sl.size() / 50; for (int i = 0; i &lt; sl.size(); i += inc) { Seg se = (Seg) sl.elementAt(i); int df1x = se.x-x; int df1y = se.y-y; int sendx = se.x + se.dx; int sendy = se.y + se.dy; int df2
x = sendx - x; int df2y = sendy - y; int nx = dy; int ny = -dx; int dot1 = df1x * nx + df1y * ny; int dot2 = df2x * nx + df2y * ny; if (getSign(dot1) != getSign(dot2)) { if (dot1 == 0) dot1 = dot2; else if (dot2 != 0) { splits++; continue; if (dot1 &gt; 0 || (dot1 == 0 &amp;&amp; se.GetDir() == pe.GetDir())) { rcount++; } else if (dot1 &lt; 0 || (dot1 == 0 &amp;&amp; se.GetDir() == -pe.GetDir())) { lcount++; } else { dbg("grade_partition problem: dot1 = "+dot1+", dot2 = "+dot2); return Math.abs(lcount-rcount) + splits * 3; Vector seglist; static int getSign(int num) { return (num &lt; 0) ? -1 : (num &gt; 0) ? 1 : 0; void Initialize() { int x, y; for (x = 0; x != width; x++) { for (y = 0; y != height; y++) { cells[x][y] = CW_VIRGIN | CW_ALL; cells[x][0] |= CW_TOP_BOUND; cells[x][height-1] |= CW_BOT_BOUND; for (y = 0; y != height; y++) { cells[0][y] |= CW_LEFT_BOUND; cells[width-1][y] |= CW_RIGHT_BOUND; void Generate() { int x, y; y = 0; int firstx = x = randno(0, width-1); int dir = 0; int origdir = dir; cells
[x][y] &amp;= ~CW_VIRGIN; while (true) { int dx = dirsx[dir], dy = dirsy[dir]; if (!can_go(x, y, dx, dy)) { dir = (dir+1) &amp; 3; if (origdir == dir) { if (x == firstx &amp;&amp; y == 0) break; int odr = origdirs[x][y]; dx = dirsx[odr]; dy = dirsy[odr]; x -= dx; y -= dy; origdir = dir = randno(0, 3); } else { delwall(x, y, dx, dy); x += dx; y += dy; cells[x][y] &amp;= ~CW_VIRGIN; origdirs[x][y] = dir; origdir = dir = randno(0, 3); }
مسئلهٔ زمان بندی کار کارگاهی یک مسئلهٔ بهینه سازی در مهندسی صنایع و تحقیق در عملیات است که در آن کارها به منابع در زمان های خاصی نسبت داده می شوند. صورت اصلی آن در ادامه آمده است: در این مسئله n کار j1, j2, …, jn با اندازه های متفاوت که باید روی m ماشین یکسان زمان بندی شوند در تلاشند تا زمان کل(makespan) را به حداقل برسانند. زمان خالی مجموع زمان لازم برای انجام همهٔ کارهاست (که همهٔ کارها تمام شده اند). امروزه، این مسئله به عنوان یک مسئلهٔ پویا(dynamic scheduling) مطرح می شود، که با ارائه شدن هر کار، الگوریتم پویا باید با اطلاعات موجود تصمیم گیری کند قبل از اینکه کار بعدی مطرح شود. این مسئله یکی از مشهورترین مسائل پویاست، و اولین مسئله ای بود که برای آن تحلیل رقابتی(competitive analysis) به وسیلهٔ Graham در سال ۱۹۶۶ مطرح شد. بهترین نمونه های مسئله برای مدل پایه با هدف بهینه سازی زمان کل به وسیلهٔ Taillard مطرح شد. تاریخچه. این مسئله حداقل هفتاد سال قدمت دارد. نمایش مسئله. (disjunctive graph) یکی از بهترین مدل های مورد استفاده برای تشریح کردن سامانه های مختلف این مسئله است. لیست الگوریتم های زمان بندی موجود در
سال ۱۹۶۶ را گراهام از قبل آماده کرده بود، که تمامی آن ها (2-1/m)رقابتی بوده اند. منظور از m در این جا تعداد ماشین ها است. همچنین این امر که زمان بندی لیست، راه حل بهینه برای مسئلهٔ آنلاین ۲ یا ۳ ماشین است اثبات شده بود. در سال ۹۲ برای مشاغل یکسان طول، برای ۲ ماشین نیز بهینه و (2-2/m) رقابتی است. در سال ۱۹۹۲، بارتال، فیات، کارلفت و وهرا الگوریتمی ۱٫۹۸۶-رقابتی ارائه کردند. در سال ۱۹۹۴، کارگر، فیلیپس و تورنگ یک الگوریتم ۱٫۹۴۵ رقابتی ارائه دادند. در سال ۱۹۹۲، آلبرز یک الگوریتم جدید که ۱٫۹۲۳-رقابتی بود ارائه داد. در حال حاضر، بهترین پاسخ موجود، الگوریتمی از فلیشر و وهل می باشد که یک راه حل ۱٫۹۲۰رقابتی است. یک حد پایین ۱٫۸۵۲-رقابتی نیز توسط آلبرز ارائه داده شد. نمونه های Taillard نقش مهمی در ایجاد زمان بندی مغازهٔ کار با اهداف مدت ایجاد(makespan objectives) ایفا می کنند. در سال ۱۹۷۶ گری، اثبات کرد که این مسئله برای nهای بزرگ تر از ۲ یک مسئلهٔ ان پی کامل است، به این معنا که برای بیش از ۳ ماشین، نمی توان راه حلی از زمان چندجمله ای برای حل این مسئله ارائه داد. بهینه سازی آفلاین (برون خطی) بازهٔ زمانی تولید. ساده ترین
حالت مسئله حداقل کردن offline makespan برای مشاغل اتومیک می باشد، که در این مشاغل اتومیک، مشاغلی هستند که شغل قابلیت تقسیم شدن به مشاغل کوچکتر را ندارد. برای مثال، این مفهوم مشابه بسته بندی کردن چندین تکه با حجم های متفاوت درون تعداد ثابتی از صندوق ها، به گونه ای که بزرگترین حجم صندوق مورد نیاز، در کمترین حد ممکن باشد. (در صورتی که حالت برعکس این مورد، یعنی کمینه کردن تعداد صندوق ها و ثابت بودن سایز هر صندوق مد نظر باشد، این مسئله تبدیل به مسئلهٔ دیگری به نام می شود). هاشبوم و یک را در سال ۱۹۸۷ ارائه دادند که یک راه حل تخمینی برای مسئله را با هر درجه ای از دقت که مد نظر باشد به دست می آورد. مشاغلی که از چندین عملیات تشکیل شده اند. حالت ابتدایی از زمان بندی کردن مشاغل با چندین عملیات(M)، بر روی چندین ماشین (M)، به گونه ای که تمامی عملیات اول باید روی ماشین اول اجرا شوند، تمامی عملیات دوم روی ماشین دوم و …. و چند شغل نمی توانند به صورت موازی اجرا شوند، به عنوان مسئله زمان بندی مغازهٔ باز شناخته می شوند. الگوریتم های مختلفی برای این سؤال موجود است، از جمله الگوریتم های ژنتیک. الگوریتم جانسون. برای حل حالتی از ا
ین مسئله که در آن ۲ ماشین وN شغل متفاوت موجود است و تمامی مشاغل باید به ترتیب مورد پردازش قرارگیرند، می توان از یک الگوریتم مکاشفه ای که توسط S.M. Johnson ایجاد شده است، استفاده کرد. قدم های مختلف این الگوریتم به صورت زیر است: شغل Pi دارای دو عمل است، طول هرکدام از این عمل ها pi۱ و pi۲ است، که روی ماشین های M۱ و M۲ به همان ترتیب اجرا می شوند. در صورتی که کمینه به Pk۱ تعلق داشته باشد، K را از لیست A حذف کنید، K را به انتهای لیست L۱ اضافه نمایید. در صورتی که مقدار کمینه به Pk۲ تعلق داشته باشد، روش جانسون، تنها در حالتی که دو ماشین داشته باشیم به صورت بهینه کار می کند. اما از آن جهت که این روش، روشی بهینه و ساده برای محاسبه است، بعضی از پژوهشگران در جهت تعمیم این الگوریتم به حالت M ماشین تلاش کرده اند. ایده مورد نظر به صورت زیر است: تصور کنید که هر شغل، نیاز به M عمل مختلف دنبال هم، روی M1, M2, M3, …, Mm دارد. ما به این گونه عمل می کنیم که m/۲ ماشین اول را به یک ماشین بزرگ (موهومی) تبدیل می کنیم و آن را MC۱ می نامیم. ماشین های باقی مانده دیگر را نیز به یک ماشین بزرگ دیگر به نام MC۲ تبدیل می کنیم. در این صورت، زم
ان پردازش نهایی برای شغل P روی MC۱ برابر است با مجموع زمان عمل ها روی m/۲ ماشین اول و زمان پردازش نهایی شغل p روی MC۲ برابر با مجموع زمان عمل ها روی m/۲ ماشین آخر است. در این صورت، ما توانستیم این مسئلهٔ m-machine را به یک مسئلهٔ برنامه ریزی ۲-machine کاهش دهیم. حال می توانیم با استفاده از الگوریتم جانسون، این مسئله را حل کنیم. این جا یک مثال از مسئله زمان بندی مغازهٔ کارها که به صورت به عنوان یک مسئلهٔ محدودیت های نشانگر آورده شده است. param N_JOBS; param N_MACHINES; set JOBS ordered = 1..N_JOBS; set MACHINES ordered = 1..N_MACHINES; param ProcessingTime{JOBS, MACHINES}&gt; 0; param CumulativeTime{i in JOBS, j in MACHINES} = sum {jj in MACHINES: ord(jj) &lt;= ord(j)} ProcessingTime[i,jj]; param TimeOffset{i1 in JOBS, i2 in JOBS: i1 &lt;&gt; i2} = max {j in MACHINES}(CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]); var end&gt;= ۰; var start{JOBS}&gt;= ۰; var precedes{i1 in JOBS, i2 in JOBS: ord(i1) &lt;ord(i2)} binary; minimize makespan: end; subj to makespan_def{i in JOBS}: end&gt;= start
[i] + sum{j in MACHINES} ProcessingTime[i,j]; subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) &lt;ord(i2)}:precedes[i1,i2] ==&gt; start[i2]&gt;= start[i1] + TimeOffset[i1,i2]; subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) &lt;ord(i2)}:!precedes[i1,i2] ==&gt; start[i1]&gt;= start[i2] + TimeOffset[i2,i1]; data; param N_JOBS := ۴; param N_MACHINES := ۳; param ProcessingTime: ۱ ۲ ۳ := ۱ ۴ ۲ ۱ ۲ ۳ ۶ ۲ ۳ ۷ ۲ ۳ ۴ ۱ ۵ ۸;
در نظریه گراف، که شاخه ای از ریاضیات است، رنگ آمیزی لیستی نوعی از رنگ آمیزی گراف است. در این رنگ آمیزی برای هرراس لیستی از رنگ ها وجود دارد که آن راس می تواند توسط یکی از رنگ های این لیست رنگ شود. این شاخه ابتدا توسط ویزینگ، اردوش، رابین و تیلور مورد مطالعه قرار گرفت و بنیان آن بنا شد. تعریف. G را یک گراف در نظر بگیرید و برای هر راس مانند v از گراف، (L(v را لیستی از رنگ های موجود برای آن رأس، تعریف کنید. رنگ آمیزی لیستی یک رنگ آمیزی انتخابی است که به هر راس مانند v یک رنگ دلخواه از لیست رنگ های آن راس ((L(v) متناظر می کند. به یک رنگ آمیزی لیستی خوب می گوییم هرگاه هیچ دو راس مجاوری همرنگ نباشند. یک گراف را k-لیست رنگ پذیر می نامیم هرگاه مستقل از این که لیست k رنگیِ رنگ های هر راس چیست، یک رنگ آمیزی لیستی خوب برای آن وجود داشته باشد. عدد رنگی لیستی ((ch("G") گراف "G"، کوچکترین عدد k است که گراف "k"، G رنگ پذیر است. به بیان دقیق تری، برای یک تابع مانند f که به هر راس مانند v یک عدد صحیح مثبت، (f(v را نسبت می دهد، گراف "G" را f-لیست رنگ پذیر می نامند، هرگاه مستقل از این که لیست (f(v رنگیِ هر راس مانند v شامل چه ر
نگ هایی باشد، یک رنگ آمیزی لیستی خوب برای آن وجود داشته باشد. به طور خاص اگر برای هر راس مانند f(v) = k "،v" باشد، گراف k-لیست رنگ پذیر می باشد. مثال. فرض کنید "q" یک عدد صحیح مثبت باشد و "G" یک گراف کامل دوبخشی "K""q","q""q" باشد. رنگ های موجود را با "q""2" عدد دو رقمی مختلف در مبنای q نمایش می دهیم. در بخشی از این گراف دو بخشی که "q" راس دارد، هر راس از گراف را متناظر با مجموعه ای از رنگ ها در نظر می گیریم که رقم باارزش آن ها یکسان است. برای مثال به راس شمارهٔ i ام مجموعه رنگ های {i0,i1, … ,iq} متناظر می کنیم. در بخش دیگر از این گراف دو بخشی، به هر راس از "q""q" راس این گراف یک مجموعه از رنگ ها مانند {... ,0a, 1b, 2c}، به طوری که رقم باارزش آن ها متفاوت باشد. به تعداد "q""q" تا مجموعه با چنین خاصیتی وجود دارد، زیرا تعداد q-تایی های (...,a,b,c) برابر با "q""q" است. برای مثال اگر q" = 2" باشد، گراف دو بخشی "K""2","4" خواهیم داشت. در این گراف دو راس واقع در یک بخش این گراف مجموعه رنگ های {00,01}, {10,11} و 4 راس واقع در بخش دیگر گراف مجموعه رنگ های {00,10}, {00,11}, {01,10}, {01,11} را دارند. تصویر روبرو یک مث
ال بزرگ تر را به ازای q" = 3" نشان می دهد. عدد رنگی لیستی گراف "G" از "q" کوچک تر یا مساوی نیست. مستقل از این که چه رنگی برای هر راس انتخاب شود، در بخش بزرگ تر راسی که لیست رنگی آن برابر با مجموعه رنگ های بخش کوچک تر است، نمی تواند رنگ شود. برای مثال اگر راس با لیست رنگی {00,01} با 01 و راس با لیست رنگی {10,11} با 10 رنگ شود، سپس راس با لیست رنگی {01,10} با هیچ کدام از دو رنگ 01 و 10 نمی تواند رنگ شود. بنابراین عدد رنگی لیستی "G" حداقل "q" + 1 است. به طور مشابه، اگر formula_1، گراف کامل دو بخشی"k"، "K"n,n-لیست رنگ پذیر نیست. فرض کنید 2k-1 رنگ موجود باشد و در یک بخش از گراف هر راس با بقیه رئوس در یک "k"-تایی از این رنگ ها متفاوت باشد. پس هر بخش از گراف باید حداقل از "k" رنگ استفاده کند، در غیر این صورت، بعضی از راس ها، بی رنگ می مانند، اما این شرط باعث می شود که دو راس مجاور هم رنگ باشند. به طور خاص گراف مسئله سه روستا، 3-لیست رنگ پذیر و گراف کامل دوبخشی که هر بخش آن n رأس دارد ۴-لیست رنگ پذیر است. ویژگی ها. عدد رنگی لیستی (ch("G" از قواعد زیر برای گراف "G" با "n" راس، عدد رنگی ("X("G و بیشینه درجه (Δ("G" : مح
اسبه عدد رنگی لیستی. دو مسئله الگوریتمی که مطرح شده است: مسئلهٔ "k"-لیست رنگ پذیری در گراف های دوبخشی برای هر "k" ≥ 3 formula_3-کامل است، و به طور مشابه برای 4-لیست رنگ پذیری در گراف های مسطح، 3-لیست رنگ پذیری در گراف های بدون مثلثی، (2, 3)-لیست رنگ پذیری برای گراف های مسطح دوبخشی. می توان در زمان خطی مشخص کرد که یک گراف 2-لیست رنگ پذیر است یا نه. برای این کار به طور مکرر راس های درجه صفر یا یک را حذف می کنیم تا جایی که به یک گراف با بیشینه درجه ی دو برسیم. گراف اولیه k-لیست رنگ پذیر است اگر و تنها اگر گراف ساده شده یک دور زوج یا یک گراف تتا باشد که از سه مسیر با نقطهٔ پایانی مشترک تشکیل شده باشد، که طول 2 تا از آن ها دو و طول سومی زوج باشد.
در علوم رایانه، آبشاره سازی جزءبه جزء (Fractional cascading) روشی است که با آن می توان، دنبال های از جستجوهای دودویی را انجام داد و یک مقدار مشخص را از میان دنباله ای از ساختار داده های مرتبط به هم، با سرعت بالایی جستجوی دودویی کرد. اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می شود، اما جستجوهای بعدی سریعتر خواهند بود. روش آبشاره سازی جزءبه جزء نخستین بار در سال ۱۹۸۶ توسط Chazelle Guibas , طی دو مقاله م(Chazelle &amp; Guibas 1986a(Chazelle &amp; Guibas ۱۹۸۶ ارائه شد. این روش، برگرفته از دو ایده بود: یکی ایدهٔ آبشاره سازی که از الگوریتم "جستجوی دامنه ای داده در داده ساختارهاً از لوکر (۱۹۷۸) و ویلارد (۱۹۷۸) برگرفته شده بود. دیگری ایده نمونه برداری جزء به جزء از (Chazelle (۱۹۸۳. بعد از آن افراد دیگری شکل های پیچیده تری از روش آبشاره سازی جزءبه جزء ارائه کردند. در این الگوریتم ها، داده ساختار، وقتی دنباله ای از عملیات حذف و درج روی آن انجام شود و داده ها تغییر کنند، همچنان معتبر است و امکان جستجوی سریع در آن وجود دارد. در فناوری اطلاعات، اصطلاحاً به ترتیب دادن یک سلسله فعالیت های پیوس
ته در پردازش داده ها که در آن انجام هر مرحله وابسته به وقوع مرحلهٔ قبل است آبشاره سازی می گویند. مثال. به عنوان یک مثال ساده از آبشاره سازی جزءبه جزء، این مسئله را در نظر بگیرید: تعداد k لیست مرتب شده از اعداد حقیقی به ما داده شده است. مجموع تعداد اعضای این لیست ها روی هم n است. یعنی اگر هر لیست را با Li نشان دهیم، Σ|Li|=n. می خواهیم این لیست ها را طوری پردازش کنیم که بتوانیم جستجوهای دودویی را به دنبال مقدار خواسته شدهٔ q در هر یک از این k لیست انجام دهیم. برای مثال، به ازای n = ۴ و k = ۱۷: L1 = ۲٫۴، ۶٫۴، ۶٫۵، ۸٫۰، ۹٫۳ L2 = ۲٫۳، ۲٫۵، ۲٫۶ L3 = ۱٫۳، ۴٫۴، ۶٫۲، ۶٫۶ L4 = ۱٫۱، ۳٫۵، ۴٫۶، ۷٫۹، ۸٫۱ ساده ترین راه حل برای این مسئلهٔ جستجو، ذخیره کردن هر لیست به طور جداگانه (در یک آرایه) است. در این صورت به حافظهٔ اضافی از مرتبهٔ n نیاز داریم. جستجو را در هر یک از این k لیست به طور جداگانه انجام می دهیم. بدترین حالت زمانی رخ می دهد که تعداد اعضای لیست ها برابر و به میزان n/k باشد. در این صورت زمان یک جستجو، در هر لیست از مرتبهٔ (log(n/k و در نتیجه زمان کلی یک جستجو از مرتبهٔ (klog(n/k خواهد بود. راه حل دوم جستجوهای سریع
تری را ممکن می کند اما فضای بیشتری از حافظه می گیرد. ما می توانیم k لیست را در یک لیست بزرگ L با هم ادغام کنیم و به ازای هر مورد x از لیست L، نتایج جستجوهای x در لیست های کوچکتر Li را قرار دهیم. یک المان از لیست ادغام شده را با x[a, b, c, d] نشان می دهیم، که x یک مقدار، و a, b, c, d مکان های مقادیر عنصر بعدی x، در هر یک از لیست های ورودی است (فرض بر این است که نخستین مکان را با ۰ نشان می دهیم). با توجه به مرتب بودن لیست های ورودی، منظور از عنصر بعدی، عنصر بلافاصله بزرگ تر یا حد اقل مساوی با x است. (اگر چنین عنصری وجود نداشت، مکان بعد از آخرین خانهٔ لیست را، قرار داد می کنیم) در این صورت خواهیم داشت: L = ۱٫۱[۰٬۰٬۰٬۰], ۱٫۳[۰٬۰٬۰٬۱], ۲٫۳[۰٬۰٬۱٬۱], ۲٫۴[۰٬۱٬۱٬۱], ۲٫۵[۱٬۱٬۱٬۱], ۲٫۶[۱٬۲٬۱٬۱], ۳٫۵[۱٬۳٬۱٬۱], ۴٫۴[۱٬۳٬۱٬۲], ۴٫۶[۱٬۳٬۲٬۲], ۶٫۲[۱٬۳٬۲٬۳], ۶٫۴[۱٬۳٬۳٬۳], ۶٫۵[۲٬۳٬۳٬۳], ۶٫۶[۳٬۳٬۳٬۳], ۷٫۹[۳٬۳٬۴٬۳], ۸٫۰[۳٬۳٬۴٬۴], ۸٫۱[۴٬۳٬۴٬۴], ۹٫۳[۴٬۳٬۴٬۵] با این راه حل ادغامی یک پرس و جو در زمان (O(log n + k انجام می شود. زمان Log n برای جستجوی q در لیست n تایی L، و k برای گزارش کردن نتایج صرف می شود. با توجه به اینکه مکان هایx
در هر لیست های ورودی، در لیست L عنصر x ذخیره شده اند، نتایج پس از جستجو به دست می آیند. این مدل، چنین مسئله های جستجویی را با صرف زمان (O(log n + kو حافظهٔ (O(n حل می کند. راه حل آبشاره سازی جزءبه جزء ذخیره کردن دنباله های جدیدی از لیست های Mi است. لیست نهایی در این دنباله Mk است که برابر است با Lk، و هر لیست قبلی از ادغام Li با هر یک از به ازای هر عنصر x در این لیست ادغامی، ما دو عدد ذخیره می کنیم: مکانی که از جستجوی x در Li به دست می آید، و مکانی که از جستجوی x در Mi+۱ به دست می آید. به ازای داده های بالا، چنین عملی، این لیست ها را به ما می دهد: M1 = ۲٫۴[۰، ۱], ۲٫۵[۱، ۱], ۳٫۵[۱، ۳], ۶٫۴[۱، ۵], ۶٫۵[۲، ۵], ۷٫۹[۳، ۵], ۸[۳، ۶], ۹٫۳[۴، ۶] M2 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱], ۲٫۶[۲، ۱], ۳٫۵[۳، ۱], ۶٫۲[۳، ۳], ۷٫۹[۳، ۵] M3 = ۱٫۳[۰، ۱], ۳٫۵[۱، ۱], ۴٫۴[۱، ۲], ۶٫۲[۲، ۳], ۶٫۶[۳، ۳], ۷٫۹[۴، ۳] M4 = ۱٫۱[۰، ۰], ۳٫۵[۱، ۰], ۴٫۶[۲، ۰], ۷٫۹[۳، ۰], ۸٫۱[۴، ۰] فرض کنید می خواهیم یک پرس و جو برای q=۵ انجام دهیم. ابتدا یک جستجوی دودویی به دنبال qدر M۱انجام می دهیم و مقدار ۶٫۴[۱٬۵]. را پیدا می کنیم. عدد «۱» در ۶٫۴[۱٬۵]. به ما می گوید که جست
جوی q در L۱ باید L۱[۱] = ۶٫۴ را برگرداند. عدد ۵ نیز می گوید تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. یک مقدار پرچم به معنی آن است که q از انتهای لیست L۲ گذشته است. دومین «۳» در ۶٫۲[۳، ۳] به ما می گوید که تخمین موقعیت qدر M۳ موقعیت ۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی گرداند. در مقایسه q با مقدار کمتر ۶٫۲. به ما نشان می دهد که نتیجه درست در M۳ ،۶٫۲[۲٬۳] است. «۲» در۶٫۲[۲٬۳] به ما می گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پ