1

Тема: Пошук циклу в транспортній задачі

Хай. От дивіться, є матриця, в деяких клітинках стоять числа, а в деяких ні. Задається початкова клітинка, котра не має містити число. І після цього необхідно віднайти такий шлях по клітинках, вершинами котрого (тобто кутами) будуть клітинки, котрі містять числа.
От приклад http://puu.sh/8kHyI.png
От я думаю, як це запрограмувати...
Була ідея - отримуємо індекси початкової точки.
1) Зміщаємося на клітинку вверх і перевіряємо ряд умов:
2) Якщо клітинка не містить числа, то рухаємось в тому ж напрямку.
3) Якщо ми вийшли за межі матриці або поточна клітинка пройдена - повертаємося в початкову клітинку і змінюємо напрям руху, на правий, наприклад (а потім на нижній та на лівий, ну типу по годинниковій стрілці рухаємось починаючи зверху)
4) Якщо клітинка містить число, то запам'ятовуємо клітинку як початкову, заносимо її в масив, і переходимо до пункту 1. (також помічаємо цю клітинку як пройдену, тому що не можна два рази проходити по одній і тій самій клітинці)
5) Якщо ми повернулись в клітинку "start", то в масиві має бути шлях циклу.

Як вам?

2

Re: Пошук циклу в транспортній задачі

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

3

Re: Пошук циклу в транспортній задачі

koala написав:

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

ее, це тіпо коли входить в стовпчик, потім виходить і знову входить? здається, немона так. От які цикли можуть бути
http://puu.sh/8lf3Z.png

4

Re: Пошук циклу в транспортній задачі

Тобто можна два в стовпчик (лівий нижній малюнок)? Тоді нове питання: чому на ньому не позначено цикл 1-2-7-8? Чи мається на увазі знайти всі можливі цикли?

5

Re: Пошук циклу в транспортній задачі

а хрін його знає... може помилка якась... зара запитаю на математичному форумі.

6

Re: Пошук циклу в транспортній задачі

Може і нема помилки - в транспортній задачі мета буває різна, може, і можна через одне місто двічі їздити.

7

Re: Пошук циклу в транспортній задачі

koala написав:

Може і нема помилки - в транспортній задачі мета буває різна, може, і можна через одне місто двічі їздити.

ну в мене це пошук мінімальних затрат часу на перевезення

8

Re: Пошук циклу в транспортній задачі

Тоді має бути перелік міст, відвідати які обов'язково треба. В іншому разі мінімальний час - 0: просто нікуди не їдемо...

9

Re: Пошук циклу в транспортній задачі

щось я зовсім запутався...

10

Re: Пошук циклу в транспортній задачі

Угу, ніяких міст нема. От вам умова.

Нехай існує m постачальників деякої продукції: A1, A2,...,Am і n споживачів цієї продукції: B1, B2,..., Bn. Відомі запаси продукції у кожного постачальника: a1, a2,..., am і потреби в цій продукції кожного споживача: b1, b2,..., bn. Також відомі вартості перевезень одинці продукції від кожного постачальника до кожного споживача, Cij - вартість перевезення одиниці продукції від i-ого постачальникак до j-ого споживача, i=1,...,m; j=1,..., n.
Скласти план перевезень таким чином, щоб задовольнити потреби всіх споживачів (по можливості) і мінімізувати сумарні витрати на перевезення.

Так от, спершу я будую отой опорний план методом північно-західного кута, а потім в мене вийшла отака табличка
http://puu.sh/8liC0.png
Маленькі циферки в кутках - це вартість перевезення, Ui і Vi - це потенціали, ну це вже метод потенціалів, я їх раніше шукав, після створення опорного плану. Далі ми шукаємо оцінки, а оцінки це як Vi+Ui-вартість перевезення. тобто для клітинки A1,B2 оцінка буде 0+8-7=1. Так от, оцінки ми підраховуємо для всіх незайнятих клітинок, ну в котрих немає великих отих чисел. А потім, клітинка з максимальною оцінкою задається як початок циклу і має будуватись цикл вже.

11

Re: Пошук циклу в транспортній задачі

Koala, лінія має бути ломаною)

12

Re: Пошук циклу в транспортній задачі

чому ви не радієте?

13

Re: Пошук циклу в транспортній задачі

Чуєте, я розробив алгоритм, він гідний для прикладу в першому пості, але не гідний для такого
http://puu.sh/8Ahdl.png

14 Востаннє редагувалося FakiNyan (05.05.2014 18:49:31)

Re: Пошук циклу в транспортній задачі

Як бачете, там точка початку це 1,3. От в мене алгоритм працює так, перевіряє зверху, там нічо нема, перевіряє знизу, знаходить там 290, ок, ця клітинка запам'яталась та додалась в цикл, а далі бачете, там зліва 30, зправа 110, і от тут моя програмка зависає, бо не знає, яку з клітинок обрати. Як гадаєте, як це можна вирішити?

15

Re: Пошук циклу в транспортній задачі

Прихований текст

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

16

Re: Пошук циклу в транспортній задачі

А чому початок не у точці 1,4? У вас же начебто першою умовою йде задоволення потреб усіх користувачів, а уже потім мінімізація затрат?

17

Re: Пошук циклу в транспортній задачі

Torbins написав:

А чому початок не у точці 1,4? У вас же начебто першою умовою йде задоволення потреб усіх користувачів, а уже потім мінімізація затрат?

Тому що перед цим ми шукаємо оцінки незайнятих клітинок, оцінка шукається як
Ui + Vi - цисло в кутку, на тій картинці немає оцих потенціалів, ну Ui і Vi - це потенціали, тому я зара не можу вам довести, що треба саме 1,3, але повірте, от спочатку знаходяться оці оцінки, а потім обирається клітинка з максимальною оцінкою, і вона є початком циклу

18

Re: Пошук циклу в транспортній задачі

Тобто за вашим алгоритмом ви спочатку мінімізуєте затрати, а уже потім будуєте шлях? Мені здається ви переплутали умови, і оцінки треба рахувати уже коли є кілька шляхів, рівноцінних у плані користувачів.

19

Re: Пошук циклу в транспортній задачі

Torbins написав:

Тобто за вашим алгоритмом ви спочатку мінімізуєте затрати, а уже потім будуєте шлях? Мені здається ви переплутали умови, і оцінки треба рахувати уже коли є кілька шляхів, рівноцінних у плані користувачів.

я нічо не плутаю, так в книжці написано же ш, і проблемою зараз є - побудова циклу

20

Re: Пошук циклу в транспортній задачі

Нехай існує m постачальників деякої продукції: A1, A2,...,Am і n споживачів цієї продукції: B1, B2,..., Bn. Відомі запаси продукції у кожного постачальника: a1, a2,..., am і потреби в цій продукції кожного споживача: b1, b2,..., bn. Також відомі вартості перевезень одинці продукції від кожного постачальника до кожного споживача, Cij - вартість перевезення одиниці продукції від i-ого постачальникак до j-ого споживача, i=1,...,m; j=1,..., n.
Скласти план перевезень таким чином, щоб задовольнити потреби всіх споживачів (по можливості) і мінімізувати сумарні витрати на перевезення.

Це цитата з книжки? А що за книжка така?