?

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

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 SPbPU 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 Анализ
  • Заключение
  • Список литературы
  • Приложение

Usage statistics

stat Access count: 245
Last 30 days: 1
Detailed usage statistics