| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > задача о назначении |
| Автор: mgf 26.4.2010, 19:15 |
| помогите пожалуйста разобраться с задачей. Задача решается венгерским методом. Дана матрица: 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 затрудняюсь.. помогите пожалуйста с реализацией алгоритма! |
| Автор: Romtek 27.4.2010, 13:41 |
| Построй блок-схему алгоритма на-русском языке. Иначе помощи не видать, как своих ушей. |