С 17 марта 2020 г. для образовательных ресурсов Электронной библиотеки СПбПУ установлен особый режим их использования

Details

Title: Алгоритмы многопоточного программирования для поиска оптимального пути: бакалаврская работа: 09.03.02
Creators: Шатиленко Владислав Николаевич
Scientific adviser: Хлопин Сергей Владимирович
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт компьютерных наук и технологий
Imprint: Санкт-Петербург, 2017
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: многопоточное программирование; дискретная оптимизация; задача коммивояжера; генетические алгоритмы
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Speciality code (FGOS): 09.03.02
Speciality group (FGOS): 090000 - Информатика и вычислительная техника
DOI: 10.18720/SPBPU/2/v17-5912
Rights: Свободный доступ из сети Интернет (чтение, печать, копирование)

Allowed Actions:

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

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

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print Download
Internet Authorized users Read Print Download
-> Internet Anonymous

Table of Contents

  • Оглавление
  • Введение
  • 1. Постановка задачи
  • 2. Многопоточность
    • 2.1 Определение и создание
    • 2.2 Синхронизаторы
  • 3. Задача коммивояжера
    • 3.1 Формулировка задачи коммивояжера
    • 3.2 Алгоритмы решения
  • 4. Методы оптимизации
    • 4.1 Генетические алгоритмы
      • 4.1.1 Общее описание генетического алгоритма
      • 4.1.2 Базисные определения
      • 4.1.3 Отбор родителей
      • 4.1.4 Скрещивание
      • 4.1.5 Мутация
      • 4.1.6 Условие завершения
    • 4.2 Метод имитации отжига
  • 5. Реализация
    • 5.1 Базовая реализация генетического алгоритма
    • 5.2 Многопоточная реализация
  • 6. Анализ производительности
    • 6.1 Закон Амдала
    • 6.2 Анализ
  • Заключение
  • Список литературы
  • Приложение

Document usage statistics

stat Document access count: 220
Last 30 days: 5
Detailed usage statistics