Всем здрасьте. Встала задача - реализовать алгоритм решения транспортной задачи методом потенциалов. Чисто учебный проект. Типа курсовой Если есть у кого готовый, приемлемо написанный на С/С++ под винду - буду счастлив, т.к. смогу немного поспать Ж) всякие паскале-подобные наречия интересуют в меньшей степени. А вообще вопрос в следующем - как построить цикл(цепь) на этапе поиска элемента матрицы стоимостей для включения в базис. Мне в голову пришло 2 варианта. 1. пусть каждой клетке с базисным x<sub>ij</sub> в опорном плане соответствует вершина графа. если каждая "базсная" клетка стоит на одной строке (в одном столбце) с другой такой клеткой или начальной клеткой - соответствующие вершины графа связываются ребром. поэтапно удаляем висячие вершины и вершины, соответствующие клеткам, стоящим не на "изломах" цикла. если на некотором шаге удаляется начальная вершина - пипец, цикла нет. если удалить ничего не удаётся - финиш. 2. построением дерева (или, что почти то же, рекурсией) произвести поиск пути с поочередной сменой направлений (по строке-по столбцу) из начальной клетки в начальную Второй способ кажется более мутным, хотя позволяет найти кратчайший цикл. Правда, в ТЗ цикл может быть только один Какой способ оптимальнее. Может есть и ещё способы? (наверняка есть) У Таха (Исследование операций) ни слова про реализацию поиска. И еще - как находить потенциалы. Старик Гаусс для столь разреженных матриц с единичными коэффициентами - из пушки по воробьям. За соображения заранее спасибо.
ладно. видать, решать мне все самому. построение цикла я сделал. реализовал вариант с рекурсией, но без рекурсии, как таковой. все пройденные базисные клетки в списке сохраняются. фактически - линейно хранимое "уровень за уровнем" дерево. элементы каждого уровня сортируются по величине пройденного пути - чтобы идти всегда кратчайшему возможному. если кому интересно - чуть позже могу выслать почтой/асей теперь еще вопрос: как находить потенциалы? пока не придумал. подскажите, кто знает (см. прошлый пост)
