Пошук найкоротшого маршруту

Деталі Створено 27 Березень 2011

При вирішенні складних алгоритмічних завдань з використанням електронних таблиць іноді доводиться стикатися з помилками через виникнення циклічних посилань у розрахунках. У переважній більшості випадків ця помилка пов'язана з неправильною побудовою формул. Але нерідко цикл закладено в алгоритмі розв'язання задачі. Мало хто знає, що Excel дозволяє проводити ітераційні обчислення без використання макросів.

У прикладі до статті за допомогою ітераційних обчислень показано рішення задачі пошуку найкоротшого маршруту в лабіринті. Завдання, на перший погляд, не зовсім економічне, але на практиці може бути застосоване під час оптимізації логістичних та технологічних процесів. Як інший популярний приклад ітераційних обчислень можна навести завдання розподілу непрямих витрат при розрахунку повної собівартості продукції. Тут циклічні обчислення виникають при розподілі витрат допоміжних служб: наприклад, котельня використовує електроенергію, що виробляється в енергоцеху, який, у свою чергу, опалюється тієї ж котельні. Зовсім не обов'язково вирішувати подібне завдання розподілу витрат через ітерації, але знати потенційні можливості Excel буде у будь-якому разі не зайвим.

Опис завдання

Отже, є карта лабіринту з визначеними координатами входу та виходу. Карта представлена у вигляді прямокутної таблиці, де кожен осередок може бути або стіною, або проходом. По периметру є огорожа у вигляді стін, усередині стіни можуть розташовуватися довільним чином. Одиничний хід є кроком в одному з чотирьох напрямків від поточного осередку: вгору, вниз, вправо або вліво. Потрібно прокластинайкоротший маршрут від входу до виходу.

Рішення завдання

Налаштування параметрів Excel

У прикладі використані формули, що працюють лише з увімкненим режимом ітераційних обчислень. Цей режим встановлюється в параметрах Excel, Excel 2000-2003 через менюСервіс\Параметри\Обчислення. В Excel 2007-2010 через діалог налаштування загальних параметрів (розділФормули ):

Крім встановлення числа ітерацій (залежить від розміру лабіринту), бажано встановити ручний режим обчислень. В іншому випадку буде серйозно уповільнений розрахунок за будь-якої зміни вихідних даних.

Завдання пошуку найкоротшого маршруту в лабіринті широко відома в математиці і прикладному програмуванні. Загальний зміст алгоритму можна викласти так:

1. Спочатку всі доступні для проходу комірки очищаються. Надалі до кожного осередку проставляються номери кроків.

2. У комірку "входу" встановлюється значення "1".

3. Цикл поки що осередок, що означає «вихід», не заповнений номером. Вихід із циклу також здійснюється, якщо за повний прохід не було зроблено жодних виправлень – у цьому випадку розв'язання задачі немає.

3.1 Цикл по всіх осередках

3.1.1 У кожен осередок встановлюється мінімальний номер із сусідніх та поточного осередку плюс одиниця. При цьому порожні сусідні осередки порівняно не потрапляють.

4. За успішного результату оптимальним маршрутом є будь-яка послідовність із послідовним збільшенням номера на одиницю від «входу» до «виходу».

Також популярним рішенням цього завдання є рекурентний виклик процедури переміщення з одного осередку до іншого до досягнення виходу.

Будь-яка комірка всередині лабіринту на аркуші «Маршрут» містить таку формулу:

Формула дуже складна (в Excel 2000-2003 досягається максимум за рівнями вкладених дужок усередині однієї формули) і потребує додаткових пояснень. Загальний зміст насправді відповідає описаному раніше циклічному алгоритму. Тобто. визначається мінімум із сусідніх осередків. У цьому «стіни» (негативні значення) не обробляються з допомогою заміни їх значень велике число (999).

Додатково до описаного алгоритму вводиться дробова частина числа, що позначає напрямок руху від попереднього осередку. Усі порівняння виробляються над цілими числами (функціяINT ). Детальна частина введена лише для полегшення показу маршруту через умовне форматування осередку. Також лише з метою умовного форматування у рядках 18-117 знаходиться службова таблиця з розрахунками координат наступного осередку оптимального маршруту. На прикладі заготовлено максимально 100 кроків для аналізу. Розрахунок для показу маршруту можна було організувати будь-яким іншим способом.

Після змін у розташуванні стін та проходів на аркуші «Карта» потрібно перейти на аркуш «Лабіринт» та запустити ручний перерахунок Excel. Це найпростіше зробити через натискання клавішіF9. Карта відобразить початковий лабіринт та маршрут оптимального переміщення. Стіни виділені сірим кольором, маршрут жовтим.

У заголовку вікна виводиться кількість кроків або повідомлення про неможливість прокладання маршруту між входом і виходом. Перевірте різні варіанти розташування стін у лабіринті.

Форматування

Осередки всередині лабіринту містять формули, і відповідно обчислені значення. У прикладі ці значення приховані – бачимо лише колір тла. Числа приховані, по-перше, для простоти сприйняття («для краси»), по-друге, щоб продемонструвати можливості спеціального форматуExcel. Викличте діалог формату комірки (найпростіше це робиться через поєднання клавішCtrl+1 ):

Користувальницький формат «;;;» позначає, що з позитивних, негативних, нульових і текстових значень необхідно показувати порожню комірку.

Для розмальовки осередків використані умовні формати двох типів:

1. "Стіни" обчислюються через формулу як значення "-1".

Висновок

Розширення масштабу лабіринту вимагає копіювання формул та додавання рядків у службову таблицю для показу маршруту. Зверніть лише увагу, що осередок «входу» не містить формули – там значення першого кроку (1,1). Також, ймовірно, потрібно збільшити параметр «Граничне число ітерацій». Будьте обережні зі збільшенням розмірів лабіринту – швидкість розрахунків уповільнюватиметься у геометричній прогресії.