Здравствуйте!
Я пишу программу генетического алгоритма для составления расписания. На вход задается некоторое количество заданий и одинаковых процессоров. Кроме того, есть орграф без циклов, который задает частичный порядок на множестве этих заданий. Особь в генетическом алгоритме представляет собой некоторую перестановку номеров заданий. Ограничения на перестановку накладываются частичным порядком(нет смысла вдаваться в подробности, если заинтересовались, см. контакты ниже). Естественно, для выбора допустимой перестановки использовать топологическую сортировку.
Я слышал, что есть несколько видов топологической сортировки, но не смог найти больше двух - по определению (см. википедию), уровневая топологическая сортировка (статья есть на хабрахабр). Если кто знает, где можно прочитать про другие виды, напишите, пожалуйста! Желательно, чтобы были оценки трудоемкости.
Кроме того, если кто-нибудь сталкивался с исследованиями в этой области (не ГА вообще, а ГА с частичным порядком заданий), дайте, пожалуйста, ссылку на ресурсы.
!!! Если кто заинтересовался этой областью, предлагаю совместные исследования !!! .
ссылки для связи: 1) skype: dmitrykober 2)
dmitry.kober@gmail.com
06.02.2011, 15:53 