21

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

Torbins написав:

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

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

Так, Математичні методи дослідження операцій, то у нас викладач в універі сам написав

22

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

Ну якщо книжка, то там мабуть ця задача йде після якоїсь глави. Тоді має бути приблизно зрозуміло якими методами цю задачу розв'язувати.

23

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

Torbins написав:

Ну якщо книжка, то там мабуть ця задача йде після якоїсь глави. Тоді має бути приблизно зрозуміло якими методами цю задачу розв'язувати.

методом потенціалів

24

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

гаразд... абсорбуйтеся! Подивіться на проблему з чистим розумом. Що в нас є? Матриця, таке собі 2D поле розділене на клітинки. Які клітинки можуть бути? Зафарбовані, і не зафарбовані. Що нам потрібно створити? Цикл, котрий починається в незафарбованій клітинці. Але ж цикл, це крива лінія, так? А в яких клітинках ми можемо змінювати напрям циклу? Лише в зафарбованих клітинках! Як на картинці... тут сині клітинки - це зафарбовані, темночервона - початок циклу, а всі інші - незафарбовані. І от ми бачимо такий цикл.
І яким же має бути алгоритм, котрий сам знаходив би цей цикл?
http://не-дійсний-домен/8KrNZ.png

25 Востаннє редагувалося FakiNyan (13.05.2014 10:34:27)

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

Мій недороблений варіант. Пишемо два методи, перший буде шукати зафарбовані клітинки по вертикалі, а другий - по горизонталі. Починаємо з вертикалі, йдемо вверх, там пусто, йдемо вниз, знаходимо зафарбовану клітинку 4,5. Далі змінюємо напрям на горизонталь. Йдемо вправо, знаходимо зафарбовану клітинку 4,6. Далі вертикаль, не знаходимо жодної зафарбованої клітинки, кінець мого недоалгоритму. Пропонуйте ваші.

26

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

всім дякую кароч

27

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

Я б почав з прямого перебору. А інтелект додавав уже потім.

P.S. Слава дощу!

28

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

Torbins написав:

Я б почав з прямого перебору. А інтелект додавав уже потім.

P.S. Слава дощу!

Я теж дощ люблю, ок, буду перебирати... я ще напишу тут свій алгоритм, і опишу, які виникнуть проблеми.

29

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

господи, да це ж нереально, чому я маю цим займатись? воно мені не цікаво, я не хочу його робити, дайте мені робити диплом!!! вже є купа сайтів з онлайн-сервісом, котрий вирішить вам ту задачу будь-яким методом, чому я маю це все сам писати??????????? Ви тільки подивіться на це
http://не-дійсний-домен/8Sjwg.png
тут є два цикла, і як воно має шукатись? в голові все легко бачется, але як воно має бути написаним на тому сраному c#, це ж не просто перебір, це суперперебір всього можливого

30

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

я внезапно дізнався. що цикл може бути тільки один

31

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

коротше, щось зробив, рішення маю, але тільки для одної задачки. підставляти інші значення боюсь, тому що якщо будуть помилки, то знову лізти в код і щось робити треба буде, тепер в мене на черзі угорський метод...