Генетический алгоритм
Задача из реальной жизни. Маленький пузатый гоблин хочет добраться из точки А в точку Б. Как ему выбрать самый лучший маршрут?
Программистам известны тысячи способов решения этой задачи. Можно, например, квадратно-гнездовым способом перебрать все возможные варианты. Заставить гоблина бегать из точки А в точку Б разными маршрутами, и каждый раз смотреть с секундомером, в какое время он уложится. Этот способ, конечно, требует огромного количества времени, однако на маленьких картах он таки работает.
Второй способ. Засеять карту сухой травой. Поджечь точку А. Смотреть, как кольцо пожара будет расширяться и увидеть, каким маршрутом огонь придёт в точку Б.
Третий способ. Подвести к точке А плюс пять вольт, а к точке Б, наоборот, минус пять вольт. Посмотреть, какой маршрут выберет электрический ток.
Короче, решений много. Для справки: эта задача — выбор оптимального пути движения для монстров — и по сей день ни разу не решена создателями компьютерных игр (достаточно быстрого алгоритма не придумано). Ресурсов процессора на обсчёт маршрутов тратится очень много, а монстры всё равно нередко умудряются запутаться «в трёх соснах».
Так вот. Одним из хитровыдуманных способов поиска лучшего маршрута является «генетический алгоритм», подсмотренный у «природы».
( Collapse )
Программистам известны тысячи способов решения этой задачи. Можно, например, квадратно-гнездовым способом перебрать все возможные варианты. Заставить гоблина бегать из точки А в точку Б разными маршрутами, и каждый раз смотреть с секундомером, в какое время он уложится. Этот способ, конечно, требует огромного количества времени, однако на маленьких картах он таки работает.
Второй способ. Засеять карту сухой травой. Поджечь точку А. Смотреть, как кольцо пожара будет расширяться и увидеть, каким маршрутом огонь придёт в точку Б.
Третий способ. Подвести к точке А плюс пять вольт, а к точке Б, наоборот, минус пять вольт. Посмотреть, какой маршрут выберет электрический ток.
Короче, решений много. Для справки: эта задача — выбор оптимального пути движения для монстров — и по сей день ни разу не решена создателями компьютерных игр (достаточно быстрого алгоритма не придумано). Ресурсов процессора на обсчёт маршрутов тратится очень много, а монстры всё равно нередко умудряются запутаться «в трёх соснах».
Так вот. Одним из хитровыдуманных способов поиска лучшего маршрута является «генетический алгоритм», подсмотренный у «природы».
( Collapse )