Не совсем понятен алгоритм построения цикла(ломаной прямой) в данном методе. Вот, что я понял, и в чем вопросы:

  1. выбрать базисную ячейку с минимальной оценкой $%s_{ij}=c_{ij}-u_i-v_j$%
  2. от нее (записав в эту ячейку "+") начать строить ломаную линию через базисные ячейки, чередуя + и - на вершинах. Вот с этого момента не ясно: нужно провести линию к дальней справа базисной ячейке? А если ее нет, то к той небазисной, ближе к которой находится базисная, и далее по такому же принципу обозначать вершины и линии?
  3. ко всем ячейкам с вершинами прибавить то значение, которое является минимальным среди всех базисных ячеек с вершинами, учитывая знак в ячейке

задан 26 Окт '15 21:55

@Ni55aN: здесь обсуждается конкретный алгоритм, поэтому нужно иметь под рукой точное его описание. Суть везде примерно одна и та же, но обозначения в разных источниках могут отличаться. Поэтому нужно дать ссылку на используемую литературу.

(26 Окт '15 22:08) falcao

Дело в том, что каждый цикл имеет свою "стоимость пересчета" Я обычно проверяю возможные замкнутые циклы именно по стоимости пересчета. Останавливаюсь на максимальной. Иногда,(не часто)бывает как в шахматах, выбираю не самый лучший по стоимости пересчета цикл, так это не беда. Придется выполнить лишнюю итерацию. Хотя это не очень приятно.

(26 Окт '15 23:25) nynko
10|600 символов нужно символов осталось
1

начать строить ломаную линию через базисные ячейки - да, это просто указание, что выполняется простой перебор вариантов... по крайней мере, я не встречал описания методов, которые оптимизируют выбор вершин для цикла...

нужно провести линию к дальней справа базисной ячейке? А если ее нет, то к той небазисной, ближе к которой находится базисная, - всегда есть базисные клетки и в строчке и столбике для выбранной клетки из пункта 1... а вот последующее перемещение (под прямым углом звена ломаной) из базисной клетки возможно не всегда... поэтому Вы должны рассматривать другой вариант перемещения...

Ещё раз повторюсь, что вы просто перебираете варианты построения ломанных до тех пор, пока не получите замкнутый цикл... (насколько я понимаю он будет единственным вариантом при данных базисных клетках и клетки из пункта 1) ...

ссылка

отвечен 26 Окт '15 23:27

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×48

задан
26 Окт '15 21:55

показан
341 раз

обновлен
26 Окт '15 23:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru