Привет. Подскажите плиз, что такое эвристический метод? Или может ссылку какую. Я просто недавно узнал, что один из оптимальных вариантов составления алгоритма генерации расписания занятий - это эвристическим методом. Подскажите плиз.

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

Возможно. Но точно я не знаю.

Эвристический метод -- ето метод с использованием эвристик.

То есть неких "дополнительных правил", наличие или отсутствие которых, скорее всего, на правильность основного метода, но может ускорить поиск решения, скажем сильно сужая пространство перебираемых вариантов.

Иногда эвристики основываются на каком-либо дополнительном знании о исходных данных, иногда на знании о структуре получаемого результата. Иногда введение эвристик сочетается с ограничением глубины перебора/точности вычислений и т.п., что позволяет либо с высокой но не 1й вероятностью найти правильное или оптимальное решение, либо найти решение близкое к оптимальному, но не обязательно оптимальное.

Например, для составления расписания занятий в институте, программа может пользоваться общим алгоритмом (перебор), но учитывать, что основная масса дисциплин имеет серии занятий, проводимых в одной и той же аудитории, одним и тем же преподавателем, для разных групп студентов. И исходя из етого вот соображения формировать начальное заполнение таблицы с расписанием, а сам перебор вариантов ограничить применением фиксированного набора каких-нибудь элементарных изменений в полученном после начального заполнения расписании. Решение для основной массы "реальных" задач по составлению расписания в институте будет очень близко к оптимальному.

Еще часто упоминают о генетических алгоритмах применительно к задаче, в том числе, составления расписания. Но их я объяснять не берусь .

Привет!

Совсем недавно (два месяца назад) я взялся за изучение этих генетических алгоритмов по простой причине - меня взяли на "работу" v odnu laboratoriju (Хотят посмотреть как я справляюсь с их заданиями. По этому в ковычках, и деньги мне не платят). Как мне не было страшно, все показалось достаточно просто . Но на самом деле выбрать ту или иную эвристику для конкретной задачи очень трудно.

Ты можешь применить эти методы для решения своей задачи, но они могут и не найти оптимального решения (впрочем, как правильно заметил господин, писавший до меня - это особенность всех эвристик). Для начала, определи функцию, которая будет оценивать твои решения. Решения - последовательность признаков, закодированных в геноме (каждый геном представляет из себя закодированный феном, причем ему соответствует уникальный феном). После этого самое сложное - определение функции мутации генома, скрещевания (кросовер) и других изменений. Ты можешь использовать уже готовые эвристические методы изменений ([2-OPT, 3-OPT, 4-OPT, OR1, OR2, EX1,...]), из них я бы выделил только :2-OPT т.к. он наиболее быстро генерирует решения с лучшим качеством. А теперь самое страшное - выбор вероятностей для выполнения скрешивания, мутации и т.д. Ну что тут сказать? Это работка для нехилого математика. Ну ты можешь, конечно прикидывать, пробовать, но какой-нибудь более-менее оптимальный выбор вероятностей ты не сделаешь. Ну это можно и на практике пробовать. Так что не пугайся.
Значит так, допустим функция, которая определяет качество решения, называется :Q() , Ты написал также кросовер :C() и функцию мутации :M(). Далее ты определяешь вероятности: повторять с вероятностью 1/2 скрешивание, с вероятностью 1/4 мутацию на каждой итерации (как-бы поколении). Количество итераций ты можешь делать сколь угодно, но на них уходит время! Вообще можно определить какое-нибудь условие останова жизни этих геномов, например, если оценка очередного решения будет больше 10 :Q(x)>10.
Кросовер можно сделать так: вероятностно выбирается место пересечения двух геномов и два генома обмениваются генами лежашими по разные стороны от точки пересечения. Например в твоем геноме 10 генов, а точку ты выбрал вероятностно - 3 :
первыи геном до скрещивания: АААААААААА
второй геном: ББББББББББ
После скрещивания:
первыи - АААБББББББ
Второй - БББААААААА

Можно поставить условие, что скрещивать геномы, оценка которых больше какого-нибудь уровня. Например:

if Q(x1)>4 and Q(x2)>4 then C(x1, x2)


Короче импровизировать можно много Твоя задача ускорить расчет. Поэтому придется много экспериментировать.
Ну если что, спрашивай...

Большое спасибо

Эвристические методы по сути методы, основанные на предположениях "здравого смысла"... Методы не обладающие строгими доказательствами нахождения оптимального решения...
Самого по себе понятия "эвристический метод" не существует, он возникает лишь в случае решения какой-то конкретной задачи (как и метод "ветвей и границ")...
К эвристическим приемам склоняются, когда для нахождения оптимального решения задачи необходимо перебрать достаточно много промежуточных решений и нет строгих доказательств, позволяющих значительно этот перебор сократить и, конечно же, в итоге, с вероятностью 1 получить оптимальное решение (например, переборные задачи на графах, в том числе задача о составлении расписания и т.п.)