2014 dxdy logo

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

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




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


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

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

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

 Профиль  
                  
 
 Re: Транспортная задача: нахождение цикла (замкнутого пути)
Сообщение31.07.2012, 11:00 


26/08/11
2057
Я когда-то писал программу для транспортной задачи...на бейсик. Поиск пути осуществлял с помощью 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 


10/11/06
64
Кажется, что информацию удобно хранить в виде двудольного графа. Вершины одной доли соответствуют "складам", а второй - "магазинам". Соединяем две вершины ребром, если соответсвующая переменная входит в базу. Циклы в таблице будут соответствовать циклам в графе.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group