payamvha/North_RAG huggingface dataset:
= { 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+"
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 = 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;
&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 df2x = 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() ==
&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;
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)
== 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) مطرح می‌شود، که با ارائه شدن هر کار،
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/۲ ماشین اول و زمان پردازش نهایی شغل 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;
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}
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 یک رنگ دلخواه از لیست رنگ‌های آن راس
راس مانند v یک رنگ دلخواه از لیست رنگ‌های آن راس ((L(v) متناظر می‌کند. به یک رنگ‌آمیزی لیستی خوب می‌گوییم هرگاه هیچ دو راس مجاوری همرنگ نباشند. یک گراف را k-لیست رنگ‌پذیر می‌نامیم هرگاه مستقل از این که لیست k رنگیِ رنگ‌های هر راس چیست، یک رنگ‌آمیزی لیستی خوب برای آن وجود داشته‌باشد. عدد رنگی لیستی ((ch("G") گراف "G"، کوچکترین عدد k است که گراف "k"، G رنگ‌پذیر است. به بیان دقیق‌تری، برای یک تابع مانند f که به هر راس مانند v یک عدد صحیح مثبت، (f(v را نسبت می‌دهد، گراف "G" را f-لیست رنگ‌پذیر می‌نامند، هرگاه
گراف "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} با
رنگی {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-لیست رنگ‌پذیری در گراف‌های
در گراف‌های مسطح، 3-لیست رنگ‌پذیری در گراف‌های بدون مثلثی، (2, 3)-لیست رنگ‌پذیری برای گراف‌های مسطح دوبخشی. می‌توان در زمان خطی مشخص کرد که یک گراف 2-لیست رنگ‌پذیر است یا نه. برای این کار به‌طور مکرر راس‌های درجه صفر یا یک را حذف می‌کنیم تا جایی که به یک گراف با بیشینه درجه‌ی دو برسیم. گراف اولیه k-لیست رنگ‌پذیر است اگر و تنها اگر گراف ساده شده یک دور زوج یا یک گراف تتا باشد که از سه مسیر با نقطهٔ پایانی مشترک تشکیل شده‌باشد، که طول 2 تا از آن‌ها دو و طول سومی زوج باشد.
در علوم رایانه، آبشاره‌سازی جزءبه‌جزء (Fractional cascading) روشی است که با آن می‌توان، دنبال‌های از جستجوهای دودویی را انجام داد و یک مقدار مشخص را از میان دنباله‌ای از ساختار داده‌های مرتبط به هم، با سرعت بالایی جستجوی دودویی کرد. اولین جستجو، بنا به حالت عادی یک جستجوی دودویی، در زمانی لگاریتمی انجام می‌شود، اما جستجوهای بعدی سریعتر خواهند بود. روش آبشاره‌سازی جزءبه‌جزء نخستین بار در سال ۱۹۸۶ توسط Chazelle Guibas , طی دو مقاله م(Chazelle &amp; Guibas 1986a(Chazelle &amp; Guibas ۱۹۸۶ ارائه شد. این روش،
&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 مکان‌های مقادیر عنصر بعدی
یک مقدار، و 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 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱],
۵], ۸[۳، ۶], ۹٫۳[۴، ۶] M2 = ۲٫۳[۰، ۱], ۲٫۵[۱، ۱], ۲٫۶[۲، ۱], ۳٫۵[۳، ۱], ۶٫۲[۳، ۳], ۷٫۹[۳، ۵] M3 = ۱٫۳[۰، ۱], ۳٫۵[۱، ۱], ۴٫۴[۱، ۲], ۶٫۲[۲، ۳], ۶٫۶[۳، ۳], ۷٫۹[۴، ۳] M4 = ۱٫۱[۰، ۰], ۳٫۵[۱، ۰], ۴٫۶[۲، ۰], ۷٫۹[۳، ۰], ۸٫۱[۴، ۰] فرض کنید می‌خواهیم یک پرس و جو برای q=۵ انجام دهیم. ابتدا یک جستجوی دودویی به دنبال qدر M۱انجام می‌دهیم و مقدار ۶٫۴[۱٬۵]. را پیدا می‌کنیم. عدد «۱» در ۶٫۴[۱٬۵]. به ما می‌گوید که جستجوی q در L۱ باید L۱[۱] = ۶٫۴ را برگرداند. عدد ۵ نیز می‌گوید تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر،
تخمین موقعیت q در M۲ مکان ۵ است. با دقت بیشتر، جستجوی دودویی برای q در M۲ مقدار ۷٫۹[۳، ۵] در موقعیت ۵ یا مقدار۶٫۲[۳، ۳] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با ۶٫۲ و مشاهده اینکه کوچکتر است، ما می‌یابیم که نتیجه درست در M۲ , ۶٫۲[۳، ۳] است. اولین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که جستجو برای qدر L۲ باید L۲[۳] را برگرداند. یک مقدار پرچم به معنی آن است که q از انتهای لیست L۲ گذشته‌است. دومین «۳» در ۶٫۲[۳، ۳] به ما می‌گوید که تخمین موقعیت qدر M۳ موقعیت ۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳
۳ است. به طور دقیق تر، جستجوی دودویی برای q در M۳ مقدار۶٫۲[۲، ۳] در موقعیت ۳ یا مقدار ۴٫۴[۱، ۲] یک مکان جلوتر را برمی‌گرداند. در مقایسه q با مقدار کمتر ۶٫۲. به ما نشان می‌دهد که نتیجه درست در M۳ ،۶٫۲[۲٬۳] است. «۲» در۶٫۲[۲٬۳] به ما می‌گوید که جستجو برای qدر L۳ باید L۳[۲]=۶٫۲ را برگرداند و «۳» در ۶٫۲[۲٬۳] به ما می‌گوید که نتیجه جستجو برای q در M۴ برابر با M۴[۳] = ۷٫۹[۳٬۰] یا M۴[۲] = ۴٫۶[۲٬۰] است. با مقایسه q با ۴٫۶ نشان می‌دهد که نتیجه صحیح ۷٫۹[۳٬۰] است و نتیجه جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما
جستجو برای q در L۴ برابر L۴[۳] = ۷٫۹. است پس ما q را در هر یک از چهار لیست پیدا کردیم به‌وسیلهٔ جستجوی دوتایی در تک لیست M۱ همراه با یک مقایسه در هر لیست متواتر. به‌طور کلی تر برای هر ساختار داده از این نوع ما یک پرس و جو را به‌وسیلهٔ انجام یک جستجوی دودویی q در M۱ انجام می‌دهیم و با استفاده از مقدار نتیجه شده موقعیتq در L۱ را تعیین می‌کنیم. در مثال ما، لیست‌های آبشاره‌سازی جزءبه‌جزء شده، در مجموع ۲۵ عنصر دارند که مقداری کمتر از دو برابر ورودی اصلی است. به طور کلی سایز Mi در این داده ساختار حداکثر به این
طور کلی سایز Mi در این داده ساختار حداکثر به این اندازه‌است: Lj| + ½| Li + ۱ | + ¼ | Li + ۲ | + … + ۱/ ۲j | Mi + j | +…. که به سادگی اثبات می‌شود سایز داده ساختار حد اکثر ۲n است: (Σ|Mi| = Σ|Li|(۱ + ½ + ¼ +…) ≤ ۲n = O(n مسئلهٔ کلی. به طور کلی، آبشاره‌سازی جزءبه‌جزء با گراف کاتالوگ آغاز می‌شود. گراف کاتالوگ گرافی جهت دار است که هر رأس آن با یک لیست مرتب شده برچسب گذاری شده‌است. هر پرس و جو در این داده ساختار، شامل یک مسیر از این گراف و یک مقدار q است و به ازای این دو، داده ساختار باید مشخص کند q در هر یک از
این دو، داده ساختار باید مشخص کند q در هر یک از لیست‌های مرتب شده‌ای که در رئوس مسیر داده شده قرار دارند، چندمین عنصر است. به عنوان یک مثال ساده، گراف کاتالوگ مسیری است با چهار رأس. با استفاده از روش پویا (داینامیک)، امکان این وجود دارد که پاسخ رئوس بعدی یک مسیر را بر اساس نتایج جستجو در رئوس قبلی مسیر به دست آید. می‌خواهیم به پرسش‌هایی از این دست، در گرافی پاسخ دهیم. در این گراف به ازای مقدار ثابت d حداکثر تعداد یال‌های ورودی از هر رأس d و حد اقل تعداد یال‌های ورودی به هر رأس نیز d است. لیست‌های مربوط به
ورودی به هر رأس نیز d است. لیست‌های مربوط به هر رأس را، بر اساس همسایه‌های منتهی به یال‌های خروجی رأس، گسترش می‌دهیم. این کسر باید طوری انتخاب شود که کوچکتر از ۱/d باشد. به طوری که مقدار مجموع لیست‌های گسترش یافته نسبت به سایز ورودی خطی باشد. هر مورد، در هر لیست گسترش یافته، محل قرار گرفتن آن مورد را در لیست‌های گسترش نایافته‌ای که در همان رأس و در رأس‌های همسایهٔ منتهی به یال‌های خروجی، ذخیره شده‌اند، ذخیره می‌کند. به عنوان یک مثال ساده از این توضیحات، d=۱، و ما هر لیست را با ½ از همسایه‌هایش گسترش
d=۱، و ما هر لیست را با ½ از همسایه‌هایش گسترش داده‌ایم: یک پرسش در این داده ساختار، شامل یک جستجوی دودویی عادی در لیست گسترش یافتهٔ مربوط به رأس اول از مسیر مورد پرس و جو، و علاوه بر آن، تعدادی جستجوی ساده‌تر، در هر یک از رئوس بعدی مسیر است. اگرکسر ۱/r از همسایه‌های یک رأس در گسترش دادن لیست آن استفاده شود، در آن صورت نتیجهٔ هر پرسش بعدی حداکثر در r مرحله، از روی مکان‌هایی که در پرسش‌های قبلی، در رئوس قبلی مسیر ذخیره شده‌است، به‌دست خواهد آمد و حتی ممکن است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی
است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی دودویی کامل یافته شود. آبشاره‌سازی جزءبه‌جزء پویا. در آبشاره‌سازی جزءبه‌جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده‌است، می‌تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می‌توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. ایجاد این تغییرات باعث به وجود آمدن مشکلاتی در ساختاربندی داده‌ها می‌شود. یکی از مشکلاتی که در این زمینه وجود دارد این است که هنگام اضافه شدن یک عضو به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست
به یک گره یا حذف شدن عضوی از آن، تغییراتی در لیست مربوط به آن گره ایجاد می‌شود. از طرفی تغییر در یک لیست منجر به وجود آمدن تغییرات در سایر لیست‌ها در سایر گره‌ها نیز می‌گردد. برای حل این مشکل، به جای استفاده از یک آرایهٔ مرتب شده برای هر گره، از یک درخت دودویی جستجو استفاده می‌شود. با این کار دو هدف برآورده خواهد شد. با استفاده از درخت دودویی جستجو، امکان به روز رسانی سایر گره‌ها هنگام تغییر یک گره، با تعداد عملیاتی محدود فراهم می‌شود و همچنین توانایی جستجوی دودویی پابرجا باقی خواهد ماند. همان‌طور که
جستجوی دودویی پابرجا باقی خواهد ماند. همان‌طور که پیش‌تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه‌داری می‌کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست‌های همسایه نیز تغییر کنند. برای حل این مشکل از روشی شبیه به روش ساخت داده ساختار B tree استفاده می‌شود. با استفاده از این روش، می‌توان اطمینان حاصل کرد
با استفاده از این روش، می‌توان اطمینان حاصل کرد که تعداد داده‌هایی که انتخاب می‌شوند، کمتر از کل داده‌های لیست تقسیم بر d است و همچنین این اعداد در مکان‌های ثابتی از لیست قرار دارند. این موضوع باعث می‌شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره‌ها نیاز دارد. با این روش، توزیع داده‌ها در میان گره‌ها به گونه‌ای خواهد بود که میانگین تعداد عملیاتی
به گونه‌ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت‌های جستجوی دودویی صورت می‌گیرد، عددی ثابت است. مسئلهٔ اصلی در مبحث پویا کردن آبشاره‌سازی جزءبه‌جزء، نگه‌داری اندیس‌ها می‌باشد. همان‌طور که پیش‌تر گفته شد، هر عضو از لیست موجود در یک گره، دو اندیس را نگه می‌دارد. یکی اندیس مربوط به جستجوی خودش در همان لیست و یکی اندیس مربوط به جستجوی آن عضو در لیست همسایه. نگه‌داری این اندیس‌ها به صورت پویا هزینه‌بر است، چراکه با تغییر یک عضو، تعداد اندیس‌هایی که در تمام لیست‌ها باید تغییر کند، عدد