Задача нахождения кратчайшего пути является, пожалуй, наиболее важной задачей теории графов. Существует множество алгоритмов поиска как кратчайших, оптимальных путей, так и субоптимальных путей. Субоптимальным путём будем называть путь, ведущий из начальной в конечную точку, но отличающийся от оптимального пути. Смысл нахождения субоптимальных путей легко рассмотреть на таком примере: предположим, что задача поиска пути напрямую описывает наш путь по городу. В таком случае оптимальный путь в зависимости от времени может оказаться невозможным к реализации (например, одна из ветвей дороги перегорожена пробкой из-за аварии). В таком случае нас будет интересовать субоптимальный путь, или по-другому, объезд.
(далее...)
Записи с меткой «университет»
Работы, связанные с обучением
09 Декабрь 2009
Поиск путей в графе
16 Ноябрь 2009
Искуственный интеллект
Разум и преподаватели университета порой ставят перед нами очень интересные и в некотором смысле даже неразрешимые задачи. Одной из таких задач на моей памяти оказалось создание искусственного интеллекта, хотя бы на самом элементарном уровне.
Искусственный интеллект (ИИ) (англ. Artificial intelligence, AI) — это наука и разработка интеллектуальных машин и систем, особенно интеллектуальных компьютерных программ, направленных на то, чтобы понять человеческий интеллект. При этом используемые методы не обязаны быть биологически правдоподобны. Но проблема состоит в том, что неизвестно какие вычислительные процедуры мы хотим называть интеллектуальными. А так как мы понимаем только некоторые механизмы интеллекта, то под интеллектом в пределах этой науки мы понимаем только вычислительную часть способности достигнуть целей в мире.
Хоть нам и неизвестно, что такое интеллект, тем более искусственный интеллект (в дальнейшем ИИ или AI), попробуем создать идею и очертить круг интеллектуальных задач для элементарной системы.
18 Май 2009
Физический симулятор
Моделирование физических процессов в графической среде всегда считалось интересной задачей. К сожалению, эту задачу редко рассматривают напрямую в рамках дисциплины систем реального времени, хотя она вполне может быть удачной демонстрацией графических приложений реального времени.
Я поставил перед собой задачу написать простой физический симулятор и реализовать его работу в реальном времени в многопоточном режиме.
Кое-что из этого даже получилось!
Скриншот - Физический симулятор
13 Апрель 2009
Менеджер памяти MC Heappie
В наше время при разработке мало-мальски сложных проектов просто необходимо использовать динамическую память под переменные – уместиться в рамки предопределённых массивов и переменных стало просто невозможно, а динамические структуры, будь то связанные списки или деревья, являются сейчас неотъемлемой частью любой программы. В то же время стандартные средства выделения памяти в C/C++ отличаются некоторой медлительностью. Известно, что функции malloc / free очень плохо работают на большом количестве мелких переменных, а функция realloc вообще является ужасом для более-менее опытного программиста.
По этой причине зачастую приходится разрабатывать какой-либо собственный контроллер памяти, который бы удовлетворял запросам скорости, и не использовал слишком много памяти под собственные нужды.
Определим круг задач и требований, которые мы предъявляем к менеджеру памяти:
1. Интерфейс менеджера должен содержать две основных функции – выделение памяти и освобождение памяти.
2. Функция выделения памяти mc_alloc () должна получать на вход размер переменной, под которую необходимо распределить место.
3. Функция освобождения памяти mc_delete () должна освобождать память по указанному адресу.
4. Менеджер памяти должен обладать универсальностью – не должно существовать ограничений на объём выделяемой памяти.
5. Объём памяти, нужный для работы самого менеджера, должен быть минимален – желательно не более 10% от размера выделяемой памяти.
6. Необходимо достигнуть производительности минимум в два раза выше, чем контроллер памяти malloc/free в C/C++.
Существует множество подходов к распределению памяти системы. Мы не будем рассматривать их все – Интернет и так кишит информацией на эту тему. Лучше перейдём напрямую к самому алгоритму менеджера памяти MC Heappie.
13 Январь 2008
Создание ландшафта по карте высот (OpenGL)
В своё время попалась мне в руки одна очень интересная задачка - реализация программы, которая строит ландшафты по карте высот. В качестве карты высот можно было бы использовать любое растровое изображение, яркость точки на котором была бы для нас высотой её над поверхностью ...
Как известно, Э.Э. Александров никогда не подкидывает неинтересных задачек, что ж, я взялся, кое-что из этого вышло ...
Генерация ландшафта по карте высот
Мы реализуем метод построения поверхности по "карте высот". Картой высот называют растровое изображение, на котором интенсивность света определяет высоту точки над некоторым нулевым уровнем.