برای ساده کردن مطالعه روی باکتری ها، اغلب پیکربندی آنها را با مدل کردن تصویر میکروسکوپی آنها به صورت یک جدول دوبعدی ساده میکنند.همانطور که میتوانید در شکل یک ساده سازی جدولی تصویری از یک باکتری معروف را، که به نام DilBactrium شناخته میشود، ببینید، برخی از خانه های جدول به عنوان بدن باکتری اشغال شده اند، در حالی که دیگر خانه ها خالی هستند.
تعدادی از خانههای خالی جدول از قبل با دیگر مادههای مرده اشغال شدهاند و بنابراین نمیتوانند توسط باکتری اشغال شوند. فرض میکنیم G مجموعه کل خانههای جدول باشد که توسط مادههای مرده اشغال نشدهاند.
دو خانه از جدول همسایه نامیده میشوند اگر یک ضلع مشترک داشته باشند و ترتیب L از خانههای جدول یک مسیر نامیده میشود اگر خانههای آن به صورت متوالی همسایه یکدیگر باشند. همچنین مجموعهای از خانههای جدول مانند S همبند نامیده میشود که به ازای هر دو خانه موجود در آن مانند c1 و c2، مسیری شامل این دو خانه وجود داشته باشد که تنها شامل اعضای S باشد (به عبارت دیگر بین هر دو عضو آن مسیری وجود داشته باشد که تنها از اعضای S گذر میکند). با در نظر گرفتن این تعاریف یک سادهسازی جدولی باکتری (که با GSB آن را نمایش میدهیم) درواقع یک زیر مجموعه با سایز ثابت و همبند از G است.
از آنجا که یک باکتری زنده حرکت میکند، حرکت آنها نیز باید در این سادهسازی، پیش بینی و مدلسازی شود. یک حرکت باکتری که آن را با زیرمجموعه همبند S مدل میکنیم، در این ساده سازی به این صورت تعریف میشود که یکی از خانه های عضو S مانند c1 از آن حذف و یکی از خانه های G که تا کنون در S نبوده است به آن اضافه میشود طوریکه زیر مجموعه (S – {c_1}) \cup {c_2} کماکان همبند باشد. این زیر مجموعه معرف پیکربندی جدید باکتری بعد از این حرکت است (منظور از پیکربندی در واقع در نظر گرفتن توامان مکان و ظاهر باکتری است).
یک GSB میتواند بعد از انجام تعدادی حرکت به وضعیتی کاملا متفاوت با وضعیت اولیه برسد و به وضوح برای یک GSB راه های مختلف زیادی برای رسیدن به وضعیت نهایی گفته شده وجود دارد. با داشتن پیکربندی اولیه و نهایی یک GSB، وظیفه شما یافتن کمترین تعداد حرکت مورد نیاز برای رسیدن GSB از پیکربندی اولیه به پیکربندی نهایی است. میتوانید فرض کنید که پیکربندیهای اولیه و نهایی هیچ خانهی مشترکی ندارند.