2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Транспортная задача: нахождение цикла (замкнутого пути)
Сообщение31.07.2012, 08:58 
При решении транспортной задачи как в методе потенциалов так и в методе падающего камня ключевым моментом при реализации является нахождение цикла (замкнутого пути). К сожалению, не нашел ни одного толкового описания алгоритма, готового к реализации. Например, для нахождения цикла предлагается следующий метод:
Цитата:
Поставьте курсор мыши в выбранную свободную ячейку. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

И это самое лучшее, что смог найти :-(
В результате нескольких часов страданий придумал следующую эвристику:
Отмечаем ячейку, для которой нам нужно найти цикл и все ячейки опорного плана. Вычеркиваем все строки и столбцы с единственным отмеченным элементом до тех пор пока не сможем ничего вычеркнуть. В итоге у нас останутся отмеченными только узлы искомого пути.
Проверял на тестовых данных - вроде работает. Это верный алгоритм?

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

 
 
 
 Re: Транспортная задача: нахождение цикла (замкнутого пути)
Сообщение31.07.2012, 11:00 
Я когда-то писал программу для транспортной задачи...на бейсик. Поиск пути осуществлял с помощью 2 функций, обращающиеся друг к другу (наверное не очень оптимизированное, зато ленивое решение) Функции HLine, VLine возвращали существует ли путь от некоторой ячейки до стартовой ячейки с первой горизонтальной/вертикальной чертой. Что-то вроде:
Код:
Function HLine(FromX,FromY) as Boolean
If FromY=StartY And FromX<>StartX Then
HLine=True
AddPoint(FromX,FromY)
Else
Hline=False
For J=1 To Columns
  If J<>FromX and not M(FromY,J).Empty Then
   If VLine(J,FromY) Then
    HLine=True
    AddPoint(FromX,FromY)
    Exit For
   End If
  End If
Next J
End If
End Function

Аналогичная VLine. Работало как-то.

 
 
 
 Re: Транспортная задача: нахождение цикла (замкнутого пути)
Сообщение27.09.2012, 14:23 
Кажется, что информацию удобно хранить в виде двудольного графа. Вершины одной доли соответствуют "складам", а второй - "магазинам". Соединяем две вершины ребром, если соответсвующая переменная входит в базу. Циклы в таблице будут соответствовать циклам в графе.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group