Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
#1

Метод потенциалов Транспортная задача - C++

23.04.2014, 08:52. Просмотров 1002. Ответов 8
Метки нет (Все метки)

Как можно найти цикл в матрице ?
нехватает этой чудо функций
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2014, 08:52     Метод потенциалов Транспортная задача
Посмотрите здесь:

Транспортная задача. Метод потенциалов. - C++ Builder
Здравствуйте. не получается сделать Метод потенциалов,а именно не получается написать ПУТЬ перемещения.Он почему то ставит криво + и...

Транспортная задача (методом потенциалов) - C++
Доброго времени суток форумчане! Нужна прога по вычислению транспортной задачи методом потенциалов. Пытался сам сделать, но как-то не...

Транспортная задача (методом потенциалов) - C++
В универе задали сделать транспортную задачу. Знания только одного семестра ОП. Сделал заполнение таблицы поиск потенциала и проверку...

Транспортная задача(метод минимального элемента) - C++
Здравствуйте! Нужно написать задачу, которая методом минимального элемента составит опорный план для транспортной задачи. Не получается...

Транспортная задача: метод северо-западного угла - C++
Здесь уже была похожая тема, но там так и нет ответа. Программа делает только одну итерацию. //libraries #include <stdafx.h> ...

Метод потенциалов на максимизацию - C++
Всем доброго времени суток. Столкнулся с проблемой нехватки алгоритма. Входные данные два массива одинаковой размерности. В первом...

Транспортная задача - C++
Здравствуйте! Помогите пожалуйста составить задачу методом минимального элемента и методом потенциалов с улучшением плана и правильным...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
5602 / 2636 / 242
Регистрация: 01.11.2011
Сообщений: 6,495
Завершенные тесты: 1
23.04.2014, 09:49     Метод потенциалов Транспортная задача #2
Цитата Сообщение от Qazan Посмотреть сообщение
Как можно найти цикл в матрице ?
Не могли бы вы пояснить, что имеется в виду под циклом?
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.04.2014, 08:52  [ТС]     Метод потенциалов Транспортная задача #3
SatanaXIII,

Пусть имеется некоторая матрица размера (n,m) . В ней выделены n + m - 1 элементов.Назовем их Хорошими.
Если в Хороших элементах нет цикла то они ОченьХорошие.

Циклом в Хороших элементах называется такое подмножество A элементов из Хороших,что
в каждой строчке и столбце наидется ровно два элемента .

Например ,
1. (1,1) (1,3) (3,3) (3,5) (5,5) (5,1)
2. (1,1) (1,3) (3,3) (3,1)
для матрицы размерности больше 5
Izual
94 / 119 / 6
Регистрация: 13.11.2012
Сообщений: 1,551
24.04.2014, 11:24     Метод потенциалов Транспортная задача #4
Цитата Сообщение от Qazan Посмотреть сообщение
Циклом в
Цитата Сообщение от Qazan Посмотреть сообщение
элементах называется
Цитата Сообщение от Qazan Посмотреть сообщение
подмножество A элементов
Цитата Сообщение от Qazan Посмотреть сообщение
что в каждой строчке и столбце наидется ровно два элемента
"А" - это сколько? Если есть n на m...
Если опустить "А" и взять в разсчёт что нужно ровно два элемента одинаковых найти - ну берите и сравнивайте.
Создайте переменную, например int k=0; Начинаете перебором сравнивать элементы.. блин у тебя 169 репутация, а задача начального уровня. Подобные задачи есть в книге, которая является азом обучения "С/С++ в задачах и примерах" автор Н.Культин.
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.04.2014, 14:17  [ТС]     Метод потенциалов Транспортная задача #5
Izual, подмножество - тогда наверное меньше чем m + n - 1

а все нужно , чтобы каждый индекс встречался дважды при количестве элементов больше 3


PS : По факту моя репутация 20
Izual
94 / 119 / 6
Регистрация: 13.11.2012
Сообщений: 1,551
24.04.2014, 15:16     Метод потенциалов Транспортная задача #6
Цитата Сообщение от Qazan Посмотреть сообщение
наверное меньше чем m + n - 1
Что значит наверное, что препод не уточнил?

Если у нас вся матрица это m x n, то (если взять m=5 и n=6) всего будет из примера 30 элементов. Но мы разсматриваем только m+n-1, значит всего 10 из 30.. И какие эти 10? Не очень ясно где эти 10 элементов вообще находятся...
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.04.2014, 16:04  [ТС]     Метод потенциалов Транспортная задача #7
Izual, вы меня не поняли

если я говорю о подмножестве, значит это меньше либо равно ,не так ли ?

Я понял ,что задачу следует интерпретировать так

Найти все элементы у которых координаты встречаются по два (рассматривая отдельно i и j е координаты).

у меня пока такая идея :

создать массив целых чисел b размером max{n,m}

теперь проходя по Хорошим элементам
делать b[i]++; & b[j]++;

потом

C++
1
2
3
4
5
6
7
8
9
10
 
   for(int i = 0;i < min{n,m};i++)
   { 
       if(b[i] != 4) return false;
   } 
   for(iunt i = min{n,m};i < max{n,m};i++)
   {
       if(b[i] != 2) return false;
   }
   return true;

Как вы думаете оптимально ?
может можно быстрей и экономней ?
Izual
94 / 119 / 6
Регистрация: 13.11.2012
Сообщений: 1,551
24.04.2014, 16:39     Метод потенциалов Транспортная задача #8
Цитата Сообщение от Qazan Посмотреть сообщение
может можно быстрей и экономней ?
Зачем? Вы ведь не будете эту формулу использовать для грамоздких целей, где под миллион n m. А раз так то и оптимизировать не вижу смысла, к тому же предполагаю что задача изначально не для usability, а для развития логики и демонстрации умений создавать алгоритм. А раз так - то вы уже сделали то что надо было.
Хотя с другой стороны я оптимизацией никогда не занимался в "мелочном плане", оптимизация нужна там где это жизненно необходимо - т.е. для реального использования при этом соотнося "цена и качество", ведь оптимизировать можно и через сам ассемблер, но смысла писать код на ассемблере - ну никакого нет. Так что то что я подчеркнул из книги Фленова "Иссуство программирования C++ и DirectX", так это то что оптимизировать надо в пределах разумного и только если игра стоит свеч.
У вас получился минимизированный код - это уже хорошо, я обычно чисто на это делаю упор - чем меньше строк кода - тем лучше. А то ведь когда реальные программы делаеш, то оптимизация может принести вместо 2-3 строк все 20-30, а это слишком усложняет жизнь, особенно когда изначально под 10 000 строк кода.(и в 20 раз если умножить - будет ппц, не стоит оно того, т.е. возможно только в отдельных моментах. Да и сила нынешних компов растёт, с появлением много процессорных чипов появился смысл делать много поточные приложения, которые оптимизируют в 1.9 раз(почти в 2) как минимум - а это куда больше чем даже самый навороченный оптимизированный код.(ну в передлах разумного построения изначального истественно)
Так что не замарачивайтесь имхо..
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.04.2014, 20:23     Метод потенциалов Транспортная задача
Еще ссылки по теме:

транспортная задача - C++ Builder
Всем привет! помогите пожалуйста переделать программу с Delphi на Builder C + +. заранее спасибо =))

Транспортная задача - C++
Всем привет) Пишу решение транспортной задачи по методу минимального элемента. Сейчас нахожусь на стадии заполнения матрицы перевозок....

Транспортная задача - C++ Builder
прошу помощи...нужно написать транспортную задачу...ни как не могу ее сделать...пожалуйста, помогите мне...

Транспортная задача - C++
Всем добрый день! Второй месяц не могу справиться, помогите пожалуйста. Очень нужна программа к этой задаче! Заранее спасибо!...

Транспортная задача - Visual C++
Помогите реализовать цикл для улучшения опорного плана.Задача решается методом потенциалов.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Qazan
211 / 59 / 9
Регистрация: 30.04.2013
Сообщений: 797
Записей в блоге: 10
24.04.2014, 20:23  [ТС]     Метод потенциалов Транспортная задача #9
Izual, для домашки по методам оптимизаций
лень писать все итераций
Yandex
Объявления
24.04.2014, 20:23     Метод потенциалов Транспортная задача
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru