payamvha/North_RAG huggingface dataset:
از نیمه شب ادامه دارد. این آیین معمولاً در محلات قدیم بروجرد همچون (صوفیون، قدقون، رازان، حافظیه، جعفری، یخچال) برگزار می‌شود که بیشتر در سقاخانه‌های محلات صوفیون و رازان است. در این آیین زنان و مردان ضمن پوشاندن صورت‌هایشان به تکرار نام خدا و روشن کردن شمع به یاد کشتگان کربلا می‌پردازند. افرادی که نذر دارند بعد از آیین چهل منبر به آیین استکان(از دیگر رسوم مردم بروجرد) که در خانه تاریخی آقا معمولاً و در شب غروب تاسوعا برگزار می‌شود می‌روند. در این آیین در بروجرد صاحب سقاخانه‌ها با شیرینی و شربت و گاهی چای
صاحب سقاخانه‌ها با شیرینی و شربت و گاهی چای در زمستان از که نذری هستند پذیرایی می‌شوند. رسم بر این است که اولین شمع را در خانه تاریخی آقا روشن کنند و آخرین شمع را در امام زاده شاهزاده ابوالحسن روشن نمایند. بعد از گذاشتن ۴۰ تا شمع در چهل منبر معمولاً بعد از گرفتن حاجت در سال بعد ۴۱ عدد شمع می‌گذارند که اصطلاحاً ۴۱ منبر گفته می‌شود. گاهی اوقات با پای برهنه و صورت پوشیده و با کسی نیز سخن نمی‌گویند البته بسته به نذر به چهل منبر می‌روند. در مراسم چهل منبر در بروجرد هر سقاخانه بسته به نظر پذیرایی می‌کنند از
بروجرد هر سقاخانه بسته به نظر پذیرایی می‌کنند از منبرگزاران به بجز شیر بسته به رسم در هر سقاخانه هست، شربت شیرینی، چای، خرما،... پذیرایی می‌شود. مراسم چهل منبر بروجرد به شماره ۳۲۶ در آثار ملی و به ثبت ملی رسیده. لاهیجان. مراسم چهل منبر در لاهیجان در این شهر، چهل منبر در شب تاسوعا و چند ساعت قبل از اذان مغرب در این شهر برگزار می‌شود. در این شب خانه‌هایی که در طی سال گذشته مراسم روضه برپا کرده بوده‌اند، منبر آن را در جلوی خانه قرار داده و مقداری برنج، مجمری از آتش و دو ظرف خالی کنارش می‌گذارند. پس از تاریکی
آتش و دو ظرف خالی کنارش می‌گذارند. پس از تاریکی هوا، حاجت‌مندان با ۴۰ شمع مخصوص رشته‌ای و ۴۰ دانه خرما از ۴۰ عدد از این منبرها می‌گذرند، در هر یک شمعی روشن می‌کنند، دانه‌ای خرما بر آن می‌گذارند و مشتی برنج از آن برداشته و برای ادای حاجتشان دعا می‌کنند. اصفهان. این مراسم در اصفهان و شهرضا تحت عنوان چهل و یک منبری شناخته می‌شود.
جنگ شوش آخرین جنگ مابین تمدن ایلام و امپراتوری آشوری نو بود که با پیروزی آشوربانی‌پال پادشاه نیرومند آشور، به پایان رسید. زمان این جنگ در سال ۶۴۵ پیش از میلادی و ۶۳۶ پیش از میلادی ذکر شده‌است. در مورد زمان این جنگ اختلاف در منابع وجود دارد. کتیبه آشور بانیپال در باره فتح و نابودی ایلام چنین می‌گوید:
به نظر می‌رسد که فرگشت پرندگان از دوران ژوراسیک آغاز شده باشد و نخستین پرندگان از گروه دایناسورهای ددپا باشند. در دسته بندی‌های زیست‌شناسی پرندگان برای خود تشکیل دهندهٔ یک رده اند. غازسانان و پرندگان آبزی. در مقایسه با دیگر سرده‌های پرندگان، غازسانان دارای فسیل‌های پیدا شده به نسبت بیشتری هستند، اگرچه بیشتر این فسیل‌ها ناکاملند و شامل استخوان‌های گوناگون و پراکنده از یک پرنده باستانی می‌شوند. برپایه داده‌های فسیلی، هاوارد عنوان کرد که پرندگان آبزی در آغاز ائوسن در ۳۷ تا ۵۵ میلیون سال پیش پدید آمدند. این
ائوسن در ۳۷ تا ۵۵ میلیون سال پیش پدید آمدند. این یافته‌ها همچنین دلیلی بر اینکه پرندگان آبزی در دوره ژوراسیک وجود داشتند ارائه نمی‌دادند.
بزرگ‌باله‌ایان، که با نام‌های شیارنهنگان و رورکوال‌ها نیز شناخته می‌شوند، بزرگ‌ترین گروه نهنگ‌های بی‌دندان هستند که شامل ۹ گونه در ۲ سرده می‌شوند. بزرگ‌باله‌ایان بزرگ‌ترین نهنگ‌های روی زمین را در خود جای می‌دهند؛ از جمله نهنگ آبی که بزرگ‌ترین جانداری است که بر روی زمین پای گذاشته‌است. وزن نهنگ نیزه‌ای معمولی که کوچک‌ترین عضو این خانواده به‌شمار می‌رود به بیش از ۹ تن می‌رسد. روش غذا خوردن بزرگ‌باله‌ایان مبتنی بر مجبور کردن گروه ماهیان و کریل‌ها به ایجاد یک توپ بزرگ از خود و سپس حمله به این توپ طعمه برای
توپ بزرگ از خود و سپس حمله به این توپ طعمه برای تغذیه است. گمان می‌رود که روش تغذیه‌ای این نهنگان بزرگ‌ترین رویداد بیومکانیکی بر روی زمین باشد.
وزارت امنیت دولت موسوم به اشتازی ، سازمان اطلاعاتی آلمان شرقی بود که مرکزش در برلین شرقی قرار داشت. اشتازی حدود ۴۰ سال به نظارت و بررسی فعالیت‌های شهروندان آلمان شرقی مشغول بود، و با استفاده از اطلاعات به دست آمده هرگونه نا آرامی را در نطفه خفه می‌کرد. در سال ۱۹۸۹ میلادی، اشتازی برای ۱۰ میلیون شهروند این کشور پرونده داشت. اشتازی بیش از ۹۱ هزار افسر داشت، و شبکه گسترده خبرچین‌های فعالش نزدیک به ۲۰۰ هزار نفر را شامل می‌شدند. به ازای هر ۶۳ نفر از جمعیت آلمان شرقی یک نفر با اشتازی همکاری داشت. مأموران اشتازی
شرقی یک نفر با اشتازی همکاری داشت. مأموران اشتازی وظایف خود را در چارچوب شعار «دشمن کسی است که دگراندیش باشد» انجام می‌دادند. اشتازی نه‌تنها مخالفان، بلکه احزاب کمونیست «برادر»، مانند حزب توده ایران را هم زیر نظر گرفته بود و در این احزاب هم جاسوسانی داشت. بنا به نوشتهٔ تحقیقی چارلی و رضا؛ از سازمان افسران حزب توده ایران تا سازمان امنیت آلمان شرقی، نوشته بهمن زبردست در شماره ۱۱۳ فصلنامه نگاه نو، محمد پورهرمزان و امیر شفابخش، از اعضای سابق سازمان افسران حزب توده ایران، در سال‌های مهاجرت با اشتازی همکاری
توده ایران، در سال‌های مهاجرت با اشتازی همکاری می‌کردند. اشتازی در تاریخ ۸ فوریه ۱۹۵۰ میلادی تشکیل و در تاریخ ۴ اکتبر ۱۹۹۰ رسماً منحل شد. پس از انحلال. پس از فروپاشی جمهوری دمکراتیک آلمان و وحدت دو آلمان، کارکنان ارشد وزارت امنیت آلمان شرقی دیگر نمی‌توانستند به عنوان «مقامات مهم» در دولت آلمان فدرال مشغول به کار باشند؛ با این حال گفته می‌شود که بیش از ۱۷ هزار نفر از کارکنان سابق اشتازی پس از اتحاد دو آلمان، در نهادهای دولتی این کشور مشغول به کار شدند. هم‌اکنون موزه اشتازی در لایپزیگ و برلین قرار دارند.
استیل در شیمی آلی یک گروه عاملی با فرمول شیمیایی COCH۳ است که گاهی برای نمایش آن از نماد Ac استفاده می‌شود. (باید دقت کرد که با عنصر اکتینیم اشتباه گرفته نشود.) گروه استیل خود دارای یک گروه متیل است که با تک پیوند به یک کربونیل پیوند خورده است. مرکز کربونیل یک اسیل دارای تک الکترون آزاد است (بدون پیوند) که با کمک آن با دیگر مواد "R" پیوند برقرار می‌کند. در آیوپاک برای استیل نام اتانویل (ethanoyl) برگزیده شده‌است ولی این نام کمتر شنیده می‌شود. ترکیب های آلی بسیاری می توانند در نیمهٔ دیگر استیل جای گیرند،
بسیاری می توانند در نیمهٔ دیگر استیل جای گیرند، مانند: استیل کولین کلراید (پیامرسان عصبی)، استیل کوآنزیم A یا Acetyl-CoA، استیل سیستئین، استامینوفن ضد درد و اسید استیل‌سالیسیلیک (acetylsalicylic acid) با نام شناخته شدهٔ آسپرین.
دستجرده روستایی از توابع بخش مرکزی شهرستان آشتیان در استان مرکزی ایران است. دستجرده معرّب «دستگرده» است. هم‌اکنون نیز در محل به «دستگرده» معروف است. در حال حاضر از نظر جغرافیایی جزء روستاهای دهستان سیاوشان می‌باشد. دهستان سیاوشان تابع شهرستان آشتیان است. این روستا دارای امکانات آب، برق، گاز و تلفن است. قنات‌های آن خشک شده و کشاورزی آن به صورت دیم است. دارای راه آسفالته به اراک از طریق داودآباد و به آشتیان از طریق سیاوشان است. جمعیت آن از سال‌ها پیش به‌مرور به تهران مهاجرت کرده‌اند. شغل تعداد کثیری از این
به تهران مهاجرت کرده‌اند. شغل تعداد کثیری از این مردم صنعت سیم لاکی، دستگاه‌های جوش، ترانسفورماتور، اسقاط خودروهای فرسوده و بازیافت است. در ایام تعطیلات و مراسم مذهبی و نوروز مراجعاتی به روستا دارند. اخیراً در زمینهٔ جداول کوچه‌ها اقداماتی صورت گرفته‌است. جمعیت. این روستا در دهستان سیاوشان قرار دارد و براساس سرشماری مرکز آمار ایران در سال ۱۳۹۵، جمعیت آن ۱۷۷ نفر (۷۲ خانوار) بوده‌است.
آیت الله سید مرتضی موسوی قزوینی (زاده:۱۹۳۱ کربلا) مجتهد و مرجع مذهبی فعلی در کربلا و امام جماعت حرم امام حسین است.وی سابقه تبعید و زندگی در ایران، کویت و آمریکا را داشته‌است.وی پدر حسن قزوینی است و از خطیبان و علمای معروف عراق می باشد.
الگوریتم ادموندز کارپ : در علوم کامپیوتر و نظریه گراف الگوریتمEdmonds_Karp پیاده‌سازی ای برای الگوریتم فورد–فالکرسون برای محاسبهٔ مسئله بیشینه جریان در شبکه شاره در زمان formula_1 است. این الگوریتم از الگوریتم ارسال-برچسب که در زمان formula_2 انجام می‌شود سریع تر است. این الگوریتم اولین بار توسط دانشمند شوروی Yefim (Chaim) Dinic در سال ۱۹۷۰ منتشر شد؛ و به‌طور مستقل توسط جک ادموند و ریچارد کارپ در سال ۱۹۷۲ با کاهش زمان الگوریتم قبلی به formula_1 انتشار یافته‌است. الگوریتم. در این الگوریتم می‌خواهیم بیشینه
الگوریتم. در این الگوریتم می‌خواهیم بیشینه شاره را از مبدأ s تا مقصد t پیدا کنیم این الگوریتم شبیه به الگوریتم الگوریتم فورد–فالکرسون است و تفاوتش این است که در این الگوریتم محدودیت الگوریتم فورد–فالکرسون بهبود می‌یابد چرا که که محاسبهٔ مسیر افزایشی را با جستجوی سطح اول پیاده‌سازی می‌کنیم. حال آنکه در الگوریتم فورد–فالکرسون جستجوی عمق اول را اجرا می‌کردیم و به محدودیت زمانی بیشتری نیاز داشت. مسیر پیدا شده باید کوتاه‌ترین مسیر باشد که ظرفیت آماده‌ای دارد؛ که توسط جستجوی سطح اول پیدا می‌شود؛ که ما اجازه
که توسط جستجوی سطح اول پیدا می‌شود؛ که ما اجازه می‌دهیم یال‌ها اندازهٔ واحدی داشته باشند. بیشترین شاره معادل با برش کمینه است. ویژگی دیگر این الگوریتم این است که طول کوتاه‌ترین مسیر هر سری افزایش می‌یابد. اثبات را می‌توان ار منبع ذکر شده مشاهده کرد کاری که در این الگوریتم می‌کنیم این است که با جستجوی سطح اول مسیر افزایشی را می‌یابیم و هر سری اگر که مسیر افزایشی (مسیری که یال پر ندارداین مسئله هم در کد سطح اولی که در زیر آمده مشخص است) داشتیم کمترین ظرفیت را پیدا می‌کند و مینیمم ظرفیت را به جریان همهٔ یال
پیدا می‌کند و مینیمم ظرفیت را به جریان همهٔ یال ها اضافه می‌کند و از آن کم می‌کند. به این صورت بیشینه شار بین مبدأ و مقصد را پیدا می‌کند که معادل با برش کمینه است. در کد زیر نحوهٔ انجام این الگوریتم نشان داده می‌شود. ورودی الگوریتم: ورودی این الگوریتم یک گراف است که یک راس مبدأ s دارد و یک راس مقصد t و روی همهٔ یال‌ها ظرفیت هر یال نوشته شده‌است. خروجی الگوریتم: بیشترین جریان از s به t تا زمانی که مسیر افزایشی با ویژگی‌های بالا وجود دارد. پیچیدگی الگوریتم. زمان اجرای این الگوریتم formula_1 است. به این علت
زمان اجرای این الگوریتم formula_1 است. به این علت که هر مسیر در زمان اجرای formula_5 به‌دست می‌آید. در هر زمان حداقل یکی از E یال سیر می‌شوند؛ که فاصله از یال سیر شده تا مبدأ باید طولانی‌تر از آخرین باری باشد که سیر شده و این طول حداکثر برابر با V تعداد راس‌ها است. پیاده‌سازی. algorithm EdmondsKarp input: C[1..n, 1..n] (Capacity matrix) E[1..n, 1.. ?](Neighbour lists) s (Source) t (Sink) output: f (Value of maximum flow) F (A matrix giving a legal flow with the maximum value) f:= 0 (Initial flow is zero)
the maximum value) f:= 0 (Initial flow is zero) F:= array(1..n, 1..n) "(Residual capacity from u to v is C[u,v] - F[u,v]) forever m, P:= BreadthFirstSearch(C, E, s, t, F) if m = ۰ break f:= f + m (Backtrack search, and write flow) v:= t while v ≠ s u:= P[v] F[u,v]:= F[u,v] + m F[v,u]:= F[v,u] - m v:= u return (f, F) algorithm BreadthFirstSearch input: C, E, s, t, F output: M[t] (Capacity of path found) P (Parent table) P:=array(1..n) for u in 1..n P[u]:= -۱ P[s]:= -2(make sure source is not rediscovered)
P[s]:= -2(make sure source is not rediscovered) M:=array(1..n)(Capacity of found path to node) M[s]:= ∞ Q:= queue() Q.push(s) while Q.size()&gt; ۰ u:= Q.pop() for v in E[u] (If there is available capacity, and v is not seen before in search) if C[u,v] - F[u,v]&gt; 0 and P[v] = -۱ P[v]:= u M[v]:= min(M[u], C[u,v] - F[u,v]) if v ≠ t Q.push(v) else 'return M[t], P return 0, P مثال. در شکل زیر گرافی داده شده‌است که روی یال‌هایش ظرفیت هر یالی قرار دارد و جریان اولیهٔ گذر کرده از یال‌ها برابر با ۰ است می‌خواهیم
گذر کرده از یال‌ها برابر با ۰ است می‌خواهیم جریان بیشینه که از A به G می‌رود را پیدا کنیم. در شکل‌های زیر مراحل مختلف الگوریتم قرار گرفته و در هر شکل یک مسیر با ویژگی‌های ذکر شده با جستجوی عمق اول پیدا شده و در زیر هر شکل مراحل مختلف مربوط به آن قرار گرفته. در زیر هر شکل ظرفیت باقی‌مانده محاسبه شده که برابر با (cf(u,v) = c(u,v) − f(u,v است و طبق الگوریتم بالا بین ظرفیت‌های باقی ماندهٔ یال‌های الگوریتم مقدار حداقلی یافت می‌شود. در آخر می‌خواهیم بیشینه جریان را پیدا کینم. می‌دانیم که جریان بیشینه برابر با
را پیدا کینم. می‌دانیم که جریان بیشینه برابر با برش کمینه است. در این شکل یک برش کمینه وجود دارد که راس‌ها را به راس‌های A B C E وو D F G تقسیم می‌کند با ظرفیت زیر: c(A,D)+c(C,D)+c(E,G)=۳+۱+۱=۵
تعداد متفاوتی الگوریتم برای حل مسئلهٔ مارپیچ وجود دارد که آن‌ها، روش‌های خودکاری برای حل مارپیچ‌ها هستند. الگوریتم‌های موشی تصادفی، دنبال کنندهٔ دیوار، تضمینی و الگوریتم تریماکس برای این طراحی شده‌اند که درون مارپیچ و توسط سیاری استفاده شوند که هیچ دانش قبلی نسبت به توپولوژی مارپیچ ندارد، در حالی که پر کردن بن بست و الگوریتم‌های کوتاه‌ترین راه برای این طراحی شده‌اند که به وسیلهٔ شخص یا برنامهٔ رایانه‌ای که می‌تواند در لحظه کل مارپیچ را ببیند، استفاده شوند. مارپیچ‌هایی که هیچ حلقه‌ای ندارد به مارپیچ‌های
مارپیچ‌هایی که هیچ حلقه‌ای ندارد به مارپیچ‌های استاندارد یا کامل شناخته می‌شوند و با مفهوم درخت در نظریهٔ نظریه گرافها هم ارزهستند. به همین دلیل بسیاری از الگوریتم‌های حل مارپیچ به نظریهٔ گراف مربوط هستند. به طوری که اگر کسی مسیرهای مارپیچ را در جهت درست بکشد، نتیجهٔ حاصل می‌تواند تبدیل به یک درخت شود. الگوریتم موشی تصادفی. این یک روش بدیهی برای این مسئله است که توسط یک روبات غیر هوشمند یا شاید یک موش می‌تواند پیاده‌سازی شود و آن به سادگی حرکت کردن در یک مسیر مستقیم تا رسیدن به یک تقاطع است و بعد انتخاب یک
مستقیم تا رسیدن به یک تقاطع است و بعد انتخاب یک مسیر به صورت تصادفی است تا در آن جهت حرکت شود. گرچه چنین روشی همواره در نهایت به یک پاسخ درست می‌رسد، اما این الگوریتم می‌تواند بسیار کند باشد. دنبال کننده دیوار. دنبال کنندهٔ دیوار، معروف‌ترین قاعده در طی کردن مارپیچ است که به آن قاعدهٔ دست چپ یا قاعدهٔ دست راست نیز می‌گویند. اگر مارپیچ یک فضای همبند ساده باشد، یعنی تمام دیوارهایش به هم یا به دیوارهٔ خارجی مارپیچ متصل باشند، با گرفتن یک دست به یک دیوار مارپیچ تضمین می‌شود که بازی‌کننده گم نمی‌شود و اگر که
تضمین می‌شود که بازی‌کننده گم نمی‌شود و اگر که خروجی وجود داشته باشد به خروجی می‌رسد؛ در غیر این صورت، او دوباره به ورودی بازمی‌گردد در حالی که هر تونل مارپیچ را حداقل یک بار طی کرده باشد. یک دیدگاه دیگر برای این که چرا دنبال کنندهٔ دیوار نتیجه می‌دهد، دیدگاه توپولوژی است. اگر دیوارها متصل باشند، ممکن است به صورت یک حلقه یا دایره تغییر شکل دهند آنگاه دنبال کردن دیوار به حرکت کردن دور دایره از نقطهٔ آغاز تا پایان خلاصه می‌شود. برای پیشبرد این ایده ملاحظه شود که با گروه کردن مؤلفه‌های همبند دیوارهای مارپیچ،
که با گروه کردن مؤلفه‌های همبند دیوارهای مارپیچ، مرزهای آن‌ها به‌طور دقیق همان جواب هستند، حتی اگر بیش از یک جواب وجود داشته باشد. (شکل‌های سمت راست) اگر مارپیچ پیوستهٔ ساده نباشد (یعنی اگر نقطهٔ شروع یا نقاط پایان در مرکز ساختار مارپیچ باشد یا مسیرها از رو یا زیر هم بگذرند.) این روش تضمینی ندارد که در رسیدن به هدف کمک کند. دنبال کردن دیوار می‌تواند در مارپیچ‌های سه بعدی یا با بعدهای بیش تر انجام شود اگر امکانش باشد که به صورت قطعی مسیرهای آن روی صفحهٔ ۲بعدی تصویر شود. برای مثال در یک مارپیچ ۳ بعدی می‌توان
تصویر شود. برای مثال در یک مارپیچ ۳ بعدی می‌توان مسیرهایی که به سمت خارج می‌آیند را به سمت شمال غربی و مسیرهایی که به داخل می‌روند را به سمت شمال شرقی در نظر بگیریم. الگوریتم تضمین کننده. مارپیچ‌های نا پیوسته را نیز می‌توان با الگوریتم دنبال‌کننده دیوار حل کرد به شرط اینکه درگاه‌های ورود و خروج در دیواره بیرونی مارپیچ قرار داشته باشند. اما اگر به‌طور مثال نقطه شروع در داخل صفحه باشد، ممکن است در یک بخش جدا از بخش خروجی باشد ؛ در این صورت تعقیب‌کننده دیوار به‌طور دائمی به دور خود خواهد گشت. الگوریتم تضمینی
دائمی به دور خود خواهد گشت. الگوریتم تضمینی (به نام Jon Pledge این نام‌گذاری شده‌است) این مشکل را حل خواهد کرد. الگوریتم تضمینی طوری طراحی شده‌است که موانع احتمالی را رفع می‌کند و نیازمند انتخاب یک جهت دلخواه حرکت است. هنگامی که یک مانع دیده می‌شود یک دست را (برای مثال دست راست) به‌طور ثابت به دیواره مانع گرفته و حرکت می‌کنیم و به ازای تمام چرخش‌ها زاویهٔ چرخش را به مجموع زوایای چرخش اضافه می‌کنیم و هنگامی که به جهت حرکت اولیه بازگشتیم و مجموع زوایای چرخش صفر شد، یعنی مانع را دور زده‌ایم و مسیر را ادامه
صفر شد، یعنی مانع را دور زده‌ایم و مسیر را ادامه می‌دهیم. در این الگوریتم هنگامی دست را از دیوار برمی‌داریم که مجموع زوایای چرخش و جهت فعلی(نسبت به جهت اولیه) برابر صفر شده باشد. این کار این امکان را به الگوریتم می‌دهد که در مسیرهای تله دار به شکل حرف "G" گیر نیفتد. فرض کنید که الگوریتم(در حرکت روی G) از دیوار اولی به سمت چپ بپییچد آنگاه به وسیلهٔ دیوارها مجبور می‌شود۳۶۰ درجه بچرخد. الگوریتمی که تنها جهت فعلی را دنبال کند در حلقه بی‌نهایت می‌افتد. این چنین که هنگامی که راست‌ترین دیوار پایین را ترک کند،
که هنگامی که راست‌ترین دیوار پایین را ترک کند، دوباره وارد بخش منحنی سمت چپ می‌شود. الگوریتم تضمین‌کننده راست‌ترین دیوار را به دلیل اینکه مجموع زوایای چرخش در آن نقطه صفر نشده، ترک نمی‌کند و دیوار را همچنان دنبال می‌کند تا در نهایت با حرکت به سمت چپ و دقیقاً زیر شکل حرف از آن خارج می‌شود. ین الگوریتم به یک فرد به همراه قطب نما این امکان را می‌دهد که از هر نقطه درونی، بدون در نظر گرفتن مکان اولیه، به یک خروجی در بیرون هر مارپیچ متناهی دوبعدی راه یابد. اما قابلیت یافتن مسیر برای حالاتی که نقطه شروع خارج صفحه
یافتن مسیر برای حالاتی که نقطه شروع خارج صفحه و نقطه پایان داخل صفحه باشد را دارا نیست. الگوریتم تریماکس. الگوریتم تریماکس که توسط چارلز پیر ترماکس معرفی شده، یک روش بهینه برای پیدا کردن راه خروجی مارپیچ است که لازمهٔ آن کشیدن خط‌هایی روی زمین است که مسیری را مشخص کند و تضمین شده‌است که برای تمام مارپیچ‌هایی که مسیرهای خوش تعریفی دارند کار می‌کند. یک مسیر یا هنوز بازدید نشده یا یک بار علامت زده شده یا دو بار. هر بار مسیری انتخاب می‌شود با زدن علامت روی زمین (از انشعاب تا انشعاب) مشخص می‌شود. از ابتدا یک
(از انشعاب تا انشعاب) مشخص می‌شود. از ابتدا یک مسیر اتفاقی انتخاب می‌شود (اگر بیش از یک مسیر وجود داشته باشد) در هنگام رسیدن به انشعابی که هنوز بازدید نشده (هیچ مسیر علامت داری نیست) یک مسیر اتفاقی انتخاب می‌شود (و مسیر را علامتگذاری می‌کنیم). در هنگام رسیدن به انشعاب علامت دار، اگر مسیر کنونی یک علامته باشد مسیر رفته را برمی‌گردیم (و مسیر بازگشت را برای بار دوم علامت گذاری می‌کنیم) اگر این حالت نبود مسیری که کمترین علامت دارد را انتخاب می‌کنیم (و طبق معمول آن را علامت گذاری می‌کنیم)، وقتی بالاخره به نتیجه
آن را علامت گذاری می‌کنیم)، وقتی بالاخره به نتیجه رسیدیم مسیرهایی که دقیقاً یک بار علامت گذاری شده‌اند یک مسیر مشخص به شروع را نشان می‌دهند. اگر خروجی وجود نداشته باشد، این روش، مسیر را تا شروع نشان می‌دهددر حالی که تمام مسیرها دو علامته هستند. در این حالت هر مسیر دقیقاً دو بار طی می‌شود، در هر جهت یک بار. نتیجهٔ این حرکت ردیابی ۲طرفه نام دارد. این الگوریتم در حقیقت نوعی از الگوریتم جستجوی عمق اول است. الگوریتم پر کردن بن‌بست. پرکردن بن بست‌ها الگوریتمی است برای حل مارپیچ‌ها که در آن تمام مسیرهای بن‌بست
برای حل مارپیچ‌ها که در آن تمام مسیرهای بن‌بست غیر از مسیر درست پر می‌شود. برای مواقعی که مارپیچ بر روی کاغذ است یا توسط رایانه قصد حل آن را از این روش می‌توان استفاده کرد . در این الگوریتم تمام صفحه مارپیچ یکجا دیده می‌شود بنابراین برای فردی که داخل یک مارپیچ نامعلوم قرار دارد مفید نمی‌تواند باشد . روش کلی کار این است که اول تمام بن بست‌ها را پیدا کرده و سپس از یک بن بست تا اولین انشعاب را پر می‌کند. ویدئوی اجرای عملی این روش در اینجا قابل مشاهده است.. الگوریتم پرکردن بن‌بست نمی‌تواند به‌طور اتفاقی یک
الگوریتم پرکردن بن‌بست نمی‌تواند به‌طور اتفاقی یک مسیر را از ابتدا حذف کند و باید برای تمام بن بست‌ها اجرا شود زیرا در هر مرحله توپولوژی مارپیچ حفظ می‌شود. علاوه برآن، این رویه به دلیل اینکه پاسخ نهایی نمی‌تواند هیچ بن‌بستی را شامل شود طولانی!!!! خواهد بود . اگر این الگوریتم بر روی مارپیچی کامل (مارپیچی که دور نداشته باشد) اجرا شود، جوابی یکتا خواهد داد اما در صورت وجود دور تنها می‌تواند مسیرهای احتمالی مسئله را به ما بدهد. الگوریتم کوتاه‌ترین مسیر. هنگامی که یک مارپیچ چند راه حل داشته باشد، ممکن است
که یک مارپیچ چند راه حل داشته باشد، ممکن است حل‌کننده بخواهد کوتاه‌ترین مسیر از ابتدا تا انتها را پیدا کند. یک الگوریتم ممکن کوتاه‌ترین مسیر را با پیاده‌سازی الگوریتم جستجوی اول سطح پیدا می‌کند. در حالی که الگوریتمی دیگر، الگوریتم جستجوی آ*، از روش‌های اکتشافی استفاده می‌کند. الگوریتم جستجوی سطح اول از یک صف استفاده می‌کند که خانه‌ها را به ترتیب بر اساس فاصلهٔ آن‌ها از ابتدا تا انتها بازدید می‌کند. هر خانهٔ بازدید شده باید اطلاعات مربوط به فاصلهٔ خودش از نقطهٔ شروع یا اینکه کدام یک از همسایگانش که به شروع
شروع یا اینکه کدام یک از همسایگانش که به شروع نزدیک تر است باعث شده که به صف اضافه شود را نگه دارد. هنگامی که مکان انتهایی پیدا شود مسیر خانه‌ها بازمی‌گردیم تا به نقطهٔ شروع برسیم که این مسیر کوتاه‌ترین مسیر است منابع. Charles Tremaux (° 1859 - † 1882) École Polytechnique de Paris (X:1876), French engineer of the telegraph
سِر جان فردریک ویلیام هرشل (زادهٔ ۷ مارس ۱۷۹۲ – درگذشتهٔ ۱۱ مهٔ ۱۸۷۱) ریاضیدان، ستاره‌شناس، شیمیدان، عکاس و مخترع تجربی بود. او چند سال نیز در کار گیاه‌شناسی فعالیت داشت. جان پسر ماری بالدوین و منجم سرشناس، فردریک ویلیام هرشل، و پدر ۱۲ فرزند بود. هرشل بنیادگذار استفاده از سیستم روز جولین در ستاره‌شناسی است. او هفت قمرِ زحل و چهار قمرِ اورانوس را نامگذاری کرده‌است. جان خدمات زیادی به علم عکاسی عرضه داشته و بررسی کوررنگی و تأثیر شیمیایی پرتو فرابنفش از کارهای اوست. زندگی. هرشل در اسلاو، باکینگهام‌شایر متولد
اوست. زندگی. هرشل در اسلاو، باکینگهام‌شایر متولد شد، وی پسر مری بالدوین و ستاره شناس ویلیام هرشل بود. وی مدت کوتاهی در کالج ایتن و کالج سنت جان، کمبریج تحصیل کرد و در سال ۱۸۱۳ فارغ التحصیل شد.
الگوریتم نیدلمن وانچ یک همترازی سراسری بر دو ترتیب متوالی (مانند A و B) انجام می‌دهد. معمولاً در بیوانفورماتیک برای همترازی توالی‌های پروتئینی یا نوکلئوتیدی کاربرد دارد. این الگوریتم در سال ۱۹۷۰ توسط سول نیدلمن و کریستین وانچ ارائه شد. این الگوریتم نمونه‌ای از برنامه‌ریزی پویا است و اولین کاربرد برنامه‌ریزی پویا در مقایسهٔ توالی‌های زیستی است. مقدمه. این الگوریتم را می توان برای هرجفت رشته ای به کار برد. در راهنمای زیر از دو توالی دی ان ای کوتاه به عنوان مثال استفاده می شود: GCATGCT GATTACA ساخت جدول. ابتدا
استفاده می شود: GCATGCT GATTACA ساخت جدول. ابتدا جدولی مانند زیر بسازید: در سطر اول، جدول رشته اول قرار می گیرد و محل شروع این رشته ستون سوم است. هم چنین رشته دوم در ستون اول قرار گرفته و محل شروع آن از سطر سوم است. در ابتدا هیچ عددی در جدول وجود ندارد. انتخاب سیستم امتیاز دهی. هنگام هم تراز سازی دو رشته، ممکن است سه حالت برای حروف رخ دهد: به هر یک از این حالات یک امتیاز اختصاص داده می شود و امتیاز یک هم تراز سازی از جمع امتیاز های هر جفت از حروف متناظر به دست می آید. سیستم های متفاوتی برای امتیاز دهی وجود
می آید. سیستم های متفاوتی برای امتیاز دهی وجود دارند که تعدادی از آن ها در بخش سیستم های امتیاز دهی ذکر شده اند. سیستم استفاده شده در اینجا، همان سیستم الگوریتم نیدلمن-وانچ است که در آن امتیاز تطابق 1+ و امتیاز عدم تطابق، درج یا حذف 1- می باشد. به طور مثال امتیاز هم ترازی زیر برابر 2- است زیرا: GCATG-CT GATT-ACA +1-1-1+1-1-1+1-1=3-5=-2 پر کردن جدول. از ستون دوم سطر دوم شروع کنید و در آن مقدار 0 را قرار دهید. سپس سطر به سطر پیش روید و امتیاز هر خانه را محاسبه کنید. این امتیاز از اضافه کردن امتیاز خانه مجاور
کنید. این امتیاز از اضافه کردن امتیاز خانه مجاور سمت چپ، بالا یا بالا چپ (به صورت قطری) به امتیاز مناسب برای تطابق، عدم تطابق یا درج-حذف به دست می آید. در واقع برای محاسبه امتیاز 3 گزینه وجود دارد: در نهایت امتیاز نهایی این خانه با بیشترین امتیاز در میان سه امتیاز به دست آمده برابر است. با توجه به اینکه خانه های سطر دوم دارای خانه بالا یا بالا-چپ نیستند، پس تنها خانه سمت چپ می تواند برای محاسبه امتیاز استفاده شود. به این ترتیب سطر دوم به ترتیب از چپ دارای امتیاز های 0، 1-، 2-، 3-،...،7- می شود. استدلالی
امتیاز های 0، 1-، 2-، 3-،...،7- می شود. استدلالی مشابه برای ستون دوم نیز به کار می رود که در نتیجه آن جدولی به شکل زیر حاصل می شود. حال برای محاسبه امتیاز خانه سطر سوم و ستون سوم، 3 حالت وجود دارد: در نهایت بیشترین امتیاز در میان این 3 یعنی عدد 1 وارد این خانه می شود. هم چنین باید پیکان مربوط را ذخیره کرد که یک پیکان قطری از خانه(3,3) به خانه (2,2) است. به همین ترتیب تمامی خانه های جدول پر می شوند تا امتیاز نهایی بهترین هم ترازی به دست آید. کامل شده این جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم
جدول در شکل 1 آمده است و طبق آن امتیاز بهترین هم ترازی این دو رشته برابر با 0 است. بازگشت به مبداء. به وسیله تعدادی پیکان مسیری را از گوشه پایین-راست جدول به گوشه بالا-چپ جدول نشان دار کنید. سپس از طریق این مسیر و طبق قوانین زیر توالی متناظر مسیر را بسازید: پیکان افقی یک جای خالی("-") را با حرف ستون متناظر مبدا پیکان و پیکان عمودی حرف سطر متناظر مبدا پیکان را با یک جای خالی تراز می کند. با توجه به قواعد بالا و طبق شکل 1، یکی از بهترین هم ترازی ها برای دو رشته ذکر شده در زیر آمده است: GCA-TGCT G-ATTACA
رشته ذکر شده در زیر آمده است: GCA-TGCT G-ATTACA سیستم های امتیاز دهی. سیستم پایه. ساده ترین سیستم امتیاز دهی به هر یک از سه حالت تطابق، عدم تطابق و درج-حذف یک مقدار نسبت می دهد. به عنوان مثال ممکن است امتیاز تطابق برابر 1 و امتیاز عدم تطابق یا درج-حذف 1- در نظر گرفته شود. که در این حالت بیشترین امتیاز مربوط به کمترین فاصله ویرایش است. به عنوان مثالی دیگر ممکن است به تطابق امتیاز 0 و به عدم تطابق و درج-حذف امتیاز 1- نسبت داده شود. که در این حالت امتیاز یک هم ترازی در واقع فاصله ویرایش میان دو رشته است.
هم ترازی در واقع فاصله ویرایش میان دو رشته است. سیستم های امتیاز دهی متفاوت برای شرایط مختلف طراحی شده اند. به عنوان مثال اگر وجود فاصله را اتفاق بدی در هم ترازی در نظر بگیریم، میتوانیم از امتیاز بندی مانند مثال زیر استفاده کنیم: امتیاز تطابق =1+ امتیاز عدم تطابق=1- امتیاز فاصله=7- ماتریس مشابهت. سیستم های امتیاز دهی پیچیده تر، نه تنها برای نوع جایگزینی بلکه برای حروف مختلف نیز امتیاز های متفاوتی در نظر میگیرند. به عنوان مثال، ممکن است به تطابق بین 2 حرف A امتیاز 1 و به تطابق بین 2 حرف G امتیاز 3 داده شود.
1 و به تطابق بین 2 حرف G امتیاز 3 داده شود. که این به معناست که تطابق G ها از اهمیت بیشتری برای هم تراز سازی برخوردار است. از این روش امتیاز دهی برای عدم تطابق نیز می توان بهره گرفت. به عنوان مثال ممکن است به دو حرف A,G امتیاز 1- و به دو حرف T,G امتیاز 2- اختصاص داده شود. برای نمایش همه حالات ممکن امتیاز دهی از ماتریس مشابهت استفاده می شود. ماتریس زیر نمونه ای از ماتریس های مشابهت برای مثال بالاست: به عنوان مثال، ماتریس زیر، ماتریس مشابهت امتیاز گذاری مورد استفاده در شکل 1 است: با توجه به اینکه امتیاز عدم