نقشهي استان الف در شكل 1 و استان ب در شكل 2 نشان داده شده است كه در آن هر نقطه، يك شهر و هر خط يك جاده بين دو شهر است.در هر دو شكل، فاصلهي شهرهاي A و B برابر است با حداقل تعداد جادههايي كه بايد طي كنيم تا از A به B برسيم. يك دزد در يكي از اين شهرها – كه از قبل مشخص نيست – مخفي شده است.
براي پيدا كردن اين دزد مجاز هستيم بهصورت ذيل عمل كنيم:
| - در ابتداي هر روز يكي از شهرها بهنام A را انتخاب و آن را جستجو ميكنيم:
| اگر دزد در آن شهر باشد او را دستگير ميكنيم. اگر دزد در آن شهر نباشد بهكمك دستگاهي، فاصلهي شهر A را تا شهري كه دزد در آن قرار دارد پيدا ميكنيم.. | - در انتهاي هر روز دزد از شهري كه در آن قرار دارد به يكي از شهرهاي «مجاور» آن ميرود. دقت كنيد دزد حتماً جاي خود را عوض ميكند. |
بهنظر شما در هر استان حداقل به چند روز نياز داريم تا مطمئن شويم دزد را دستگير خواهيم كرد؟
دو شهر را «مجاور» ميگوييم اگر با يك جاده بههم متصل باشند.