2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Виды топологической сортировки / генетический алгоритм
Сообщение06.02.2011, 15:53 


06/11/09
35
Каир, но родом из России
Здравствуйте!

Я пишу программу генетического алгоритма для составления расписания. На вход задается некоторое количество заданий и одинаковых процессоров. Кроме того, есть орграф без циклов, который задает частичный порядок на множестве этих заданий. Особь в генетическом алгоритме представляет собой некоторую перестановку номеров заданий. Ограничения на перестановку накладываются частичным порядком(нет смысла вдаваться в подробности, если заинтересовались, см. контакты ниже). Естественно, для выбора допустимой перестановки использовать топологическую сортировку.

Я слышал, что есть несколько видов топологической сортировки, но не смог найти больше двух - по определению (см. википедию), уровневая топологическая сортировка (статья есть на хабрахабр). Если кто знает, где можно прочитать про другие виды, напишите, пожалуйста! Желательно, чтобы были оценки трудоемкости.

Кроме того, если кто-нибудь сталкивался с исследованиями в этой области (не ГА вообще, а ГА с частичным порядком заданий), дайте, пожалуйста, ссылку на ресурсы.

!!! Если кто заинтересовался этой областью, предлагаю совместные исследования !!! .
ссылки для связи: 1) skype: dmitrykober 2) dmitry.kober@gmail.com

 Профиль  
                  
 
 Re: Виды топологической сортировки / генетический алгоритм
Сообщение10.02.2011, 10:15 


06/11/09
35
Каир, но родом из России
Возможно, кто-нибудь знает эффективный способ перебора всех возможных для данного орграфа перестановок вершин, полученных топологической сортировкой?

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

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



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

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


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

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