Модераторы: volvo877, Snowy, MetalFan
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> задача о назначении, венгерский метод 
:(
    Опции темы
mgf
Дата 26.4.2010, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 33
Регистрация: 23.4.2009

Репутация: нет
Всего: нет



помогите пожалуйста разобраться с задачей. Задача решается венгерским методом. Дана матрица:
10  20  12  5
3    14   9   1
13   8    6   9
7    15  8   10
Где строки - это базы, а столбцы - торговые точки. Нужно найти оптимальное расстояние доставки товара от баз до торговых точек. 
Алгоритм таков:
1. находим минимум по строкам и вычитаем его из всех элементов строки. В каждом столбце находим минимум и вычитаем из каждого элемента столбца. 
2. Находим строку с 1 нулем и называем нулевой элемент отмеченным. В столбце, где находится отмеченный ноль, все остальные нули зачеркиваются и не рассматриваются.
3. повторяем пункт (2), до тех пор, пока это возможно. 
4. находим столбец я 1 нулем и запоминаем его. В строке, где находится 1 ноль, остальные нули зачеркиваем. 
5. продолжаем повторять пункт (4), пока это возможно. 
6. проводим вертикальные и горизонтальные линии, пересекающие все отмеченные нули , получаем новую матрицу из не зачеркнутых чисел. Находим минимум в этой матрице  и вычитаем его из всех не зачеркнутых элементов, и прибавляем ко всем числам, которые стоят на пересечении прямых.

К полученной матрице алгоритм применяется снова, пока каждая строка и и столбец матрицы не будет содержать ровно 1 отмеченный ноль. 
На местах нулей будет содержаться оптимальное решение.
Реализация на паскале. 

Проблем с заполнением матрицы, нахождением минимума, максимума нет.. А вот как применять сами пункты 2,4,6 затрудняюсь.. помогите пожалуйста с реализацией алгоритма!
PM MAIL   Вверх
Romtek
Дата 27.4.2010, 13:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 153
Регистрация: 7.12.2004
Где: Холон

Репутация: нет
Всего: 4



Построй блок-схему алгоритма на-русском языке. Иначе помощи не видать, как своих ушей.
--------------------
Romiras HomeLab - материалы и статьи по разработке ПО, моделирование алгоритмов, обработка и анализ информации, нейронные сети, машинное зрение и пр.
PM WWW   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi"
THandle
Rrader
volvo877

Запрещается!

1. Обсуждать и делится взломанными компонентами или программным обеспечением

2. Публиковать ссылки на варез

3. Оффтопить

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, THandle, Rrader, volvo877.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Object Pascal: кроссплатформенные технологии | Следующая тема »


 




[ Время генерации скрипта: 0.0382 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.