ПАРАЛЛЕЛЬНЫЙ ПЕРЕБОР С ИСПОЛЬЗОВАНИЕМ TCP/IP СЕТИ НА ПРИМЕРЕ ЗАДАЧИ КОММИВОЯЖЕРА

Марков С., Чапкин С.
Научный руководитель: Костенко Т.П.

          Использование мощной аппаратной базы при решении переборных задач часто позволяет добиться качественного роста эффективности, не смотря на экспоненциальную сложность большинства переборных схем.
          С увеличением глубины минимаксного перебора в шахматах, шашках и других подобных играх происходит стабилизация оценки позиции. Однако разница оценок для достигнутых на сегодняшний день глубин перебора все еще остается значительной. Увеличение глубины просмотра на 2-3 полухода позволяет в большинстве случаев получить решающее преимущество. Именно этот фактор стал одним из немаловажных условий победы шахматного компьютера Deep Blue, аппаратная часть которого позволяла просматривать в одну секунду более 200 млн. позиций.
          Однако, следует отметить тот факт, что создание подобной аппаратной базы с последующим ее совершенствованием приводит к значительному росту финансовых и временных затрат.
          Альтернативой использованию специализированной аппаратной базы для решения переборных задач является использование распределенных, аппаратно-независимых систем. Одним из примеров такой системы является сетевая реализация алгоритма Литтла для задачи коммивояжера. Объединенные усилия машин сети позволяют обеспечить достижение огромной производительности. Причем подключение новых и модернизация старых узлов сети позволяет добиться роста производительности без внесения изменений в программную часть вычислительного комплекса.
          Спецификой алгоритма Литтла для задачи коммивояжера является возможность значительного улучшения результатов за счет увеличения вычислительной мощности. Это связано с тем, что, не смотря на экспоненциальную сложность алгоритма, эффективность отсечения столь высока, что позволяет даже для больших графов (60-70 узлов) находить точные решения за приемлемое время. Для больших графов возможно нахождение приблизительных решений, отличие которых от точных весьма невелико. Для 400-500 вершин перебирая несколько десятков миллионов узлов оказывается возможным нахождение решения, отклонение которого от точного не превышает 10%.
          Авторами работы реализован параллельный вариант алгоритма Литтла для вычислений в TCP/IP сети. Система основана на концепции клиент-сервер. Приложение-сервер осуществляет самостоятельный перебор решений на основе алгоритма Литтла, использующего в качестве начальной оценки путь, полученный приближенным полиномиальным алгоритмом, что позволяет достичь большей эффективности отсечения. Приложения-клиенты, подключаясь к серверу, сообщают ему о готовности начать перебор. Сервер выделяет в дереве перебора поддерево достаточной глубины и пересылает его клиенту, а затем получает от клиента результат перебора этого поддерева. Глубина поддерева выбирается с таким расчетом, чтобы:
          а) клиент затратил на его обработку не менее нескольких секунд (в противном случае непозволительно возрастет нагрузка на сеть);
          б) время отсечения не превысило некоторой величины, определяемой в каждом конкретном случае для конкретного графа (суть этого ограничения заключается в том, чтобы при сбое клиента потерять как можно меньше времени на повторный перебор).
          Оценка, полученная клиентом, используется сервером для отсечения в ходе собственного перебора. В случае если оценка, полученная клиентом, меньше наилучшей найденной на данный момент, сервер осуществляет широковещательную рассылку этой оценки, для повышения эффективности отсечения в приложениях-клиентах.
          Сервер запоминает задания, выданные клиентам, и в случае сбоя клиентов перебирает эти задания самостоятельно или же рассылает другим клиентам.
          Алгоритм построен таким образом, чтобы уменьшить нагрузку на линии связи, т.к. для распределенной TCP/IP системы слабым звеном являются именно каналы связи.